Hi, I am writing a Python Sudoku Solver which will solve the sudoku with sheer logic and no need for backtracking. There is one strategy I would like to implement, but I can't think of a way apart from lots of looping. In the image, see that all the candidate 7's in the first row are restricted to the 3rd grid only (1st row 7th and 8th columns). Since a 7 has to appear in the first row, we can safely eliminate 7's from other cells in the 3rd grid (in this case, only 2nd row 9th column), which in turn will expose a hidden 7 in 4th row last column. Now how do I implement this strategy? That is, for every row, for all candidates occurring in that row in different cells (3,7,8 and 9 for 1st row), if one candidate is restricted to one grid only, that candidate should be eliminated from other cells in that grid. Same goes for column. And similarly for a grid, if one particular candidate occurs in one row or one column only, then that candidate can be excluded from other cells in that row or column. I have a dictionary dic, where the key is the element's coordinates (I am implementing the matrix through numpy), and the value is its corresponding current list of candidates. If the cell has an established value, dic doesn't have that cell's coordinates as its key. For example dic[(0,2)] doesn't exist, as sudoku has a value of 6, while dic[(1,8)] = [1,3,7] (2nd row 8th column). Any idea how to implement this check without excessive looping?
This post has been edited by cupidvogel: 13 December 2011 - 11:51 PM
Well when I was in school there were two ways I did went about a solver, one was complicated and was in Assembly the other was much simpler. Depth First Search is your friend for these types of problems.
While BFS may be a little brutish, you can always use different heuristics to smarten up its decisions
The near entirety of sudoku solvers found on net use depth first search. That might be easier technically (indeed I myself designed one two or three years back in C), but the method completely takes the challenge out of it, and reduces a challenging problem to a brute force one. Hence I am trying to devise it such that it won't have any need for guessing, each step would be logical.
Well, the request was for a sudoku solver "with no need for backtracking". If this is the case then you might want to reconsider, depth first search inherently uses backtracking; with a fixed search tree, it may well have a benefit over breath-first search.
Lots of looping could be the way forward, if you can do it that way, although sudoku puzzles are often treated as NP-complete.
This post has been edited by Simown: 16 December 2011 - 05:00 PM