Various Questions

Peter40 · Posted: Thu Jul 28, 2005 9:47 pm Post subject: Various Questions

I wrote a program as many have to solve a 9x9 sudoku and found that for some difficult sudokus I could not avoid a guess and backtrack strategy. A friend said that was cheating and I should enhance the program to make it solve all sudokus by applying logic only with no guessing. I went back and discovered other steps I could program in but there remain puzzles I have to guess. Even if I find more enhancements and solve these I will not be confident that it works in every case. So

1, Is there a proof which shows that either all 9x9 sudokus can be solved without trial and error or that there exists a class of sudokus that can not be solved by logic alone.

I soon found that with the ability to guess and backtrack you can use the solver to generate valid sudoku grids with an initial seed or no seed at all. What I have not discovered is how to strip back a complete grid to the point that there is only one possible solution, where the removal of just one more guide would allow more than one solution. Also I have not discovered how to tell whether a given set of guide cells would yield and easy or a difficult puzzle, and therefore am a long way from understanding how to build a puzzle of given difficulty. So

2, How can you determine the mininum number of guides needed.
3, How can you set out to create a puzzle in a given range of difficulty.

antony · Posted: Fri Jul 29, 2005 3:02 am Post subject:

If I understand tilps' results well (high score "1.7.3"), there are few, if any, grids that can't be solved with simple rules + forcing chains, which seems to be considered as logic, not T&E.

If you get a filled grid, stripping it is straightforward, as long as your solver is able to tell you if a solution is unique. (If your backtracking solver is recursive, continue the search after the first solution was found.)

tilps · Posted: Fri Jul 29, 2005 9:35 am Post subject:

dukuso · Posted: Fri Jul 29, 2005 1:13 pm Post subject:

there should be a better method to generate hard sudokus than
just filtering random sudokus.

Has anyone tried hill-climbing ?
This is assuming that sudokus which look similar are also similar
in their hardness-rating. I don't know whether this is true.

We could also improve by considering the statistics
of hard sudokus, their cycle-structure, the equivalence
classes of their chunks.

We could fix a complete grid which looks promising and only consider
subsets of its clues.