[Help-glpk] generating diverse sudoku solutions with mathprog

[Andrew Makhorin]

I modified the sudoku example model (please see the attachment) to
accumulate all previously found solutions in a text file, which is
the mathprog data section. The solution components stored in the file
are used in packing inequalities to forbid all the previous points,
that allows (in principle) to obtain all solutions. This technique can
also be used to prove that the instance has exactly one solution.

$ glpsol -m sudoku.mod -d sudoku.dat

 +-------+-------+-------+
 | 1 6 4 | 7 5 8 | 2 3 9 |
 | 2 5 8 | 6 9 3 | 7 1 4 |
 | 3 7 9 | 2 1 4 | 8 6 5 |
 +-------+-------+-------+
 | 7 8 2 | 1 4 9 | 6 5 3 |
 | 5 1 6 | 3 8 2 | 9 4 7 |
 | 4 9 3 | 5 6 7 | 1 8 2 |
 +-------+-------+-------+
 | 6 4 5 | 9 7 1 | 3 2 8 |
 | 9 2 1 | 8 3 5 | 4 7 6 |
 | 8 3 7 | 4 2 6 | 5 9 1 |
 +-------+-------+-------+

$ glpsol -m sudoku.mod -d sudoku.dat -d sudoku.sav

 +-------+-------+-------+
 | 1 6 4 | 7 2 8 | 5 3 9 |
 | 3 5 8 | 6 9 1 | 7 2 4 |
 | 2 7 9 | 3 5 4 | 8 6 1 |
 +-------+-------+-------+
 | 7 8 2 | 1 4 9 | 6 5 3 |
 | 5 1 6 | 2 8 3 | 9 4 7 |
 | 4 9 3 | 5 6 7 | 1 8 2 |
 +-------+-------+-------+
 | 6 4 5 | 9 7 2 | 3 1 8 |
 | 9 2 1 | 8 3 6 | 4 7 5 |
 | 8 3 7 | 4 1 5 | 2 9 6 |
 +-------+-------+-------+

$ glpsol -m sudoku.mod -d sudoku.dat -d sudoku.sav

 +-------+-------+-------+
 | 1 4 7 | 2 5 8 | 6 3 9 |
 | 2 5 8 | 6 9 3 | 4 1 7 |
 | 3 6 9 | 7 1 4 | 8 2 5 |
 +-------+-------+-------+
 | 5 8 2 | 1 4 9 | 7 6 3 |
 | 7 1 6 | 3 8 2 | 9 5 4 |
 | 4 9 3 | 5 6 7 | 1 8 2 |
 +-------+-------+-------+
 | 6 7 5 | 9 2 1 | 3 4 8 |
 | 9 2 4 | 8 3 6 | 5 7 1 |
 | 8 3 1 | 4 7 5 | 2 9 6 |
 +-------+-------+-------+

etc.

sudoku.mod
Description: MPEG movie

sudoku.dat
Description: Binary data