6 Replies - 4500 Views - Last Post: 21 June 2011 - 06:55 AM Rate Topic: -----

#1 darek9576  Icon User is offline

  • D.I.C Lover

Reputation: 198
  • Posts: 1,688
  • 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  Icon User is offline

  • The Ninjaducky
  • member icon



Reputation: 2871
  • View blog
  • Posts: 11,026
  • 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.
Was This Post Helpful? 1
  • +
  • -

#3 macosxnerd101  Icon User is offline

  • Self-Trained Economist
  • member icon




Reputation: 10486
  • View blog
  • Posts: 38,858
  • 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.
Was This Post Helpful? 1
  • +
  • -

#4 darek9576  Icon User is offline

  • D.I.C Lover

Reputation: 198
  • Posts: 1,688
  • 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.
Was This Post Helpful? 0
  • +
  • -

#5 macosxnerd101  Icon User is offline

  • Self-Trained Economist
  • member icon




Reputation: 10486
  • View blog
  • Posts: 38,858
  • Joined: 27-December 08

Re: Sudoku solver - backtracking

Posted 20 June 2011 - 11:25 AM

Glad I could help! :)
Was This Post Helpful? 0
  • +
  • -

#6 pbl  Icon User is offline

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

Reputation: 8329
  • View blog
  • Posts: 31,857
  • 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/
Was This Post Helpful? 2
  • +
  • -

#7 darek9576  Icon User is offline

  • D.I.C Lover

Reputation: 198
  • Posts: 1,688
  • Joined: 13-March 10

Re: Sudoku solver - backtracking

Posted 21 June 2011 - 06:55 AM

Sweet. Thank you.
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1