StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

POSudoku solver in Java, using backtracking and recursion
text
Body
copied!<p>I am programming a Sudoku solver in Java for a 9x9 grid.</p> <p>I have methods for:</p> <ul> <li><p>printing the grid</p></li> <li><p>initializing the board with given values</p></li> <li><p>testing for conflicts (if same number is in same line or 3x3 sub-grid)</p></li> <li><p>a method to place the digits, one by one, which requires the most work.</p></li> </ul> <p>Before I go into detail with that method, keep in mind that I have to use recursion to solve it, as well as backtracking (watch the applet here as an example <a href="http://www.heimetli.ch/ffh/simplifiedsudoku.html" rel="noreferrer">http://www.heimetli.ch/ffh/simplifiedsudoku.html</a> )</p> <p>Also, I am solving this Sudoku by moving vertically downwards, starting from the top left, through the first column, and then through the second column, etc.</p> <p>So far, I have the following:</p> <pre><code>public boolean placeNumber(int column){ if (column == SUDOKU_SIZE){ // we have went through all the columns, game is over return true; } else { int row=0; //takes you to the top of the row each time while (row < SUDOKU_SIZE) loops through the column downwards, one by one { if (puzzle[row][column]==0){ //skips any entries already in there (the given values) puzzle[row][column]=1; //starts with one while(conflictsTest(row,column)){ //conflictsTest is the method I wrote, which checks if the given parameters are in conflict with another number puzzle[row][column] += 1; } //BACK TRACKING placeNumber(column); //recursive call } else{ row++; // row already has a number given, so skip it } } column++; // move on to second column placeNumber(column); } return false; // no solutions to this puzzle } </code></pre> <p>Where I labeled BACKTRACKING is where I believe the remainder of my code needs to go.</p> <p>I thought up of something along the lines of:</p> <ul> <li>if the value is 10, set that value back to zero, go back a row, and increment that value by 1</li> </ul> <p>That backtracking 'strategy' doesn't exactly work for several reasons:</p> <ol> <li><p>what if the previous row, was a given value (aka I'm not supposed to increment it or touch it, but instead, go back to the last value that I placed there)</p></li> <li><p>what if the previous value was a 9. and if I incremented that by 1, now we're at 10, which won't work.</p></li> </ol> <p>Can someone please help me out?</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload