The New Sudoku Players' Forum

[Davy]

Hi Guys,

Since i am new to this forum, maybe a small introduction: i've only started doing sudokus since a few months ago. My girlfriend was doing them for quite some time already, and i used to laugh with her "sudoku-addiction". At some point i wanted to do another hobby-project (i am a programmer), and since she used an app which requires a periodic payment for new puzzles, i decided to write my own sudoku app.

Generating some sudoku puzzles ... how hard can it be, right?

Since then, i have picked up the sudoku addiction also. I am not as fast as my girlfriend yet, but i need to have my daily sudoku

And now the actual question i have: to be able to generate puzzles, i have up until now:
- a bruteforce way of generating complete solutions
- a bruteforce way to check if a puzzle has a single solution
- a solver that implements: naked/hidden singles, locked candidates and subsets. I have noticed that with only these techniques, i can already solve the majority of sudokus that most websites/apps generate. Next on the list to implement is x-wing and coloring.

I have also started on the generation of puzzles, and that works in the following way:
1: start from a full solution
2: randomly select a symmetric pair from the solution to remove (i read somewhere that puzzles are ideally symmetrical)
3: check if the puzzle can be solved, and if only one solution is possible
4: rate difficulty, and if difficulty was higher than any previously generated puzzle, store it as the most difficult puzzle
5: repeat from step 2

The actual code is more complex, because i actually start with 10 random pairs that i test in parallel, and at every step in the process i try 10 different combinations. So i am brute-force-searching many random combinations.

The effect of this is that i can easily find puzzles that involve singles and locked candidates, but my puzzles never require subsets. Which is quite odd. is there any trick or technique to use to generate more difficult puzzles? I would actually prefer to write a non-brute-force generator, but i wouldnt know where to start to be honest.

[JasonLion-Admin]

I generate puzzles in much the way you describe. The only significant differences are that I limit the maximum number of clues and I have various speed optimizations that you didn't mention. This is the typical approach, difficult puzzles are rare, so expect to need to create thousands to hundreds of thousands of puzzles to get a difficult one. That means it is really a question of speed, over complexity. The other approach is to incorporate a difficulty limited solver in the original puzzle creation process. This limits puzzles to a maximum difficulty but doesn't promise that difficult puzzles will occur any more frequently. This second approach can however provide a large speed improvement, which is critical when creating 16x16 puzzles for example.

[m_b_metcalf]

is there any trick or technique to use to generate more difficult puzzles?

Davy, two thoughts occur to me.
1) The method you describe does indeed produce aesthetically pleasing puzzles, but it leaves in redundant clues that decrease the difficulty. You could try generating without the symmetry constraint, as an exercise.

2) You could add a step 6.: if the first step in solving the candidate puzzle involves a single, repeat from 1.

HTH

Mike Metcalf

[Davy]

I've made good progress. I was hampered by a really silly bug in my grading code ... so i was actually generating fairly difficult puzzles but my grading didnt properly grade them I discovered sudokuwiki.org and am now comparing my grading against that one (very helpful website)

I also just started implementing more strategies, and of course that also helped a lot (obvious, i know). I have added xwing, ywing and xyzwing. I dont think i will implement much more strategies, because i dont want to loose track of my goal: implement a sudoku app in xamarin for learning purposes. I havent written a single line of code in for my app yet (and i can always keep adding strategies once the app works).

So yes. Soon, the google play store will contain one more sudoku app bringing the total to ... way too much

And yes, i have also started optimizing my code on a technical (using more efficient/faster datastructures) and logical level. Generating a puzzle that is graded "diabolical" by sudokuwiki is often done in less than 30 seconds.

Example: 100090085043002000000000000960000040001024500007000800000056000000080203800000104

[easudoku]

Try the dancing link algorithm: https://en.wikipedia.org/wiki/Sudoku_solving_algorithms, https://en.wikipedia.org/wiki/Knuth%27s_Algorithm_X and https://en.wikipedia.org/wiki/Dancing_Links. It is used by eaSudoku.com that could generate a pretty hard puzzle in a few hundred milliseconds.