Assignment Problem Solver (Hungarian Algorithm)

Features

• Optimal solution via the Hungarian algorithm, no permutation search
• Both minimisation and maximisation
• Handles non-square matrices and lists the unassigned rows or tasks
• Numeric and labelled matrices, detected automatically
• One row per assignment, each copyable on its own
• Reports the total cost (shown as total value when maximising)
• Optionally require a square matrix, with a clear error if it is not
• A provably optimal result, guarded by a known-optimum assertion

How to use

1. Paste the cost matrix (numbers only, or with row and column names)
2. Choose the problem type: minimise or maximise
3. For a non-square matrix, choose automatic handling or require a square
4. The result appears as you type; copy the assignments you need

FAQ

What matrix format does it accept?

Two shapes. (1) Numbers only: each line is one row of costs, separated by spaces or commas, with rows and columns named R1… and C1…. (2) Labelled: the first line lists column names, and every following line starts with a row name followed by that row of costs. The rule is "if any field on the first line is not a number, parse as labelled", so a purely numeric table is never misread.

What happens when the number of rows and columns differ?

In automatic mode, surplus columns are added with zero cost when there are more rows, and the rows that end up unassigned are listed; with more columns, surplus rows are added and the undone tasks are listed. Every row and column constraint is satisfied, and the total is still optimal. Choose "Require a square matrix" if you want it to refuse instead.

Is the optimum reliable?

Yes. It uses the standard shortest-augmenting-path Hungarian algorithm, O(n³), which finds the global optimum for any real cost matrix. A test pins a known-optimum 5×5 matrix (optimum 13), and another cross-checks against brute-force enumeration on a 4×4.

How is maximisation handled?

The costs are negated and then minimised — mathematically the same as maximising. The result shows the sum of the original values and labels it "Total value", so you never see a row of negative numbers.