Calling all sudoku experts

Everything about Sudoku that doesn't fit in one of the other sections

Calling all sudoku experts

Postby Sarah » Sun Jun 19, 2005 12:12 pm

I am a 16yr old recently hooked on sudoku, and although I might be showing my age here I was wondering if its possible to design a sudoku puzzle so it not only satisfies the row/column/box requirements but the two 9-digit diagonal lines as well.
If anyone has any ideas/thoughts/comments please feel free to reply - but pardon my ignorance if this is an obvious question.:D
Sarah
 
Posts: 2
Joined: 19 June 2005

Postby george-no1 » Sun Jun 19, 2005 1:17 pm

Well, interestingly enough, I am a 14 year old recently hooked on Su Doku and I have been wondering the same thing, but I think it's fairly safe to say there are quite a lot of puzzles that satisfy those requirements, this one being the first one I could think up:

1 4 5 l 3 6 7 l 2 9 8 l
6 2 8 l 1 4 9 l 3 7 5 l
7 9 3 l 5 2 8 l 6 1 4 l
==================
2 5 7 l 4 8 1 l 9 6 3 l
9 6 4 l 7 5 3 l 8 2 1 l
3 8 1 l 2 9 6 l 4 5 7 l
==================
8 1 9 l 6 3 5 l 7 4 2 l
5 3 2 l 9 7 4 l 1 8 6 l
4 7 6 l 8 1 2 l 5 3 9 l

As for how many possible Su Dokus there are that fit these requirements, that is a much more difficult question, and I would invite anyone who feels up to the challenge to work it out - I'll have a go but I'll probably fail.

George:)
george-no1
 
Posts: 150
Joined: 20 May 2005

Postby Red Ed » Sun Jun 19, 2005 8:17 pm

This one ought to yield to brute force. Like this, for example:

1. we may as well assume that the leading diagonal contains 1...9 in that order. Then we'll count the number of solutions and multiply the result by 9! = 362880 to get the final answer.

2. given 1...9 down the leading diagonal, there are 4752 ways of placing 1...9 in some order down the other diagonal to make an X shape. Given any such X shape, it's easy to have a computer enumerate all possible completions of the grid. But doing that 4752 times is too expensive, so ...

3. we split the 4752 X shapes into equivalence classes. Two X shapes are equivalent if you can transform one into the other by rotating, transposing and permuting the rols/cols of the grid. This is standard stuff by now! In this case, I think we end up with 74 equivalence classes (to be confirmed ...).

4. so now you just do 74 (or however many it is) calculations, one per representative X shape, and add up the results.

I'll set this going overnight. Hopefully have an answer by the morning.
Red Ed
 
Posts: 633
Joined: 06 June 2005

Postby Red Ed » Sun Jun 19, 2005 10:05 pm

It finished quicker than I expected. There would appear to be 9! * 0x23aebeed30 = 55613393399531520 sudokus that have 1-9 laid out in some order on the diagonals.

This is roughly in line with the following naive approximation. A random sudoku diagonal can be constructed in x = (9*8*7)^3 ways, of which only 9! = x/352.8 are acceptable for this new type of puzzle. There are 6.67*10^21 sudokus, so maybe only 1 in 352.8^2 of those = 5.36*10^16 have the diagonal property we need.
Red Ed
 
Posts: 633
Joined: 06 June 2005

Postby george-no1 » Mon Jun 20, 2005 9:51 am

Well done there, that seems good enough to me!!

George:)
george-no1
 
Posts: 150
Joined: 20 May 2005

nice work!

Postby Sarah » Mon Jun 27, 2005 5:26 am

Well done for figuring that out - I'll take your word on it as I'm no maths whiz.:) Just one of the great things about sudoku, you don't have to be brillant at maths to work out a numbers game!
Sarah
 
Posts: 2
Joined: 19 June 2005


Return to General

cron