## How many valid Soduko grids are there?

## How many valid Soduko grids are there?

(OP)

Hi All,

I'm not sure if this counts as a puzzle, but it's something that I've been trying to exercise my brain on these last few day:

What's the algorithm or formula for determining the number of legal ways of filling a Soduko grid?

Understand, I'm not interested in knowing what the number is (well, I suppose it would be slightly interesting). I would like to know how to go about calculating it.

I've got as far as saying that the first row will have 9! (factoral 9) combinations. For the second row, I'd guess there would be 9 * 2 * 3! (each of the 9 in the first row could go in one of two possible 3 x 3 squares, and for (the second row in) each square there would be 3! combinations).

After that, my brain starts hurting and I can't see how to proceed.

Anyone got any insights?

Mike

Mike Lewis (Edinburgh, Scotland)

My Visual FoxPro site: www.ml-consult.co.uk

## RE: How many valid Soduko grids are there?

________________________________________________________

Zameer Abdulla

Help to find Missing people

Sharp acids corrode their own containers.

## RE: How many valid Soduko grids are there?

ht

It's not perfect - gets stuck on some of the fiendish difficulty level puzzles, but it pauses to let you interact with it when this happens.

Cheers,

Jeff

Jeff's Page @ Code Couch

http://www.codecouch.com/jeff/

http://www.codecouch.com/jeff/blog/

What is Javascript? FAQ216-6094

## RE: How many valid Soduko grids are there?

Thanks for both those replies. They didn't answer my question, but the links are interesting -- and worth exploring further.

BabyJeffy: I've toyed with the idea of writing a solver myself, but I doubt I've got the skill to do it (other than by brute force, which as you rightly say wouldn't be fun).

Mike

__________________________________

Mike Lewis (Edinburgh, Scotland)

My Visual FoxPro site: www.ml-consult.co.uk

## RE: How many valid Soduko grids are there?

AFAIK formula is purely deductive. There are 9 blocks:

1 2 3

4 5 6

7 8 9

... each 3x3 in size. Start with #1, #5 and #9, proceed with #2 and #4 (assuming #1/#5/#9 are filled in), then #6 and #8.

Why diagonally? Because blocks within a single step don't affect each other. This simplifies formula a lot. Say, if number of permutations for #1 is N#1, then (N#1)^3 gives count for all 3 blocks in a group (#1/#5/#9) together. Ditto for #2/#4, though this is the toughest part; people unfamiliar with probabilistic math usually do it brute-force. #6/#8 group is trivial. #3/#7 are already uniquely determined with other blocks (multiplier 1 = no need to analyze). All together:

N = (N#1)^3 + (N#2)^2 + (N#6)^2 * 1

or

N = (9!)^3 * (4*9*6*2 + 4*2*2)^2 * (2^3)^2 * 1 = *** gulp! ***

------

select stuff(stuff(replicate('<P> <B> ', 14), 109, 0, '<.'), 112, 0, '/')

## RE: How many valid Soduko grids are there?

Vongrunt,

This is fascinating. Your idea of taking the 3 x 3 grids diagonally seems to be the key. I can see that grids 1, 5 and 9 would have (9!)^3 combinations. I haven't got my head round the rest of it yet, but I'll work on it.

By the way, I reckon that:

(9!)^3 * (4*9*6*2 + 4*2*2)^2 * (2^3)^2 * 1

evalutates to approx. 6.14 * 10^23

Thanks for your insights.

Mike

__________________________________

Mike Lewis (Edinburgh, Scotland)

My Visual FoxPro site: www.ml-consult.co.uk

## RE: How many valid Soduko grids are there?

Cheers,

Dian

## RE: How many valid Soduko grids are there?

Avos number is 6.022E23 this is 6.14E23 if you subtract one from the other you get 11.8E20 !!! or a difference of

11,800,000,000,000,000,000,000

Easy to see how these conspiracy theories start though!!

Steve: Delphi a feersum engin indeed.## RE: How many valid Soduko grids are there?

http://www.mrexcel.com/tip109.shtml

________________________________________________________

Zameer Abdulla

Help to find Missing people

Sharp acids corrode their own containers.

## RE: How many valid Soduko grids are there?

By the way, I just bought a Sudoku book which includes a 16 x 16 grid. The bill it as "the hardest Sudoku in the world". We'll see.

Mike

__________________________________

Mike Lewis (Edinburgh, Scotland)

My Visual FoxPro site: www.ml-consult.co.uk

## RE: How many valid Soduko grids are there?

Jeff

Jeff's Page @ Code Couch

http://www.codecouch.com/jeff/

http://www.codecouch.com/jeff/blog/

What is Javascript? FAQ216-6094

## RE: How many valid Soduko grids are there?

Leslie

Anything worth doing is a lot more difficult than it's worth - Unknown Induhvidual

Essential reading for anyone working with databases: The Fundamentals of Relational Database Design

## RE: How many valid Soduko grids are there?

Leslie,

I've done a few 12 x 12s. I didn't find them particularly difficult, but they do take a lot longer.

I'm saving the 16 x 16 for a long train journey I have to make next month.

Mike

Mike Lewis (Edinburgh, Scotland)

My Visual FoxPro site: www.ml-consult.co.uk

## RE: How many valid Soduko grids are there?

The answer is "42"

## RE: How many valid Soduko grids are there?

Yuri Rubinov has posted his Sudoku game written in VFP here.

I hope it helps.

## RE: How many valid Soduko grids are there?

http://www.sudoku.org.uk/killersudoku.asp

I posted my original thread trying to get ideas for a solver. I thought about making an access database and doing quries on the criteria, but with the number of combonations, even doing just the first three rows was to much.

For these puzzles, thought about running through the different combinations of numbers for each sum (for 6: 123 132 213 231 312 321) but would still end up with quite a lot of data to run through. I also wouldn't even know where to start on entering the criteria. Guess I am just stuck doing these puzzles which I enjoy the most :)

Blue

If I wasn't Blue, I would just be a Dragon...

## RE: How many valid Soduko grids are there?

the number of solutions of course is very high. But if you have one solution, each solution tranlating each of the nine digits to one other would be valid.

for example replace each digit with digit+1 and replace 9 with 1.

If you see all these permutations as similar result I doubt, that there are that many really unique solutions.

Bye, Olaf.

## RE: How many valid Soduko grids are there?

I imagine 1-12 in each row and column, but how are the segments broken up?

## RE: How many valid Soduko grids are there?

There's also a GREAT article in the June 2006 issue of Scientific American about sudoku!

Leslie

## RE: How many valid Soduko grids are there?

JaG

'Very funny, Scotty... Now Beam down my clothes.'

## RE: How many valid Soduko grids are there?

Greg

"Personally, I am always ready to learn, although I do not always like being taught." - Winston Churchill

## RE: How many valid Soduko grids are there?

As far as solving it.. does putting the info into excel and coding it to find the answer count?

## RE: How many valid Soduko grids are there?

Skie, if you can solve it in excel VBA, you go for it, but the prize condition is you must show your working (i.e. VBA Code)

Warmest regards,

JaG

'Very funny, Scotty... Now Beam down my clothes.'

## RE: How many valid Soduko grids are there?

No, it's a very good thing, that there are 26 letters, you can do a 36x36 grid including the ten digits.

What would that be called? Hexatricosimal system?

Bye, Olaf.

## RE: How many valid Soduko grids are there?

solved it (ctrl+A for the spoiler):

## CODE

fgvhlcpyqnjtoisrxembkudwa

dayiphfowkcmbugtqvjnslerx

mbqrxgljtadpvyeshuwkfoicn

jcwnusmxevrhfqkiadloygbpt

vluyteimnqfgkcjdbarphxsow

bkmsgpvcjriduxahftownylqe

hxpqodkwlfbsnvycujgetrami

wirfdtuasbqoehlnkmyxgpjvc

cnaejxogyhmwtrpvsliqdkufb

xybgwvnqfeuilmhptksdcjoar

krdpfmhlgwaqxtojcibyvenus

tocuarbpdskjywnelgvhxqmif

sqnjhiytucpfdevaroxmlwgbk

lvemiaxkojscgbrqnwufpdhty

ihtkrlqsboyvpgwmecnujafxd

qdgxmytucpnkifbwosajehrlv

yjsvnwadhxerclmbgpftuiqko

pfoacnerimxujdqlyhkvbtwsg

uwlbefjvkgoahstxiqdrmncyp

nujwbkshpltymaigvrecofxdq

aexlyjrnvuhbqkcodftiwspgm

gpidkqwemyvxsofujbharctnl

omhcqbgfatlnrjdywxpsivkeu

rsftvocixdgewpukmnqlabyjh

Here's the code used (Visual FoxPro). Beware of broken lines.

## CODE

*(3x3)x(3x3) = 9x9 Grid

*#Define ccCharacters "123456789"

*#Define ccSodukoSDF "D:\my\vfp9\soduko\simplesoduko.sdf"

#Define cnBase 5

*(5x5)x(5x5) = 25x25 Grid

#Define ccCharacters "abcdefghijklmnopqrstuvwxy"

#Define ccSodukoSDF "D:\my\vfp9\soduko\abcsoduko.sdf"

Local lnCount, lcFields

Public gcGridFields

gcGridFields=""

lcFields=""

For lnCount = 1 To cnBase*cnBase

lcFields = lcFields + "," + Chr(lnCount+64)+" C(1)"

gcGridFields = gcGridFields + "," + Chr(lnCount+64)

Endfor

gcGridFields = Substr(gcGridFields,2)

lcFields = Substr(lcFields,2)

Create Cursor curGrid (&lcFields, iLevel I)

Append From (ccSodukoSDF) Type Sdf

Replace All iLevel With 1

Local Array laGrid[1]

Select &gcGridFields From curGrid Into Array laGrid

Create Cursor curSteps (iRow I, iCol I, cLetter C(1), iLevel I, iSolvingCase I)

Clear

solvesudoku(@laGrid,2)

Select curGrid

Delete All In curGrid

Append From Array laGrid

Browse

Procedure solvesudoku()

Lparameters taGrid, tnLevel

Local Array laUsable[cnBase*cnBase,cnBase*cnBase]

Local lnCount, lnCount2, lcUsed, lcUsable

Local liRow, liCol

llContinue = .T.

Do While llContinue

llContinue = .F.

* determine used digits/letters of each row, column, block

Local Array laRows[cnBase*cnBase]

Local Array laCols[cnBase*cnBase]

Local Array laBlks[cnBase*cnBase]

For lnCount=1 To cnBase*cnBase

lcRowUsed = ""

lcColUsed = ""

lcBlkUsed = ""

For lnCount2=1 To cnBase*cnBase

lcRowUsed = lcRowUsed + taGrid[lnCount , lnCount2]

lcColUsed = lcColUsed + taGrid[lnCount2, lnCount ]

lcBlkUsed = lcBlkUsed +;

taGrid[Int((lnCount-1)/cnBase)*cnBase +Int((lnCount2-1)/cnBase)+1,;

(lnCount-1)%cnBase*cnBase+(lnCount2-1)%cnBase+1]

Endfor

laRows[lnCount] = lcRowUsed

laCols[lnCount] = lcColUsed

laBlks[lnCount] = lcBlkUsed

Endfor

* determine usable digits/letters of each field

For lnCount=1 To cnBase*cnBase

For lnCount2=1 To cnBase*cnBase

If !Empty(taGrid[lnCount , lnCount2])

Loop

Endif

lcUsed = laRows[lnCount]+laCols[lnCount2]+laBlks[Int((lnCount-1)/cnBase)*cnBase+Int((lnCount2-1)/cnBase)+1]

laUsable[lnCount,lnCount2] = Chrtran(ccCharacters,lcUsed,"")

If Len(laUsable[lnCount,lnCount2])=0

* error, no digit/letter available for a field!

Return .F.

Endif

If Len(laUsable[lnCount,lnCount2])=1

* only one digit/letter available, then take it!

taGrid[lnCount,lnCount2] = laUsable[lnCount,lnCount2]

laUsable[lnCount,lnCount2] = .F.

Insert Into curSteps Values (lnCount,lnCount2, taGrid[lnCount,lnCount2], tnLevel,1)

llContinue = .T.

Exit

Endif

Endfor

Endfor

If llContinue

Loop

Endif

* examine usable digits/letters of rows

For lnCount=1 To cnBase*cnBase

lcUsable = ""

For lnCount2=1 To cnBase*cnBase

If !Empty(taGrid[lnCount , lnCount2])

Loop

Endif

lcUsable = lcUsable + laUsable[lnCount,lnCount2]

Endfor

* any letter only once available?

lcLetter=""

For lnCount2=1 To Len(lcUsable)

If Occurs(Substr(lcUsable,lnCount2,1),lcUsable)=1

* yes!

lcLetter = Substr(lcUsable,lnCount2,1)

Exit

Endif

Endfor

If !Empty(lcLetter)

For lnCount2=1 To cnBase*cnBase

If !Empty(taGrid[lnCount,lnCount2])

Loop

Endif

If lcLetter $ laUsable[lnCount,lnCount2]

taGrid[lnCount,lnCount2] = lcLetter

laUsable[lnCount,lnCount2] = .F.

Insert Into curSteps Values (lnCount,lnCount2, taGrid[lnCount,lnCount2], tnLevel,2)

llContinue = .T.

Exit

Endif

Endfor

Endif

If llContinue

Exit

Endif

Endfor

If llContinue

Loop

Endif

* examine usable digits/letters of cols

For lnCount=1 To cnBase*cnBase

lcUsable = ""

For lnCount2=1 To cnBase*cnBase

If !Empty(taGrid[lnCount2, lnCount])

Loop

Endif

lcUsable = lcUsable + laUsable[lnCount2,lnCount]

Endfor

lcLetter=""

For lnCount2=1 To Len(lcUsable)

If Occurs(Substr(lcUsable,lnCount2,1),lcUsable)=1

lcLetter = Substr(lcUsable,lnCount2,1)

Exit

Endif

Endfor

If !Empty(lcLetter)

For lnCount2=1 To cnBase*cnBase

If !Empty(taGrid[lnCount2,lnCount])

Loop

Endif

If lcLetter $ laUsable[lnCount2,lnCount]

taGrid[lnCount2,lnCount] = lcLetter

laUsable[lnCount2,lnCount] = .F.

Insert Into curSteps Values (lnCount2, lnCount, taGrid[lnCount2,lnCount], tnLevel,3)

llContinue = .T.

Exit

Endif

Endfor

Endif

If llContinue

Exit

Endif

Endfor

If llContinue

Loop

Endif

* examine usable digits/letters of blocks

For lnCount=1 To cnBase*cnBase

lcUsable = ""

For lnCount2=1 To cnBase*cnBase

liRow = Int((lnCount-1)/cnBase)*cnBase +Int((lnCount2-1)/cnBase)+1

liCol = (lnCount-1)%cnBase*cnBase+(lnCount2-1)%cnBase+1

If !Empty(taGrid[liRow,liCol])

Loop

Endif

lcUsable = lcUsable + laUsable[liRow,liCol]

Endfor

lcLetter=""

For lnCount2=1 To Len(lcUsable)

If Occurs(Substr(lcUsable,lnCount2,1),lcUsable)=1

lcLetter = Substr(lcUsable,lnCount2,1)

Exit

Endif

Endfor

If !Empty(lcLetter)

For lnCount2=1 To cnBase*cnBase

liRow = Int((lnCount-1)/cnBase)*cnBase +Int((lnCount2-1)/cnBase)+1

liCol = (lnCount-1)%cnBase*cnBase+(lnCount2-1)%cnBase+1

If !Empty(taGrid[liRow,liCol])

Loop

Endif

If lcLetter $ laUsable[liRow,liCol]

taGrid[liRow,liCol] = lcLetter

laUsable[liRow,liCol] = .F.

Insert Into curSteps Values (liRow, liCol, lcLetter, tnLevel,4)

llContinue = .T.

Exit

Endif

Endfor

Endif

If llContinue

Exit

Endif

Endfor

Enddo

* no sure letter, so simply try and error now:

Local lcLeft,lcRight

For lnCount=1 To cnBase*cnBase

For lnCount2=1 To cnBase*cnBase

* two letters available only?

If Empty(taGrid[lnCount,lnCount2]) And Len(laUsable[lnCount,lnCount2])=2

* try both

lcLeft = Left(laUsable[lnCount,lnCount2],1)

lcRight = Right(laUsable[lnCount,lnCount2],1)

Select curGrid

Append From Array taGrid

Replace All iLevel With tnLevel For iLevel=0

laUsable[lnCount,lnCount2] = .F.

taGrid[lnCount,lnCount2] = lcLeft

Insert Into curSteps Values (lnCount, lnCount2, lcLeft, tnLevel,5)

If !solvesudoku(@taGrid, tnLevel+1) &&recurse

* restore Grid from before recursion

Select &gcGridFields From curGrid Where iLevel = tnLevel Into Array taGrid

* restore Grid log

Select * From curGrid Where iLevel<=tnLevel Into cursor curGrid readwrite

* restore steps from before recursion

Select * From curSteps Where iLevel<=tnLevel Into Cursor curSteps Readwrite

* including deletion of the last step

Go Bottom In curSteps

Delete Next 1 In curSteps

taGrid[lnCount,lnCount2] = lcRight

Insert Into curSteps Values (lnCount, lnCount2, lcRight, tnLevel,6)

If !solvesudoku(@taGrid, tnLevel+1) &&recurse

* restore Grid from before recursion

Select &gcGridFields From curGrid Where iLevel = tnLevel Into Array taGrid

* also restore Grid log

Select * From curGrid Where iLevel<tnLevel Into cursor curGrid readwrite

* restore steps from before recursion

Select * From curSteps Where iLevel<=tnLevel Into Cursor curSteps Readwrite

* including deletion of the last step

Go Bottom In curSteps

Delete Next 1 In curSteps

Return .F.

Endif

Endif

Endif

Endfor

Endfor

Endproc

A bit ugly, could have defined some more subroutines, but it's configurable for the normal kind of soduko, just define cnBase, ccCharacters and the initial grid ccSodukoSDF correspondingly.

Additional to the final solution you can see some versions of the grid each time the code went into recursion and curSteps contains all single steps done to find the solution (minus the ones that didn't lead to the solution).

The initial grid is read in using a sdf type format, that is simply an ascii text with 25 lines and the characters without any delimiter, eg for your soduko:

## CODE

fg lc njt s x bku a

day h wk b t vj x

bq lj a vyes u cn

m evr fqk adloy pt

luyte mn fg jdb r h so

k pv r uxah t nyl

x wl v uj trami

r u sbqoe n m c

a j g mwt liqd

eu m p s c oa

kr fm lg qx c byve

toc arb jy ne hx mi

n h y p evaro m gbk

ve i x ojs gbrq w pd ty

krlq b vpg mecnu af d

g t n i b v

yjsv wa h m pf q o

pf cneri xuj ly kv w

be v g ahstx rmnc

u b sh a vr c xdq

a xl j n hbqk t

i k em vxs j arctn

om gfa n d wxpsivke

rs t c dg pu m ab

Bye, Olaf.

## RE: How many valid Soduko grids are there?

There is no one single solution to that Sudoku puzzle. After a great amount of work (I was solving it semi-manually), I was able to find multiple solutions that work.

While a brute force approach will find a solution, I was using a "proof by contradiction" approach to try to find the solution, only to find that no such thing exists.

Thanks for the puzzle, though. It was lots of fun!

## RE: How many valid Soduko grids are there?

the first block of the first row you can use any of 9 numbers.

the second block of the first row you have one number already dedicated so can choose any of 8 numbers.

and so forth down to the the last block which leaves you only one number to choose from.

First row straight factor of 9.

9*8*7*6*5*4*3*2=362,880

Second row you can not duplicate the number above so you have 8 numbers to choose from. Next block is where it gets confusing... Conceivably, you could still have 8 numbers to choose from assuming that you used the number above this block in the first block of this row. If not then you only have 7 numbers you can choose from. next block would be only 7 numbers. so I believe it would be:

8*8*7*6*5*4*3*2=322,560

following this logic the next row would be

7*7*7*6*5*4*3*2=246,960

and then:

6*6*6*6*5*4*3*2 and so on and so forth.

But like I said that is only IMHO, so all are more than welcome to call me an idiot and explain it in their own terms.

Shut up and load the Photon Torpedoes...

## RE: How many valid Soduko grids are there?

You're just considering rows and columns. You also need to satisfy the once per block constraint. But the idea is good. I'd say it comes down to this:

9*8*7*6*5*4*3*2*1*

6*5*4*3*2*1*1*1*1*

3*2*1*1*1*1*1*1*1*

6*5*4*3*2*1*1*1*1*

3*2*1*1*1*1*1*1*1*

1*1*1*1*1*1*1*1*1*

3*2*1*1*1*1*1*1*1*

1*1*1*1*1*1*1*1*1*

1*1*1*1*1*1*1*1*1

And that isn't even considering rotated and mirrored solutions or permutations, which also shouldn't be considered as unique solutions.

Possible permutations are 9*8*7*6*5*4*3*2*1, possible rotations *4, possible mirroring *2.

Which would leave something like 6*5*3*3*2*6*5*4*3*2*3*2*3*2 = 13996800

Still not sure if that takes into account the dependancies of row, column and block correctly.

Bye, Olaf.

## RE: How many valid Soduko grids are there?

You seem to be failing to take into account that there can be some overlap of numbers, so instead of:

9*8*7*6*5*4*3*2*1*

6*5*4*3*2*1*1*1*1*

3*2*1*1*1*1*1*1*1*

6*5*4*3*2*1*1*1*1*

3*2*1*1*1*1*1*1*1*

1*1*1*1*1*1*1*1*1*

3*2*1*1*1*1*1*1*1*

1*1*1*1*1*1*1*1*1*

1*1*1*1*1*1*1*1*1

I venture it would look more like:

9*8*7*6*5*4*3*2*1*

6*5*4*6*5*4*3*2*1*

3*2*1*3*2*1*3*2*1*

6*6*6*6*5*4*3*2*1*

5*5*4*5*5*4*3*2*1*

3*2*1*3*2*1*3*2*1*

3*3*3*3*3*3*3*2*1*

2*2*2*2*2*2*2*2*1*

1*1*1*1*1*1*1*1*1

However, even this solution is oversimplified. I think vongrunt had a good solution posted above.

## RE: How many valid Soduko grids are there?

Shut up and load the Photon Torpedoes...

## RE: How many valid Soduko grids are there?

No, I doubt this one:

9*8*7*6*5*4

6*5*4*6*5*4

3*2*1

If I fill in from start to end rowwise, if I get to the second row and the second block, there are NOT 6 digits you can choose from, there are 3 digits already used within the 2nd row and 3 digits within the same block, therefore only in the case the three digits in the same block are identical to the 3 digits of the second row so far, you can choose between any of the 6 remaining digits.

Our schemes each show the most/least possible digits remaining. The factor you need to take should be inbetween, so I fear we are both wrong and the true calculation can't be laid out this way.

Bye, Olaf.

## RE: How many valid Soduko grids are there?

Shut up and load the Photon Torpedoes...

## RE: How many valid Soduko grids are there?

Bye, Olaf.

## RE: How many valid Soduko grids are there?

http://en.wikipedia.org/wiki/Mathematics_of_Sudoku

It's much higher as my result, but I said:

The article says this number was computed through a mixture of logic and brute force computation, so there seems to be no simple formula which you could also apply to the 25x25 grid.

Even taking symmetries into account the number is still higher: 5,472,730,538. As that is not dividable by 9! I'd say permutations are already considered too.

Nevertheless the number of valid sudoku grids is so high, that the industry of sudoku puzzle magazines can thrive quite a long time. It's more probable, that people get tired of these puzzles than that every possible puzzle is ever printed.

Bye, Olaf.

## RE: How many valid Soduko grids are there?

Olaf,

Agreed. As I stated in my post, I was oversimplifying it because I was going for the maximum (mostly to highlight the possibilities excluded in your scheme). The bottom line is that the mathematics of this are a little beyond me at the moment. Thanks for the link. I'll check it out when I get a chance.