This post has been edited by cupidvogel: 05 December 2011  12:40 AM
3 Replies  2256 Views  Last Post: 05 December 2011  06:38 PM
#1
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)?
Replies To: Is backtacking a must in Sudoku solving algorithm?
#2
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 NPcomplete 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.
I'm moving this to the Software Development > Computer Science forum, as this is an algorithm related problem, not a Python one.
#3
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...eventhinking!/
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.
http://www.instructa...eventhinking!/
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
#4
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 npcomplete, then some kind of graph traversal algorithm is required a simple backtracking algorithm is an obvious choice.
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 npcomplete, then some kind of graph traversal algorithm is required a simple backtracking algorithm is an obvious choice.
This post has been edited by KarelLodewijk: 05 December 2011  06:39 PM
Page 1 of 1
