i need some help with this sudoku solver please help me The goal of this project
ID: 3629268 • Letter: I
Question
i need some help with this sudoku solver please help meThe goal of this project is to write a program for solving the Sudoku puzzle.
Write a program for solving the Sudoku puzzle.
The numbers in the puzzle are arranged in a 9 by 9 array of integers. But my own solution makes use of a 10 x 10 x 10 cube. The first two indices for this cube vary between 1 and 9 but the third is running from 0 to 9.
Actually, the bottom level (k = 0) represents the actual puzzle. Namely, the square matrix CUBE[i][j][0] (where 1 <= i <= 9, 1 <= j <= 9) represents the 9 by 9 array of the puzzle.
The elements CUBE[i][j][k] with 1 <= k <= 9 are used for keeping track of the possible values for CUBE[i][j][0]. Namely, the value of CUBE[i][j][k] is either 0 or 1 depending on whether or not k is a possible value for CUBE[i][j][0]. Clearly, if CUBE[i][j][0] already has a nonzero value then CUBE[i][j][k] should be set to 1 for 1 <= k <= 9.
So, whenever a new number is inserted into the puzzle, say CUBE[3][8][0] = 5, then CUBE[3][8][k] must be set to 1 for 1 <= k <= 9. Moreover, CUBE[i][j][5] must be set to 1 throughout row 3 and column 8. A similar elimination operation is needed with respect to the small 3 by 3 square that includes CUBE[3][8][0].
Indeed, the first thing to do after loading the initial values of the puzzle is to go through the entire puzzle and mark off all the positions in the upper levels of the CUBE which must be excluded from the possible choices at the each cell.
Now, counting the number of unmarked (i.e. 0) elements in the upper levels of the CUBE, we can determine the degree of freedom for every position in the puzzle. Namely, the degree of freedom for CUBE[i][j][0] will be the sum of the unmarked cells in the vector CUBE[i][j][k] for k = 1, 2, 3, … , 9. A separate 9 by 9 array, DEGREE[i][j], is used for recording the degrees of freedom for CUBE[i][j][0].
Clearly, if a cell is still empty (CUBE[i][j][0] = 0) but its degree of freedom is 0, then we have a conflict. Otherwise we can search for cells with a degree of freedom of 1. Such cells can be filled by just one possible number. Then we can look for cells with a degree of freedom of 2. In that case one of the two possibilities is pursued further while the other is pushed on a stack for possible back-tracking later on.
The stack itself is a three dimensional array where each level contains the current state of the puzzle at the time when a choice was made but with the alternative choice in place of the first one. We have to go back to these alternative choices whenever we run into a conflict. But, if the stack is empty and we still have a conflict then the puzzle cannot be solved.
Obviously, every time a new number is inserted in the puzzle the degrees of freedom must be updated. It is conceivable but highly unlikely that the degree of freedom is greater than 3 for every open position in the puzzle and yet the puzzle still has a unique solution. So, my program would deal with degree 3 at most which can
be treated similarly to degree 2.
If you can come up with a better approach I do not have a problem
Explanation / Answer
An easier way (but probably much, much slower) would be to use a simple DFS where each state is a complete game board. You can consider filling in a single square at a time, disregarding degrees of freedom and what not, and fill in that square, move on to the next, fill it in with a possible value, etc. etc. until one of the constraints are broken (duplicate in row, column, or square). At this point, backtrack to the previous state, set a different value other than the one that just broke the constraint, try again. Backtrack when there are no more values or the assignment is invalid, and you'll find your answer when everything is filled and no constraints are broken (I don't think its that slow, and it should be fairly straightforward to program)
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.