I have found a nice implementation of the Sudoku solver here:
http://www.heimetli....fiedsudoku.html
I understand most of the code since its quite self  explanatory but i dont get how this implementation manages the backtracking. Can someone point me to the write lines of code and explain.
I do get that in the solve() method, the author tries to find the right number for the current cell  it loops from 1 to 10. If it does find it it calls next() which provides next cell. Thats ok. But in my view, doing this way would keep going and going until stuck, but this somehow manages to go back and review the choices it made.
If someone can explain it would be awesome. THanks.
Sudoku solver  backtracking
Page 1 of 16 Replies  5366 Views  Last Post: 21 June 2011  06:55 AM
Replies To: Sudoku solver  backtracking
#2
Re: Sudoku solver  backtracking
Posted 20 June 2011  04:07 AM
Since there are specific options for each cell, you can recurse until you are wrong. However, since you are in a loop in the recursion, you can change the current number and try again. If that fail, you change the number and try again. You will eventually hit a solution where it no longer needs to go back. When this happens, you have found a solution.
#3
Re: Sudoku solver  backtracking
Posted 20 June 2011  06:52 AM
Since recursion is stack based, backtacking literally means going back to the previous recursive call. As Dogstopper explained, the current call, when it is found that it is pointless to continue, will be popped from the call stack, and you will return to the previous recursive call on the stack.
#4
Re: Sudoku solver  backtracking
Posted 20 June 2011  11:18 AM
Ok. That does actually make sense. Thanks a lot. Appraciate it.
#6
Re: Sudoku solver  backtracking
Posted 20 June 2011  06:16 PM
Just preaching for my parish
http://www.dreaminco...hebruteforce/
http://www.dreaminco...ruteforcegui/
http://www.dreaminco...hebruteforce/
http://www.dreaminco...ruteforcegui/
Page 1 of 1
