The objective is to fill the 9×9 grid with numbers from 1 to 9 such that each row, column, and 3×3 boxes contains each number exactly once. For a particular puzzle some pre-defined hints are given.
We want to develop a simple algorithm for solving such a Sudoku problem that can be implemented by SimTalk in Plant Simulation. An appropriate data structure is a table with 9×9 cells. The cells are lists of data type integer. Such a list saves the set of possibilities. This data structure is able to store a solved or an unsolved puzzle.
The basic idea is a recursive procedure with a parameter of the described data structure. If there is an empty cell then the puzzle is unsolvable. Each recursive procedure needs such an exit condition. For a cell with at least 2 possibilities the procedure is recursively called with all possible values. A corresponding subroutine reduces the sets of possibilities of the other cells. If all cells have exactly one possibility a solution is found.
The model file for Plant Simulation 11 TR 2 contains some example puzzles. Press the button and select a Sudoku problem containing in the collection. You can early terminate the algorithm by pressing again the button. Otherwise the algorithm finds all possible solutions.
The maximal depth of the recursive calls of the recursive procedure describes the complexity of the problem. But this description depends on the algorithm and its implementation.
For an unique solution 17 hints seems to be necessary. Note that 77 hints are not enough for an unique solution.
Delahaye, Jean-Paul: The Science Behind Sudoku. Scientific American 294 (2006), 80-87.
Krawitz, Björn (personal communication 2006)
Nice one, thank you Peter!
I could not resist and had to tamper with it a bit I should say, I was not trying to "improve" it, I only wanted to see whether some checks that I do as a human when solving Sudokus can speed up the "brute-force" algorithm
I've added some checks to fix certain cells before going into deeper recursions. I've walked through each column and row and checked whether I can find a number that appears in only one list of possible cell-values in that column/row and then I fixed that cell to this number.
This reduces computation time and also the requried call-depth, especially for more complex puzzles (for puzzle B2: down from 104s to 14s and from 40 recursions to 30).
And I've realized: It's great (more? ) fun for me to use Plant Simulation for solving Sudokus than solving them manually ^^