Cancel
Showing results for 
Search instead for 
Did you mean: 

Solving Sudoku Puzzles

Siemens Phenom Siemens Phenom
Siemens Phenom

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.

 

Problem.gif

 

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.

 

Solution of the given puzzle

 

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.

 

References

Delahaye, Jean-Paul: The Science Behind Sudoku. Scientific American 294 (2006), 80-87.

Krawitz, Björn (personal communication 2006)

2 REPLIES

Re: Solving Sudoku Puzzles

Solution Partner Valued Contributor Solution Partner Valued Contributor
Solution Partner Valued Contributor
It's great!

Betreff: Solving Sudoku Puzzles

Gears Phenom Gears Phenom
Gears Phenom

Nice one, thank you Peter!

 

I could not resist and had to tamper with it a bit Smiley Happy 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 Smiley Happy

 

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? Smiley Happy ) fun for me to use Plant Simulation for solving Sudokus than solving them manually ^^

____________________________________________________________
Alex Dilg, Consultant at SimPlan AG (www.SimPlan.de)
This post was good and/or helpful to you? Please provide some Kudos, thank you!