How many valid Soduko grids are there?

[Mike Lewis]

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

 

[traingamer]

Looks pretty straightforward to me. What are the actual rules? Is there 1 letter missing?


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

 

[Skie]

so is it all letters sans "z"?

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

 

[JAG14]

traingamer, one letter missing (Z) because its a 25x25 grid and the inconsiderate buggers who invented the English Alphabet put 26 letters in (Not even thinking that somebody, someday would create a game the required Squared Grids, talk about bad future-proofing)

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

[tt]'Very funny, Scotty... Now Beam down my clothes.'[/tt]
​

 

[Olaf Doschke]

Hi!

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.

 

[Olaf Doschke]

Hi JAG,

solved it (ctrl+A for the spoiler):

[COLOR=#ffffff]etkosudbriwlanxfpycgqmvhj          
fgvhlcpyqnjtoisrxembkudwa          
dayiphfowkcmbugtqvjnslerx          
mbqrxgljtadpvyeshuwkfoicn          
jcwnusmxevrhfqkiadloygbpt          
vluyteimnqfgkcjdbarphxsow          
bkmsgpvcjriduxahftownylqe          
hxpqodkwlfbsnvycujgetrami          
wirfdtuasbqoehlnkmyxgpjvc          
cnaejxogyhmwtrpvsliqdkufb          
xybgwvnqfeuilmhptksdcjoar          
krdpfmhlgwaqxtojcibyvenus          
tocuarbpdskjywnelgvhxqmif          
sqnjhiytucpfdevaroxmlwgbk          
lvemiaxkojscgbrqnwufpdhty          
ihtkrlqsboyvpgwmecnujafxd          
qdgxmytucpnkifbwosajehrlv          
yjsvnwadhxerclmbgpftuiqko          
pfoacnerimxujdqlyhkvbtwsg          
uwlbefjvkgoahstxiqdrmncyp          
nujwbkshpltymaigvrecofxdq          
aexlyjrnvuhbqkcodftiwspgm          
gpidkqwemyvxsofujbharctnl          
omhcqbgfatlnrjdywxpsivkeu          
rsftvocixdgewpukmnqlabyjh          [/color]

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

*#Define cnBase 3
*(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:

 t  s    iwl nxfpy  qmv
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.

 

[KornGeek]

JAG14,

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!

 

[TAnselm]

I would think "IMHO" that is a standard 9X9 layout
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...

 

[Olaf Doschke]

Hi Tanselm,

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.

 

[KornGeek]

Olaf,

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.

 

[TAnselm]

The answer is 42

Shut up and load the Photon Torpedoes...

 

[Olaf Doschke]

Hi KornGeek!

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.

 

[TAnselm]

I believe the original question was the maximum possible layouts so yes wou would assume whatever you need to for the maximum.

Shut up and load the Photon Torpedoes...

 

[Olaf Doschke]

The original question can be read, can't it. It's about " the number of legal ways of filling a Soduko grid". Not a maximum that is only a rough calculation being a limit to the number of solutions.

Bye, Olaf.

 

[Olaf Doschke]

Here you go:

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

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

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

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.

 

[KornGeek]

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.

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.