UncleEbenezer wrote:Well, brute force can be seeded. In this case we can place a double-5 (and the 5 of 5-2) among those on the bottom row, which in turn tells us places it isn't. Double-zero is among the big patch of those, etc. And you can seed it with observations like the unique candidate for 3-0. But I haven't pursued it far: a few such observations still leave an awful lot of entropy to brute-force.
More interesting: how does a puzzle-setter ensure the solution is unique?
For many puzzles, the way I'd do it is not by setting a puzzle, then trying to determine whether it has a unique solution, but by picking a solution, then trying to find a puzzle to which it is the unique solution.
For instance, suppose I decide to treat a sudoku puzzle as 'gentle' if it can be solved entirely by spotting an empty cell which must be a particular digit because it's the only cell in its row (or column, or block) that can contain that digit, or because all eight other digits already appear at least once in the cell's row, column and/or block and that digit itself doesn't, filling the empty cell with that digit, and repeating. I can easily write a program to solve 'gentle' sudoku puzzles - it just needs an inner loop that runs through the 81 cells, checking whether each of them can be filled in by that rule, and an outer loop that keeps invoking that inner loop until either the entire board is filled or it reports that it cannot fill any of the remaining cells. If that results in the entire board being filled, I know that the puzzle has a unique solution that can be found using 'gentle' steps only and so it is a 'gentle' puzzle; if it reports that there are remaining empty cells but it cannot fill any of them, I know that it's not a 'gentle' sudoku puzzle (though whether that's because it has no solutions, multiple solutions or a unique solution that requires non-'gentle' logical steps to get to it may not be obvious). And that program won't take long: the outer loop is invoked a number of times that is at most the number of empty cells in the puzzle, and each invocation of the inner loop applies a fairly simple test a number of times that is also at most the number of empty cells in the puzzle. So the program does less than 81^2 = 6561 such tests, and each such test just involves checking up on the contents or possible values of 20 cells. Well programmed and run on a decent computer, such a program could decide whether hundreds of thousands of proposed sudoku puzzles are 'gentle' per second, quite possibly even millions.
Still, the chances of a sudoku puzzle grid filled with a random collection of blanks, 1s, 2s, 3s, 4s, 5s, 6s, 7s, 8s and 9s being a solvable sudoku puzzle are almost certainly absolutely tiny, and the chances of it having a unique solution that can be arrived at by using only 'gentle' steps smaller still. So even being able to check millions of such grids per second for being 'gentle' would probably take a
very long time to find a 'gentle' puzzle with a unique solution. Obviously a human puzzle setter could use their intelligence to increase those chances enormously, but using a human to generate just one possible puzzle is a great deal more expensive (in both monetary and elapsed-time terms) than using a computer to generate and check many millions, possibly even billions.
But turn that process of starting with a proposed puzzle and trying to check whether it has a unique solution that can be reached by a number of 'gentle' steps around: instead, start with a solved sudoku grid and try to find a sudoku puzzle from which it can be reached by a series of 'gentle' steps. One such 'puzzle' is the solved sudoku grid you start with - it is of course an extremely uninteresting one, requiring zero 'gentle' steps to solve. But we can make it more interesting (albeit
very marginally so) by emptying one of the filled cells. That empty cell can of course always be filled by a 'gentle' step, so we've arrived at a (still excessively) 'gentle' sudoku puzzle with the desired solution. And we can repeat that step of emptying a filled cell to get a slightly more interesting 'gentle' sudoku puzzle (because it takes two 'gentle' steps to solve rather than one) with the desired solution, then again to get one that takes three 'gentle' steps to solve, etc.
In the early stages of that process of emptying filled squares, it is easy to see that the filled cell we've just emptied is certain to be refillable with a 'gentle' step. It becomes harder to see that as more and more cells are emptied, and at some stage, it actually ceases to be true. That stage can arrive as early as when the fourth cell is emptied - e.g. if my desired solution contains two blocks fitting the following pattern:
+-----------+-----------+
| x x x | x x x |
| | |
| x x 1 | x 2 x |
| | |
| x x 2 | x 1 x |
+-----------+-----------+
and I happen to choose to empty the four cells containing red 1s and 2s, none of the emptied cells can be filled with a 'gentle' step, so the resulting puzzle is not a 'gentle' one - and indeed it doesn't even have a unique solution, because as well as having the desired solution we started with, it has another, namely that solution with the two red 1s replaced by 2s and the two red 2s replaced by 1s.
That issue can however be easily dealt with: start with a desired solution, and repeatedly empty a cell chosen at random, then check the resulting sudoku puzzle for being 'gentle' using the program described above, until that check fails, at which point you output the puzzle you had before that last cell-emptying. That will probably go a long way, though there is a chance it will output a
very unchallenging puzzle with just 3 empty cells. That process only needs to run the 'gentleness' checker a number of times equal to the number of empty cells in the puzzle you end up with for the successfully-emptied cells plus 1 for the unsuccessfully-emptied cell, so I'd be confident that it could generate thousands of 'gentle' puzzles per second, probably tens or even hundreds of thousands - though with no guarantees about their quality!
To improve the quality, don't just pick a random cell to empty at each stage. Instead, start by choosing a random order in which to try to empty the cells. At each stage, choose the first remaining cell in that order, empty it (keeping a record of the digit you removed from it) and test the resulting puzzle for being 'gentle'. If it is, leave the cell emptied; if not, replace the removed digit in it; either way, move on to the next cell in the random order. When you've finished dealing with all 81 cells in that way, you know that you've arrived at a 'gentle' puzzle with the desired solution that cannot be converted into any better such puzzle just by emptying one of its still-filled cells. There's a cost to doing that - you do 81 tests for 'gentleness' rather than the number of cells successfully emptied plus one, so I'd expect it to be a bit slower at producing 'gentle' sudoku puzzles - but I'd still expect it to be able to produce at least thousands of them per second...
Suppose that you instead want 'medium' sudoku puzzles, which you decide mean those that cannot be solved by 'gentle' steps alone, but that can be if you also do 'medium' steps - those might be steps of the form "if all the cells within a block that can hold digit N are in the same row (or column), then the six cells in that row (or column) that are outside that block cannot contain the digit N" and the similar "if all the cells within a row (or column) that can hold digit N are in the same block, then the six cells in that block that are outside that row (or column) cannot contain the digit N". 'Medium' sudoku puzzles with a desired solution can be generated by writing a similar 'medium' puzzle checker that tries to solve a sudoku puzzle using both 'medium' and 'gentle' steps rather than just using 'gentle' steps, and then following the same procedure as above: start with the desired solution, choose a random order in which to try to empty the cells, and try emptying each cell in turn in that order, using the 'medium' puzzle checker after each emptying to determine whether one still has a 'medium' puzzle with a unique solution - if not, back off from that emptying; otherwise, leave the cell empty; and either way, move on to the next cell in the order. When one gets to the end of that, one has a puzzle that can be solved with a sequence of 'gentle' and/or 'medium' steps and that cannot be reduced to a more challenging such puzzle by emptying any of the remaining filled cells. That means that it's a 'gentle' or 'medium' puzzle, so as a final check, run the 'gentle' puzzle checker on it and either separate out the 'gentle' puzzles if you want 'gentle' as well as 'medium' puzzles, or reject them if you only want 'medium' puzzles.
One can clearly extend that idea up to 'challenging', 'hard', etc, levels of puzzle where the solution can contain further types of step. And indeed, one can produce a 'full backtracking' puzzle checker quite easily, that simply picks an empty cell to try all possible digits for (preferably choosing one with the smallest number of possible digits for efficiency), and for each of those possible digits, fills it in, removes it as a possible digit for all other cells in the same row, column or block and then invokes itself recursively on the now more-constrained puzzle. One has to take a little bit of care about writing such a puzzle checker, basically to stop it exploring further possibilities once it's found enough solutions: if one just wants to know whether a puzzle has a unique solution, stop it with a "multiple solutions" result as soon as it finds a second solution rather than letting it proceed with its search to find all solutions (the reason why can be seen if one considers the completely unconstrained 'sudoku puzzle' which has all 81 cells blank:
https://en.wikipedia.org/wiki/Mathematics_of_Sudoku and/or
https://oeis.org/A107739 tell me that it has 6,670,903,752,021,072,936,960 solutions, so letting it find all of them might take inordinately long...). That allows one to produce 'ultimate' sudoku puzzles: ones that have a unique solution, but not one that's findable by using all of the types of solution steps that your lower levels of difficulty explore.
I'll also mention that this way of generating sudoku puzzles extends easily to the job of generating sudoku puzzles with a symmetrical pattern of empty and filled squares: rather than emptying cells one at a time, empty them a complete set of symmetrically placed cells at a time.
I'm not saying that every type of puzzle can be generated in that way, i.e. by starting with a solution as a "no work needed at all" puzzle, successively removing constraints from the puzzle until it no longer has just one solution, and finally backing off from the last constraint removal. But a lot can, and for those that can, it's generally much easier to start with a valid solution and use it to come up with a puzzle to which it's the unique solution, than it is to start with a puzzle, hope it turns out to have a unique solution, and repeat if that doesn't happen until it does.
Gengulphus