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 1## 6 Replies - 5768 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...he-brute-force/

http://www.dreaminco...rute-force-gui/

http://www.dreaminco...he-brute-force/

http://www.dreaminco...rute-force-gui/

Page 1 of 1