The Hungarian algorithm finds the exact minimum-cost one-to-one pairing between n workers and n tasks in cubic time, and the Assignment Problem Solver applies it directly to any labelled square cost matrix up to 20 by 20. You paste a comma-separated grid whose first row begins with a leading comma and lists task names, whose next rows start with a worker name and one finite cost per task, then read back a unique task for every worker, the cost of each pairing, and the minimum total. Every computation happens inside the browser, the solver enforces deterministic row and column tie-breaking so identical costs resolve the same way on every run, and the finished assignment can be copied as plain text for homework, manual checks, or a small scheduling draft. The implementation follows the primal-dual method that Harold W. Kuhn described in 1955 and that Google OR-Tools documents as the standard for complete weighted bipartite assignment.
The Assignment Problem in Plain English
An assignment problem models a complete weighted bipartite graph: one side holds workers, machines, agents, or other resources, and the other holds tasks, jobs, locations, or choices. Every matrix cell is the cost of pairing one worker with one task, and a valid solution picks exactly one cell from every row and exactly one from every column so that no worker takes two tasks and no task is given to two workers. The goal is to minimise the sum of the chosen cells, which is why textbook problems are written as cost matrices rather than profit tables.
The same shape appears under many labels. Assigning technicians to jobs, drivers to routes, classrooms to periods, and parcels to vehicles all reduce to the same problem once every option has been given a single number. The discipline is keeping the model honest: each cell must genuinely represent the cost of doing that one pairing, and the matrix must stay square so that every worker can be matched and no row is left dangling.
How the Hungarian Algorithm Reaches the Minimum
The solver runs a primal-dual Hungarian algorithm, also known as the Kuhn–Munkres method. It maintains row and column potentials — auxiliary values that act like shadow prices on every row and column — and repeatedly augments a minimum reduced-cost matching until all rows have been incorporated. After the last row is added, every task column points to exactly one worker, giving the unique one-to-one pairing you wanted.
Two properties make this useful for the "with steps" framing the calculator promises. First, the algorithm runs in cubic time on an n by n matrix, which is fast enough for the 20 by 20 browser bound the tool exposes and well within reach for hand calculation on a 3 by 3 or 4 by 4 example. Second, the routine is exact: it returns the minimum-cost pairing for the matrix you entered, not an approximation. Ties between equally cheap pairings are resolved by the natural row and column order, so the same input always yields the same output — which is the property you want when you are verifying a manual reduction or comparing two drafts.
For a deeper treatment of the underlying search and the role of the potentials, the Google OR-Tools assignment guide walks through the reduced-cost graph and the augmenting-path logic in detail.
Building a Cost Matrix the Solver Accepts
- Open the Assignment Problem Solver and clear the default matrix so the input field is empty.
- Write the header row so it begins with a comma, then list every unique task name separated by commas, for example ",Task A,Task B,Task C". The leading comma leaves the top-left cell empty and matches the parser's expectation.
- Add one worker per row. Each line starts with the worker's name and then contains exactly one finite numeric cost for every task, separated by commas. Keep worker and task counts equal so the matrix stays square.
- Check that every cost is finite (no blanks, no NaN, no infinities) and that every label is unique. Costs may be positive, zero, or negative when the sign convention genuinely fits your model.
- Paste the matrix into the input box, run the solver, then read the table of pairings, the per-pairing costs, and the minimum total. Copy the assignment as text if you need to paste it into a report or a chat reply.
A 3×3 Worked Example
The simplest case the solver accepts is one worker per task with three options each. Using the matrix below, the assignment with the smallest total cost has a sum of 5.
| Worker | Task 1 | Task 2 | Task 3 |
|---|---|---|---|
| Worker A | 4 | 1 | 3 |
| Worker B | 2 | 0 | 5 |
| Worker C | 3 | 2 | 2 |
Enumerating the six valid permutations shows the same thing the solver shows. Worker A to Task 2 (cost 1), Worker B to Task 1 (cost 2), Worker C to Task 3 (cost 2) gives 1 + 2 + 2 = 5, and no other valid pairing drops lower — the next-best candidates come in at 6 and 7. The deterministic tie-breaking means that if you re-run the matrix the calculator reproduces the same pairing, which is the behaviour you need when you are cross-checking a manual Hungarian reduction row by row.
Running the Solver and Reading the Output
The result panel returns three pieces of information for every run. First, a list of pairings that names exactly one task for every worker and exactly one worker for every task, so no row or column is reused. Second, the cost of each pairing as it was read from your matrix, using the same sign and units you entered. Third, the minimum total, which is the sum of the per-pairing costs and the value you should compare against a hand calculation or another solver.
The matrix parser is strict on purpose. Rectangular matrices, duplicate names, blanks inside a row, NaN values, and infinite costs are rejected with a visible message rather than silently coerced. If you see a rejection, fix the input rather than trying to work around it, because the Hungarian routine assumes every cell is finite and every row and column is uniquely labelled.
| Input condition | Status | Reason |
|---|---|---|
| Square matrix with unique names and finite costs | Accepted | Matches the complete weighted bipartite model the algorithm expects |
| Rectangular matrix (more workers than tasks, or vice versa) | Rejected | The solver matches one task per worker; padding belongs in your input, not the solver |
| Blank, NaN, or infinite cost | Rejected | The algorithm needs every cell to be a finite number |
| Duplicate worker or task name | Rejected | Labels must identify a unique row or column |
When the Cost Matrix Is Not Enough
The Hungarian routine minimises the numeric sum of the cells you entered and nothing else. It does not see skill thresholds, workload capacity, team dependencies, fairness, travel time that depends on the order of visits, precedence between tasks, multiple tasks per worker, worker availability windows, or uncertainty unless those effects are already encoded in the costs. Real staffing decisions also involve legal, ethical, and human considerations that cannot be reduced to a number. Treat the solver as a transparent mathematical baseline, then layer your own rules on top of the answer before acting on it.
Two practical traps deserve a callout. First, the solver always minimises, so if your data are profits or scores to maximise, transform them deliberately — for example, subtract every score from a large constant — or pick a model designed for maximisation. Pasting scores and assuming that "best" automatically means largest will quietly return the wrong answer. Second, blank or forbidden pairings are not supported in this version; every matrix cell must contain a finite cost, so a forbidden pair must be entered as a large penalty that genuinely represents the cost of allowing it.
When to Step Up to a Larger Solver
The 20 by 20 browser bound is large enough for classroom examples, manual Hungarian checks, and modest scheduling drafts, and the cubic-time algorithm returns the optimum immediately at that scale. Beyond that, the same minimum-cost pairing structure can be expressed as a linear assignment problem inside a mixed-integer program, a constraint program, or a min-cost flow network, where you can add the real-world rules described above and still let a validated solver search for an optimum. If you need to encode capacity, skill levels, or forbidden assignments explicitly, move to one of those tools rather than smuggling the rule into a single cost cell.
For a homework check, a quick sanity test on a 5 by 5 job assignment, or a draft schedule that fits on one screen, the Assignment Problem Solver gives you the exact optimum in one paste-and-run. For anything larger or more constrained, build the same matrix as the cost block of a richer model and let a dedicated solver carry the extra rules.