3 Replies - 2345 Views - Last Post: 05 December 2011 - 06:38 PM

#1 cupidvogel  Icon User is offline

  • D.I.C Addict

Reputation: 31
  • View blog
  • Posts: 593
  • Joined: 25-November 10

Is backtacking a must in Sudoku solving algorithm?

Posted 05 December 2011 - 12:32 AM

While solving Sudoku, including the toughest ones, is it possible to device a set of algorithms so as to eliminate the need of backtracking altogether? That is, suppose there is a function which includes like say 15 algorithms to find a cell where only one number is allowed. Is it possible that this function always fills at least one cell, so that if initially the Sudoku has 55 cells to fill, the function will be invoked at most 55 times, that is the function doesn't need to be a recursive one (backtracking calls for it to be recursive)?

This post has been edited by cupidvogel: 05 December 2011 - 12:40 AM


Is This A Good Question/Topic? 3
  • +

Replies To: Is backtacking a must in Sudoku solving algorithm?

#2 Motoma  Icon User is offline

  • D.I.C Addict
  • member icon

Reputation: 452
  • View blog
  • Posts: 797
  • Joined: 08-June 10

Re: Is backtacking a must in Sudoku solving algorithm?

Posted 05 December 2011 - 07:10 AM

This is a fantastic question, but one which I am not well suited to answer. The short answer is no, the sudoku problem is traditionally thought to falls into the class of NP-complete which are verifiable in polynomial time, but has no efficient way of devising a solution.

I'm moving this to the Software Development > Computer Science forum, as this is an algorithm related problem, not a Python one.
Was This Post Helpful? 2
  • +
  • -

#3 xclite  Icon User is offline

  • LIKE A BOSS
  • member icon


Reputation: 916
  • View blog
  • Posts: 3,210
  • Joined: 12-May 09

Re: Is backtacking a must in Sudoku solving algorithm?

Posted 05 December 2011 - 09:35 AM

Edit: Deleting a bunch of stuff because of my wall of text, found this:

http://www.instructa...even-thinking!/

The author of that "instructable" claims you never need to guess in Sudoku, because there's always a way to deduce which number belongs in a box based on either being the only box where such a number is permitted. If one were to copy his algorithm, backtracking may not be required.

My current solver DOES use backtracking for ambiguous puzzles, although I may give his a try for comparison's sake.

This post has been edited by xclite: 05 December 2011 - 09:50 AM

Was This Post Helpful? 1
  • +
  • -

#4 Karel-Lodewijk  Icon User is offline

  • D.I.C Addict
  • member icon

Reputation: 452
  • View blog
  • Posts: 857
  • Joined: 17-March 11

Re: Is backtacking a must in Sudoku solving algorithm?

Posted 05 December 2011 - 06:38 PM

Depends on what you understand under sudoku. I the sudoku has a unique solution, the algorithm in the link works. Basically all sudokus you find in magazines have a unique solution so people don't get stuck.

If your sudoku doesn't have a unique solution then your algorithm will have to guess at some point. If there is a greedy algorithm that results in an accurate guess without actually solving the sudoku then I don't know it and if it is indeed np-complete, then some kind of graph traversal algorithm is required a simple backtracking algorithm is an obvious choice.

This post has been edited by Karel-Lodewijk: 05 December 2011 - 06:39 PM

Was This Post Helpful? 1
  • +
  • -

Page 1 of 1