Sudoku brute force solve?

Question

I am writing a small program that solves Sudoku puzzles. It uses brute force to (i.e. fills table with random numbers, checks if solved, repeat).

Can anyone tell me how I can calculate the probability that one candidate solution is correct ?

In other words what is the probability that one set of random numbers is the one that solves the puzzle ?

Answer 1

Well, you can continually reduce the likelihood of making a wrong choice by reducing the number of "silly" choices. "Brute force" doesn't worry as much about how silly its choices are though...

I'll assume that you will at least avoid using duplicate letters on each row (as in, you won't have two nines or five nines on one row, though you might have many nines in the same column).

----

The chances are hard to predict though, as there are still many unknowns, like how many pieces are set out.

I'll assume that you have 9 rows and 9 columns.

I googled sudoku and got the first result to count how many spots are filled in. There were 34 out of the 81 spaces filled in.

I'll use that puzzle in fact:

2 x x x x 8 x x x

x 3 8 x 9 7 x x x

x 7 x x 5 4 x 2 1

3 9 7 x 1 x 2 x 4

x x x x x x x x x

5 x 2 x 4 x 1 3 7

4 1 x 5 8 x x 9 x

x x x 9 2 x 4 8 x

x x x 4 x x x x 5

On the first row, there are two spots filled in. For the first space, there are 7 different numbers you can put in (1, 3, 4, 5, 6, 7, 9). Then for the next position, there are 6 choices since you picked one previously. The ones after that have 5, 4, and so on. Thus the first row has:

7·6·5·4·3·2·1 choices.

When you multiply a natural number by all of the positive integers below it, you are doing what is called the factorial. That means you can simplify the above as:

= 7!

The next line has 4 choices taken. That means there are 5 options left (1, 2, 4, 5, 6). Then the next spot has four choices and so on.

This means 5!

For the line below, you have 5 choices taken: 4! choices available.

If you do this for all the rows, you get a total amount of choices of:

7!·5!·4!·3!·9!·3!·4!·5!·7!

If you simplify this, you get:

= (7!)²·(5!)²·(4!)²·(3!)²·9!

Or just calculating gives:

= 2,752,400,208,376,627,200,000

That's over 2 sextillion choices.

Brute force is not the way to go.

----

You greatly improve your chances if you stop and "rewind" once you have a duplicate value in a column. That way, you eliminate all of the things which follow that would be a complete waste of time. A huge number of the above choices would be eliminated by just making sure that the first three lines don't have any overlaps. Then you wouldn't try any of the many choices below that which obviously wouldn't work.

Calculating probabilities like that becomes much more complicated though, and they would change with each puzzle also.

Answer 2

The chance is very slim.

Say, the puzzle already have 30 clues, it will need 51 answers.

The number of totally random combinations will be  9^51.  

so the probability 1/(9^51)  =~ 1/(10^47)

Chances are even much less for puzzles with 17 clues.