Generating sudokus for fun and no profit
Tom Nick created a free Sudoku application that generates puzzles based on human perception of difficulty, using advanced algorithms like CSP and Arc Consistency to improve solving efficiency and user experience.
Read original article
Tom Nick developed a free and open-source Sudoku application, sudoku.tn1ck.com, to provide a better experience for players, particularly his grandmother. The project involved creating a Sudoku generator that assesses difficulty based on human perception. The process begins with solving a Sudoku, which is essential for generating one. Various algorithms were explored, starting with a brute force method and advancing to more sophisticated techniques like Constraint Satisfaction Problems (CSP) and Arc Consistency.
The brute force approach, while simple, is inefficient. Improvements were made by implementing heuristics such as the Minimum Remaining Value, which selects cells with fewer possibilities, significantly reducing the number of iterations needed to solve difficult puzzles. The Arc Consistency method further refines the process by ensuring that the domains of variables (Sudoku cells) remain consistent with the constraints of the game.
To rate the difficulty of generated Sudokus, Nick utilized iteration counts from different solving strategies, comparing them to established difficulty levels from existing Sudoku databases. The analysis revealed a correlation between iteration counts and perceived difficulty, although it raised questions about the accuracy of these measures for human solvers.
The Sudoku generation process involves filling an empty grid with random numbers while ensuring uniqueness and solvability. The algorithm can adjust difficulty by adding or removing numbers, although generating highly difficult puzzles can be time-consuming due to the constraints involved. Overall, the project combines algorithmic innovation with a personal touch, aiming to enhance the Sudoku experience for users.
Related
Chasing a Bug in a SAT Solver
Adolfo Ochagavía and Prefix.dev swiftly resolved a bug in the SAT-based dependency solver, resolvo, with community input. The incident emphasizes open-source collaboration and potential debugging tool enhancements for software quality.
Solving puzzles faster than humanly possible
The Opus Magnum challenge tasks players with automating puzzle-solving to optimize Cost, Cycles, and Area metrics. Participants submit solutions for evaluation, exploring automated vs. human strategies, hybrid approaches, scoring systems, mods, and bots.
The first 10k games at bgammon.org, an open source online backgammon service
The milestone of 10,000 games on bgammon.org is celebrated, with community contributions and developments noted. Optimization efforts enhance speed and user experience, including the introduction of the Universal Backgammon Engine Interface (UBEI).
Getting the World Record in Hatetris (2022)
David and Felipe set a world record in HATETRIS, a tough Tetris version. They used Rust, MCTS, and AlphaZero concepts to enhance gameplay, achieving a score of 66 points in 2021.
Exercise: Minesweeper in 100 lines of Ruby
Radan Skorić implemented Minesweeper in 100 lines of Ruby code, emphasizing code reduction while maintaining readability. The implementation covers board generation, gameplay logic using Ruby features, and hints at future multiplayer functionality.
- Users commend the application's user-friendly design and interactive features.
- Several commenters share their experiences with other Sudoku games and generators, highlighting different approaches to puzzle difficulty.
- There is interest in exploring advanced algorithms and techniques for generating and solving Sudoku puzzles.
- Some users point out issues, such as broken links to resources and the desire for more puzzle variants.
- Overall, the community expresses enthusiasm for the project and offers constructive feedback.
23 commentsThe numbers themselves are all interchangeable, so you have 9! combinations: 362,880.
Columns 1-to-3 are all interchangeable, as are 4-to-6, and 7-to-9. On top of this, these blocks of columns (1-to-3, 4-to-6, 7-to-9) are all interchangeable. Read about wreath products in group theory to know more. Each of the above symmetries are 3!, combined to yield 3! * 3! = 36 combinations. As well as the columns though, the rows have the same property, so those can be combined too: 36 * 36 = 1,296.
Finally, there are the symmetries of a square. Combining all rotations and flips yields a further 8.
In total, sudoku has 3,762,339,840 symmetries. Owing to the starting state of the sudoku puzzle being incomplete, the orbit of the set of points (more group theory) will be smaller than 3 billion, but it provides an efficient method of recreating many more puzzles with the same property. In this case, human complexity.
So if you have a puzzle that can be solved using only techniques that interested people can come up with fairly readily/intuitively and apply without a lot of ceremony, then that would be, perhaps, very easy. The more advanced techniques (for humans) needed to solve the puzzle, the harder it would be rated.
You can also feed these techniques into the generation so that you can guide the difficulty as it's being generated (the way I did it, I found it would still fall into puzzles that are easier than the target, or get stuck on puzzles that are too hard, but applying adjustments to backtracking and forward progress based on heuristics observed in "stuck" scenarios seemed to do the trick.
> Once upon a time I decided to create a complete sudoku application as my grandma wanted to play some sudokus on her computer and I wasn't satisfied with the free offers available.
I liked the rest too and the website as well, especially the user friendly UX - the "applets" can be paused, the website has all kinds of display options, there are keyboard shortcuts and support for arrow keys.
My dream would be a "made for grandma" embeddable badge - and websites like this becoming a trend in 2024.
Many years ago I wrote a Sudoku generator in C++ that was based on Knuth’s “dancing links” algorithm. It then analyzed the generated puzzle in terms of what techniques were necessary to solve it, and ranked them accordingly.
Perhaps there is still something useful in there: https://github.com/stlab/adobe_source_libraries/tree/main/te...
I am a broken record on posts that mention sudoku in bringing in Knuth's treatment of it. He has a ton of really fun exercises on the game in the latest volume. Perhaps the most fun are the puzzles that have a single solution, but do not have enough information to place a single piece without ambiguity.
While I like the idea of using ARC3 to grade sudoku, I much prefer the approach developed by Andrew C. Stuart in [0], where they rely on the human techniques* needed to solve the sudoku. Indeed, Sudoku are small enough that a reasonable greedy algorithm is enough to solve them quasi instantly on modern hardware.
* techniques to solve the sudoku that can be applied by an human (as opposed to a computer).
[0]: https://www.sudokuwiki.org/Sudoku_Creation_and_Grading.pdf
[0] https://www.conceptispuzzles.com/index.aspx?uri=puzzle/euid/...
[1] https://www.conceptispuzzles.com/index.aspx?uri=puzzle/sudok...
[2] https://www.conceptispuzzles.com/index.aspx?uri=mobile/10001...
[3] https://www.conceptispuzzles.com/index.aspx?uri=mobile/10001...
https://www.chiark.greenend.org.uk/~sgtatham/puzzles/js/solo...
https://brainium.com/games/sudoku/
It has selectable difficulty and a "hint" mode that teaches you how to solve even the hardest sudokus without any backtracking search at all.
I got at least as far as thinking through something like your list of algorithms here. But I could help but imaging that there must also be even-more efficient or interestingly exotic solutions out there.
Like something amusing as a rainbow-table type approach where you calculate all the possible soduko boards in advance, then (somehow?) convert any given puzzle into just an index lookup of a matching solution. So like (perhaps a lot of) brute force up front, but O(1) in execution?
Related
Chasing a Bug in a SAT Solver
Adolfo Ochagavía and Prefix.dev swiftly resolved a bug in the SAT-based dependency solver, resolvo, with community input. The incident emphasizes open-source collaboration and potential debugging tool enhancements for software quality.
Solving puzzles faster than humanly possible
The Opus Magnum challenge tasks players with automating puzzle-solving to optimize Cost, Cycles, and Area metrics. Participants submit solutions for evaluation, exploring automated vs. human strategies, hybrid approaches, scoring systems, mods, and bots.
The first 10k games at bgammon.org, an open source online backgammon service
The milestone of 10,000 games on bgammon.org is celebrated, with community contributions and developments noted. Optimization efforts enhance speed and user experience, including the introduction of the Universal Backgammon Engine Interface (UBEI).
Getting the World Record in Hatetris (2022)
David and Felipe set a world record in HATETRIS, a tough Tetris version. They used Rust, MCTS, and AlphaZero concepts to enhance gameplay, achieving a score of 66 points in 2021.
Exercise: Minesweeper in 100 lines of Ruby
Radan Skorić implemented Minesweeper in 100 lines of Ruby code, emphasizing code reduction while maintaining readability. The implementation covers board generation, gameplay logic using Ruby features, and hints at future multiplayer functionality.