I recently stumbled upon a special Sudoku variant and am now struggling to effectively solve it programatically.
Consider the following initial 6x6 grid:
The red question mark is supposed to represent our secret digit. The secret digit behaves like a normal digit. That is, it has an actual value between
6, but this value isn't revealed to the player. In this game type, if we create a collision, the newly placed digit would become a neutral element that can be seen as a joker, not colliding with any other digit. For instance, if the secret digit actually was a
6 and we placed a
6 in its row, it would become a neutral element (and we would therewith also know what the secret digit is). We can generate a maximum of one neutral element (meaning that we can only create one collision), a second collision would render the grid unsolved.
Side note: Naturally, this interactive game type doesn't make sense to be printed on a piece of paper; it would e.g. require a client-server infrastructure for the secret not to be revealed to the player.
Since the secret digit follows the basic rules, we can deduce that it can't be a
4 in the example grid, but every other digit could be possible. We can also see that there isn't a unique solution; in fact, there usually are hundreds of possible solutions. In a 6x6 initial grid, there is always one secret digit and 6 digits that are pretty randomly placed in the grid (without colliding with each other). This means, the secret could be exposed right off the bet, but we will dismiss the trivial case since it's not fun at all :)
The most promising strategy would be to find out the secret digit as quickly as possible. That is, we would place digits in its row, column or box until either every possibility is exhausted, or we create a collision. As soon as we know what the secret is, we can solve the puzzle like a normal one (simply ignoring the neutral element if present).
I want to write an algorithm that finds the secret digit without creating an unsolvable board.
I wrote a rather blunt program which starts by identifying the fields in the secret's row, column and box with the fewest blockers. It then inserts digits in those fields, in an order from fewest blockers to most blockers until the secret can be deduced by collision or exhaustion. In the example grid, it would do something like this:
The blue digits would be placed in ascending order (starting with
My current alogrithm produces an unsolvable board about 20% of the time, which is unacceptable to me. And that's why I'm asking the question:
What would be a smarter approach, minimizing or even eliminating the possibility of creating an unsolvable puzzle?
P.S.: I appreciate every type of answer; theoretical prose, pseudo-code or real code in a popular language is all fine, I simply want to get the gist of which fields/digits to select for the starting strategy.