Sign in to follow this  

Sudoku program

This topic is 4398 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I have been attempting to write a program in C which solves Sudoku puzzle games. I am first outlining the rules of this puzzle for those of you unfamiliar with it. 1.It contains a 9x9 matrix. 2.Each row,column and 3x3 submatrices need to be filled with numbers 1 to 9 3.In no row,column or 3x3 submatrix should a number be repeated. I first decided to write a program to solve a mini version of Sudoku with a 4x4 matrix,2x2 submatrices and numbers 1 to 4. Here is the algorithm which I used. 1.I generated all possible combinations with numbers 1 to 4 for the first row and for each of those combinations I generated all possible combinations for the second row and so on for all the rows. 2.Then I checked if any number was repeated in any column or 2x2 submatrix in each of the 4x4 matrix generated by the previous step. If not I compared the matrix generated with the incomplete 4x4 matrix in the question. If it matched the output is displayed else the next matrix is generated and compared. The program worked for 4x4 Sudoku puzzles but did not for 9x9 Sudoku puzzles. I think it takes too long for each matrix to be generated. Is there any way to increase the speed of processing or should I try a different logic? Please help

Share this post


Link to post
Share on other sites
Personally I'd try a different approach. Instead of generating all concievable boards, you would be better off dealing with 'possibilities.'

Each cell would store a list of possible values, and the aim of the solver is to produce a board in which there is exactly one value in each list.

You'd search for cells in which the list has only one value and remove that value from the lists of all other cells in the same row/column/block. Repeat until no more removals can be made. (This is known as the 'reduction' step).

Unless you're very lucky, you'll probably be faced with a board in which there are still some cells with multiple values in. Pick one of those cells, and 'split' it - turn your one board, with a cell [1,2,5], into three boards, where the cell has [1] in the first, [2] in the second and [5] in the third.

Perform the reduction step again, then split, the reduce, then split, etc etc. If at any time you encounter a cell with no values in its list, you can throw that particular board away as being no good and continue on with the next.

Share this post


Link to post
Share on other sites
Sign in to follow this