# Sudoku solver - backtracking

Page 1 of 1

## 6 Replies - 6105 Views - Last Post: 21 June 2011 - 06:55 AMRate Topic: //<![CDATA[ rating = new ipb.rating( 'topic_rate_', { url: 'https://www.dreamincode.net/forums/index.php?app=forums&module=ajax&section=topics&do=rateTopic&t=236337&amp;s=395b3b74db3633189e4731f6278b5093&md5check=' + ipb.vars['secure_hash'], cur_rating: 0, rated: 0, allow_rate: 0, multi_rate: 1, show_rate_text: true } ); //]]>

### #1 darek9576

• D.I.C Lover

Reputation: 203
• Posts: 1,731
• Joined: 13-March 10

# Sudoku solver - backtracking

Posted 20 June 2011 - 01:59 AM

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.

Is This A Good Question/Topic? 0

## Replies To: Sudoku solver - backtracking

### #2 Dogstopper

Reputation: 2965
• Posts: 11,222
• Joined: 15-July 08

## 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 macosxnerd101

• Games, Graphs, and Auctions

Reputation: 12318
• Posts: 45,417
• Joined: 27-December 08

## 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 darek9576

• D.I.C Lover

Reputation: 203
• Posts: 1,731
• Joined: 13-March 10

## Re: Sudoku solver - backtracking

Posted 20 June 2011 - 11:18 AM

Ok. That does actually make sense. Thanks a lot. Appraciate it.

### #5 macosxnerd101

• Games, Graphs, and Auctions

Reputation: 12318
• Posts: 45,417
• Joined: 27-December 08

## Re: Sudoku solver - backtracking

Posted 20 June 2011 - 11:25 AM

### #6 pbl

• There is nothing you can't do with a JTable

Reputation: 8378
• Posts: 31,956
• Joined: 06-March 08

## 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/

### #7 darek9576

• D.I.C Lover

Reputation: 203
• Posts: 1,731
• Joined: 13-March 10

## Re: Sudoku solver - backtracking

Posted 21 June 2011 - 06:55 AM

Sweet. Thank you.