2

I recently stumbled upon a special Sudoku variant and am now struggling to effectively solve it programatically.

Consider the following initial 6x6 grid:
enter image description here

The rules

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 1 and 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.

Analysis

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 :)

Solving strategy

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).

The problem

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:

enter image description here
The blue digits would be placed in ascending order (starting with 1). 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.

  • It seems you are simply placing the digits onto the board in a manner that does not immediately violate any constraints. Also, your algorithm for creating the initial field might be creating unsolvable games. Why don't you modify existing working algorithms to consider your hidden fields? After all, Sudoku is a pretty well-studied game. It seems that in the case of a single hidden field, you'd necessarily end up with the same solution as if that field were free! – amon Dec 28 '14 at 16:24
  • @amon 1) Correct, my starting strategy is currently not much better than just arbitraily putting legal digits around the secret digit. That's what I want to improve. 2) The algorithm for creating the board wasn't supposed to be part of the question and can be assumed to flawlessly create a board with multiple solutions. 3) What working algorithms do you have in mind for this specific Sudoku variant, and especially for carefully finding the secret digit? – MCL Dec 28 '14 at 16:36
  • 4) The secret digit is one specific digit that just isn't initially revealed to the player. That is, it does influence the solution, it can't be simply ignored. – MCL Dec 28 '14 at 16:37
  • How is the ? different from an empty field? It also represents a value from 1 to 6 that isn't revealed to the player, and that needs to be found. – Florian F Dec 28 '14 at 21:38
  • 1
    So you try to put a digit on the same line, and either it works or it says there is a collision, which reveals the value? And you get penalty for creating a collision? – Florian F Dec 28 '14 at 21:50
1

I don't think i understood the WildCard concept to well. Maybe some images of sample configurations on the board would help?

There are already well established Sudoku Solving Algorithms that exist. Some like

Backtracking.

Keep placing numbers one by one until you reach an unsolvable position, then retrace your last step and continue.

Constraint Solving

Each cell has many constraint because of the row, the column and the group of cells. Map out all the constraints of each cell and begin solving the cell where the answer is unique for that contraint. Keep udating the other contraints as numbers are added.

You can find more here

Since there are well established algorithms, one strategy to tackle this problem is to modify the above strategies to include this. Eg: this cell would impose no constraint in its rows, columns and the bigger cell.

I will try to edit with pseudo code for a constraint based solution if I have time.

  • Solving a normal Sudoku isn't a problem. My question is about which fields to choose in order to find out what the hidden/secret digit is. Imagine an online Sudoku game where you're presented with the example board above. You can place digits anywhere on the free fields of the board. If you place a digit that collides with the secret digit, a neutral element (you could also call it a 0) will be placed instead. If that makes it clearer, I will incorporate this in my question. – MCL Dec 28 '14 at 17:18
  • The main problem is that you can't calculate a solution before knowing what the secret digit is. Which means, you have to place digits in its row, column or box until you know what digit exactly it is. Only then you can start backtracking for instance. – MCL Dec 28 '14 at 17:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.