Ant colony optimisation for the Sudoku problem.
General (not guaranteed unique solution) instances of 9x9, 16x16 and 25x25 sudoku. File name is inst_f_n.txt, where f is the fixed cell percentage (0-95) and n is the instance number (100 for each size and fixed cell fraction).
Sixteen 9x9 logic-solvable instances. See the paper for details.
make -f Makefile
The makefile uses g++ to compile. However, any C++ compiler should work, as long as it supports the C++11 standard.
Alternatively, for windows, there is a Visual Studio 2017 project file in the vs2017 folder.
--alg n n=0 (default) use Ant Colony System. n=1 use backtracking search
--file filename open puzzle instance in filename
--puzzle puzzle_string read puzzle in string format - use '.' for blank cells, 1-9 for 9x9, 0-f for 16x16, a-y for 25x25.
--blank start with a blank grid, need to set order
--order set the order for a blank grid (3, 4 or 5 for 9x9, 16x16, 25x25)
--verbose print the solution after solving. If not set, the code outputs 0 (success) or 1 (fail) followed by the elapsed time
--showinitial print the initial (constrained) grid. The grid is constructed by setting each given cell in turn, and propagating the constraints. In some cases this is sufficient to solve the puzzle, so the initial constrained grid will be the solution.
--timeout secs set the timeout in seconds (default 10 seconds)
--nAnts n set number of ants, default 10
--q0 value set ACS q0 parameter (which controls greediness) - default 0.9
--rho value set ACS rho parameter (which controls pheromone evaporation) - default 0.9
--evap f use value f for the best-value evaporation parameter. Default is 0.005
Solve the 'platinum blond' puzzle using ACS, showing the initial constrained grid and the full solution
./sudokusolver --file instances/logic-solvable/platinumblond.txt --showinitial --verbose
Solve a 16x16 general instance using backtracking seach
./sudokusolver --alg 1 --file instances/general/inst16x16_45_10.txt --verbose