this post was submitted on 18 Aug 2024
54 points (96.6% liked)
Programming
17534 readers
319 users here now
Welcome to the main community in programming.dev! Feel free to post anything relating to programming here!
Cross posting is strongly encouraged in the instance. If you feel your post or another person's post makes sense in another community cross post into it.
Hope you enjoy the instance!
Rules
Rules
- Follow the programming.dev instance rules
- Keep content related to programming in some way
- If you're posting long videos try to add in some form of tldr for those who don't want to watch videos
Wormhole
Follow the wormhole through a path of communities !webdev@programming.dev
founded 2 years ago
MODERATORS
you are viewing a single comment's thread
view the rest of the comments
view the rest of the comments
I did this as my second larger project while learning programming. My solver was at the level of "Skip on invalid Sudokus" and I stopped the project when my generator was able to generate non-unique puzzles.
The thing is, a brute-force algorithm doesn't care whether your puzzle is unique, it will find a solution.
I guess, I would have had to also check whether all cells contain only one number to verify a unique solution, but if I remember correctly, my generator didn't even backtrack. I think, I just threw in random numbers that matched the constraints...
If you move past the 'brute force' method of solving into the 'constraints' level, it's fairly easy to check whether there are multiple possible valid solutions. Using a programming language with a good sets implementation (Python!) makes this easy - for each cell, generate a set of all the values that could possibly go there. If there's only one, fill it in and remove that value from all the sets in the same row/column/block. If there's no cells left that only take a unique value, choose the cell with the fewest possibilities and evaluate all of them, recursively. Even a fairly dumb implementation will do the whole problem space in milliseconds. This is a very easy problem to parallelize, too, but it's hardly worth it for 9x9 sodokus - maybe if you're generating 16x16 or 25x25 'alphabet' puzzles, but you'll quickly generate problems beyond the ability of humans to solve.
The method in the article for generating 'difficult' puzzles seems mighty inefficient to me - generate a valid solution, and then randomly remove numbers until the puzzle is no longer 'unique'. That's a very calculation-heavy way of doing it, need to evaluate the whole puzzle at every step. It must be the case that a 'unique' sodoku has at least 8 unique numbers in the starting puzzle, because otherwise there will be at least two solutions, with the missing numbers swapped over. Preferring to remove numbers equal to values that you've already removed ought to get you to a hard puzzle faster?