I'm trying to create a Sudoku puzzle (programatically, if that matters). Here's how I do it.
STEP 1: Creating an initial set, with unique solution:
123456789 456789123 789123456 ...etc...
STEP 2: Mixing it up a bit, according to applicable rules, like swapping numbers
STEP 3: This is where I need you help. This is the part where I should be emptying some fields, to turn solution into a puzzle.
Question - is there any algorithm, or any approach to this, except that of trying to empty a random field, and then testing through way too much iterations if puzzle still has a unique solution?
Any help much appreciated (textual explanation, pseudo-code, or whatever you have to offer)
I encountered this problem when I was working on a sudoku puzzle generator that also estimated the difficulty of the puzzles it generated. In general, it is often hard to prove that a Sudoku puzzle has more than one solution unless you just guess values and show that two or more solutions work. The way I approached the problem was to start with an empty puzzle and ADD one number at a time in a random fashion to the initial puzzle, and then calculate with my solver which values were allowed or disallowed at each position in the puzzle, and then just keep choosing one allowed value for a position to add to my initial puzzle until my solver determined that the solution was unique. Technically unless your solver is perfect, this could lead to a contradiction where you think one value is allowed even though it's not, and you don't figure it out until later. However, in my empirical studies it seems like the probability of this happening is very low, at least if you added values in a random fashion the way I did. I.e. you arrive at a unique solution almost always, and get a good variety of puzzles. When I picked a value for a position and it led to a contradiction, my solver almost always found it immediately, so that that value could be ruled out. I always chose a position that had the maximum number of possible allowed values left, and then chose a value uniformly at random from the possible values for that position.