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?
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?