4
$\begingroup$

I'm talking about the vanilla sudoku game, with 9x9 grids equally split into 9 regions.

I've tried a few approaches to estimate the probability that a specific number is in a specific location, but I can't seem to find the right pattern about it.

Suppose I have this (partial) grid:

Partial sudoku grid

What kind of calculation or method would help me find the probabilities of having a 8 in any of the free locations?

Intuitively, I'd think there is a 50% chance of there being an 8 in any of the free locations of the two leftmost squares, but I'm not too sure what to think anymore with that rightmost almost-empty square.

(I do realize that this specific example has multiple solutions; I couldn't come up with one that had just one solution but wasn't trivially easy to solve.)


EDIT I also realize that since 'good' sudokus only have one solution, as Thomas Andrews noted, the probability that a certain location contains an 8 is either 0 or 1.

Therefore, let's assume that I can determine the value of a square with 100% certainty if and only if it can be found through the naked single or hidden single techniques (that is, the number is either the only possible option for a square, or there is no other place where the number can be). Those two techniques are only enough to solve the most basic sudokus.

If I chose to observe the grid with those two techniques only, even though I'd get stuck at some state, it would still be possible to enumerate several successor states that would seem legal at first, and very obviously, many of them would have overlapping results. For instance, taking the partial grid above, several successor states would have an 8 in the second square. And by counting every single occurrence of the 8 value in the second square, divided by the number of seemingly legal successor states, I would get what I call the probability of an 8 being there.

The problem is that, even for a computer, counting those is sloooow. So I am wondering what kind of maths I could use the get the right answer, without resorting to the manual count, just knowing the constraints.

$\endgroup$
  • 2
    $\begingroup$ Given that a Sudoku problem has only one solution by definition, the probability that a specific square ought to have an '8' is always either zero or one. You'll need a more precise formulation of what probability you are trying to find for it to be anything other than 0 or 1. $\endgroup$ – Thomas Andrews Jan 18 '12 at 22:07
  • $\begingroup$ There are algorithms available you should study those first; they might assist in your formulation the question more precisely or completely answer your query. $\endgroup$ – Adam Jan 18 '12 at 22:29
  • $\begingroup$ @ThomasAndrews, I've updated my question to reflect better my line of thought. $\endgroup$ – zneak Jan 19 '12 at 0:05
3
$\begingroup$

I'm guessing that the probability you're looking for is "given all possible sudoku puzzles that are compatible with this row, what percentage of them have an 8 in this single location."

For the puzzle you've given, I would tend to 0.5 to the four locations in the left and center square (these are obviously correlated), and 1/3 to the three middle row locations in the right most 3x3 square (which are again correlated).

But to figure out these numbers exactly would require a lot of work.

| cite | improve this answer | |
$\endgroup$

Your Answer

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