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

 

[ZmrAbdulla]

try

http://www.excelforum.com/showthread.php?t=380395

________________________________________________________
Zameer Abdulla
Help to find Missing people
Sharp acids corrode their own containers.

 

[BabyJeffy]

I wrote a Soduko solver in Javascript a while back. It didn't do brute force - which was the fun part

http://code-couch.com/jeff/snippets/sudoku/index.php

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

[tt]Jeff's Page @ Code Couch

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

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

[/tt]

What is Javascript? FAQ216-6094

 

[Mike Lewis]

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

 

[vongrunt]

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

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! ***

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

 

[Mike Lewis]

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

 

[Diancecht]

That is the Avogadro number ... the universal conspiration is out there

Cheers,
Dian

 

[sggaunt]

Dan Conspiracy, Well not really.
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.

 

[ZmrAbdulla]

Yeah.. here is the one I have found long before.. was missing from the favourites. It is with Excel VBA.

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

________________________________________________________
Zameer Abdulla
Help to find Missing people
Sharp acids corrode their own containers.

 

[Mike Lewis]

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

 

[BabyJeffy]

Oooo... is it done in Hex?

Jeff

[tt]Jeff's Page @ Code Couch

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

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

[/tt]

What is Javascript? FAQ216-6094

 

[lespaul]

My Sudoku book has a 12x12 grid and that was pretty difficult! I had to create an excel spreadsheet with extra large squares to track all of my candidate numbers!

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

 

[Mike Lewis]

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

 

[franklin97355]

There is an article in Circuit Cellar April issue by Jeff Bachiochi on automating Sudoku puzzle solving.

The answer is "42

 

[TheRambler]

Hi Mike,

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

Play Sudoku: create puzzle on your own, get puzzle, solve it on your own, get the solution, see how the solution works by following it step by step. Written in VFP7, but for the best of my knowledge it should run from VFP command window in versions 5/6/8/9.

I hope it helps.

 

[bluedragon2]

I was pointed to this thread from another I started in the Squaring the Circle forum. I enjoy sudoku puzzles and have found a site that has sudoku puzzles combined with cross sums:

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]Blue[/Blue] [Dragon]

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

 

[Olaf Doschke]

Hi Mike,

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.

 

[KornGeek]

I can understand how a 16x16 grid works (1-16 in each row, column, and 4x4 segment), but how does a 12x12 grid work?

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

 

[lespaul]

here's a link that shows the variant grids.

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

Leslie

 

[JAG14]

Free copy of The Sims 2 or GTA: Vice City to the first one to solve this bugger.

JaG

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