Recursive Solution To Sudoku Generator
Solution 1:
In the Java code: I'll translate it to psuedocode:
forall z values:
If for current (x,y), the number 'z'is legal then:
insert z to current (x,y)
if finished
hooray!
else
go to next square
elsetrynext number
But what if you can't put any number there as it ends up being illegal (aka a board where you can't insert any number in a specific square)?
You don't address that. What you need to do is implement it via backtracking:
forall z values:
If forcurrent (x,y) the number 'z'is legal then:
insert z tocurrent (x,y)
go to next(x,y)
try to complete the board //recursivecall
if you completed the board //== the resultof the recursion is legal
return the completed board
If all z values have been attempted
return "cannot complete board"
increment z, try again withcurrent (x,y)
Solution 2:
Java:
You should initialize your
board
variable, you may want to initialize it in a constructor:publicclassSudokuGenerator { publicstaticfinalint BOARD_WIDTH = 9; publicstaticfinalint BOARD_HEIGHT = 9; publicSudokuGenerator(){ board = newint[BOARD_WIDTH][BOARD_HEIGHT]; } }
I believe that your loop iterator in the function nextBoard it is wrong:
for(int i=1;i<10;i++){ ... }
I think that you want to iterate from 0 to 9.
In the function nextBoard, you also need to check the variable:
int[] toCheck = {1,2,3,4,5,6,7,8,9};
You get an
java.lang.ArrayIndexOutOfBoundsException
, you should initialize it from 0 to 8, otherwise you try to access the board row number 9 and you get a runtime error.Another problem that you need to solve is that x is being set to nine in
nextBoard()
function. Call the functionnextBoard(int x, int y)
"manually" with these parameteres:nextBoard(7,3)
and you will understand why x is being set to nine. Check specifically the values of the variablenextX
.
I believe it will really help you if you use a debugger to check this kind of errors, here you have a nice tutorial with a video explanation(in case your are using the Eclipse IDE).
Hope it helps.
Solution 3:
Java:
Your loop iterator in nextBoard range from 1 to 9. I don't think you meant that. Same in the function legalMove.... initialize cornerX and cornerY to 0.
Solution 4:
interesting question, I just noticed this one bug in the Java code: isn't the call to Collection.shuffle() useless since the toCheck array will remain unmodifed (unshuffled) after this call? Here is my quick fix (and I'm sure there are more clever ways to do it):
List<Integer> lst = Arrays.asList(1, 2, 3, 4, 5, 6, 7, 8, 9);
Collections.shuffle(lst);
for (int i=0; i<lst.size(); i++)
toCheck[i] = lst.get(i);
Solution 5:
In Java array indexes are zero-based. In nextBoard
you loop over 1..9
for i
and use it as an index into toCheck
which will skip the first element at index 0
and go past the end of the array. This will throw ArrayIndexOutOfBoundsException
if the line containing toCheck[i]
is reached with i
equal to 9
.
Post a Comment for "Recursive Solution To Sudoku Generator"