
View previous topic :: View next topic 
Author 
Message 
 Peter40
 Joined: 28 Jul 2005  Posts: 1  :   Items 

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. 

Back to top 


 antony
 Joined: 22 Jul 2005  Posts: 13  :   Items 

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.)
Code:  For every hint (or pair of hints), in a random order,
Remove it.
Solve.
If solution is not unique anymore, put the hint(s) back.

To create a grid of given difficulty, create many grids and rate them with a humanlike solver, until you have the one. Some patterns seem to result in harder puzzles, though not necessarily.
Last edited by antony on Fri Jul 29, 2005 2:34 pm; edited 1 time in total 

Back to top 


 tilps
 Joined: 19 Jun 2005  Posts: 44  :   Items 

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


antony wrote:  If I understand tilps' results well ... 
From ~3million sudoku i've generated so far for the 3x3 size, all have had a 'constructive logic proof' for every move required to solve them. Many of them would have been easier to solve using trial and error I am sure. 

Back to top 


 dukuso
 Joined: 14 Jul 2005  Posts: 424  :  Location: germany  Items 

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 hillclimbing ?
This is assuming that sudokus which look similar are also similar
in their hardnessrating. I don't know whether this is true.
We could also improve by considering the statistics
of hard sudokus, their cyclestructure, the equivalence
classes of their chunks.
We could fix a complete grid which looks promising and only consider
subsets of its clues. 

Back to top 




You cannot post new topics in this forum You cannot reply to topics in this forum You cannot edit your posts in this forum You cannot delete your posts in this forum You cannot vote in polls in this forum

Powered by phpBB © 2001, 2005 phpBB Group
Igloo Theme Version 1.0 :: Created By: Andrew Charron
