| View previous topic :: View next topic |
| Author |
Message |
John Ruddock
Joined: 19 Oct 2005
Posts: 4
|
 Posted: Tue Oct 25, 2005 7:37 pm Post subject: More mathematics - possibly esoteric |
 |
|
I have always been interested in maths, though not a brilliant practitioner. I did study maths for scientists in my 1st year at university, but have never studied number theory or advanced combinatorial theory. I have a layman's interest for "the 4 coloured map problem", "Fermat's last theorem" etc.
So esoteric questions:
Given that I can't see why a classical 9 x 9 Sudoku grid can't have a solution in which the top left box, the centre middle box and the bottom right box are identical - can any of these solutions be solved from a 17 number starting grid?
Can the numbers in a 17 number starting grid be placed according to a knight's tour?
Are there any symmetrical 17 number starting grids? Placement only.
I have seen and completed puzzles in which only 8 different integers have been provided - what is the minimum number of different integers that are needed?
For this minimum number, what is the smallest size of starting grid? Are any of them 17? |
|
| Back to top |
|
 |
David Bryant
Joined: 29 Jul 2005
Posts: 559
Location: Denver, Colorado
|
| Posted: Wed Oct 26, 2005 3:54 pm Post subject: Some General Observations |
|
|
Good to hear from you, John.
I'd like to make just a few general observations about your questions. I'm not sure I can answer any of them completely, but maybe with some help from the other good people on this forum we can at least make a dent in a couple of them.
| John Ruddock wrote: | | Given that I can't see why a classical 9 x 9 Sudoku grid can't have a solution in which the top left box, the centre middle box and the bottom right box are identical - can any of these solutions be solved from a 17 number starting grid? |
Since permutation of the digits will transform any valid Sudoku grid into another valid Sudoku grid, we can make the first part of this question a bit more specific and say that the top left, middle center, and bottom right boxes must all look like this:
We can also replace your "I can't see why ..." verbiage with an actual example of such a solution grid:
| Code: | 123 597 648
456 218 397
789 634 512
874 123 965
392 456 871
615 789 234
947 865 123
238 971 456
561 342 789 |
| John Ruddock wrote: | | Can the numbers in a 17 number starting grid be placed according to a knight's tour? |
Either I don't understand this question, or else the answer is clearly yes. A knight's tour of a 9x9 checkerboard would have to involve 80 moves, and would by definition lead through every square on the board.
I guess you mean "Can the clues in a 17-clue Sudoku be arranged so that it's possible for a knight to visit all 17 cells in just 16 moves?" Is that what you had in mind? Does the knight have to end up back at the starting point after a 17th move? Or can he be anywhere (in relation to the starting point) after 16 moves?
| John Ruddock wrote: | | Are there any symmetrical 17 number starting grids? Placement only. |
Can you be a bit more specific about the particular symmetry that interests you? I suppose you mean the rotational symmetry (1/2 rotation about the center square) that's commonly exhibited in published puzzles. We could also characterize this as reflection across a diagonal.
Other forms of symmetry are possible -- for example, reflection across row (or column) 5. A guest ("mwalimu") raised a question about the various possible symmetries right here just a few days ago.
| John Ruddock wrote: | I have seen and completed puzzles in which only 8 different integers have been provided - what is the minimum number of different integers that are needed?
For this minimum number, what is the smallest size of starting grid? Are any of them 17? |
Since we have a (possibly complete) list of the 17-clue Sudokus, we ought to be able to answer a related question (what's the smallest number of distinct digits in the initial 17-clue grid?) fairly easily.
These are interesting questions, John. Thanks for bringing them up! dcb |
|
| Back to top |
|
|
Guest
|
| Posted: Wed Oct 26, 2005 6:24 pm Post subject: Re: Some General Observations |
|
|
| David Bryant wrote: | Good to hear from you, John.
Thanks David, your insights are very interesting - I have just spent an hour replying to this message, but the "gremlins" ate the message! I provided some comment, some clarification and some thoughts for future discussion. This time round, I'll leave out the future thoughts.
I'd like to make just a few general observations about your questions. I'm not sure I can answer any of them completely, but maybe with some help from the other good people on this forum we can at least make a dent in a couple of them.
| John Ruddock wrote: | | Given that I can't see why a classical 9 x 9 Sudoku grid can't have a solution in which the top left box, the centre middle box and the bottom right box are identical - can any of these solutions be solved from a 17 number starting grid? |
Since permutation of the digits will transform any valid Sudoku grid into another valid Sudoku grid, we can make the first part of this question a bit more specific and say that the top left, middle center, and bottom right boxes must all look like this:
We can also replace your "I can't see why ..." verbiage with an actual example of such a solution grid:
| Code: | 123 597 648
456 218 397
789 634 512
874 123 965
392 456 871
615 789 234
947 865 123
238 971 456
561 342 789 |
Perhaps I have missed the point here. Thanks for providing a valid solution according my desired design. Can this solution be reduced to a 17 clue starting grid - or is it the cae that ALL Sudoku 9 x 9 solutions can be reduced to a 17 clue starting grid?
| John Ruddock wrote: | | Can the numbers in a 17 number starting grid be placed according to a knight's tour? |
Either I don't understand this question, or else the answer is clearly yes. A knight's tour of a 9x9 checkerboard would have to involve 80 moves, and would by definition lead through every square on the board.
I guess you mean "Can the clues in a 17-clue Sudoku be arranged so that it's possible for a knight to visit all 17 cells in just 16 moves?" Is that what you had in mind? Does the knight have to end up back at the starting point after a 17th move? Or can he be anywhere (in relation to the starting point) after 16 moves?
Your clarification of my inappropriately worded question is right on. I think both the scenarios you put in the above paragraph merit an answer>
| John Ruddock wrote: | | Are there any symmetrical 17 number starting grids? Placement only. |
Can you be a bit more specific about the particular symmetry that interests you? I suppose you mean the rotational symmetry (1/2 rotation about the center square) that's commonly exhibited in published puzzles. We could also characterize this as reflection across a diagonal.
Other forms of symmetry are possible -- for example, reflection across row (or column) 5. A guest ("mwalimu") raised a question about the various possible symmetries right here just a few days ago.
mwalimu's analysis of symmetry is brilliant. I totally agree with his rank order - which begs the question - what is the highest symmetry possible for a 17 clue starting grid?
| John Ruddock wrote: | I have seen and completed puzzles in which only 8 different integers have been provided - what is the minimum number of different integers that are needed?
For this minimum number, what is the smallest size of starting grid? Are any of them 17? |
Since we have a (possibly complete) list of the 17-clue Sudokus, we ought to be able to answer a related question (what's the smallest number of distinct digits in the initial 17-clue grid?) fairly easily.
These are interesting questions, John. Thanks for bringing them up! dcb
I've got loads more, I'm particularly intersetd in the categorisation of operations, "quantifying" each moves's difficulty and hence compiling a "quantitative" description of each puzzle from which the current newspaper "banding" system falls foul. This message had better get through!!!
|
|
|
| Back to top |
|
|
David Bryant
Joined: 29 Jul 2005
Posts: 559
Location: Denver, Colorado
|
| Posted: Wed Oct 26, 2005 8:29 pm Post subject: A statistical sample |
|
|
| John Ruddock wrote: | I have seen and completed puzzles in which only 8 different integers have been provided - what is the minimum number of different integers that are needed?
For this minimum number, what is the smallest size of starting grid? Are any of them 17? |
I don't have an answer to these questions yet, but I did crunch my way through the first 100 17-clue Sudoku puzzles to see how the digits in each one shake out. Here are my results.
-- Exactly 79 different combinations of the digits 1 - 9 occur in those 100 puzzles. 61 of the combinations are unique; 15 of them occur twice, and 3 of them occur three times.
-- In 40 of the puzzles, only eight of the digits appear as initial clues.
-- Of those 40, 39 omit the digit "9", and 1 omits the digit "7".
I understand that statistics don't really prove anything, but sometimes they're interesting. Here is the list of combinations of digits I found in those first 100 17-clue puzzles. Notations to the right indicate either 2 or 3 occurrences for the ones that were duplicated. dcb
| Code: | 11122233344566778
11122233345566778
11122233345667789
11122233444556778
11122233445566778
11122233445566788 2
11122233445567788 3
11122233445666789
11122233445667788 2
11122233445667789 3
11122233445667899
11122233445677889
11122233455667778
11122233455667899 2
11122233455678889
11122234455666778
11122234455667899 2
11122234455677889
11122234555678899
11122234556678899 2
11122333445566778
11122333445566788
11122333445567788
11122334445566778 2
11122334445567788
11122334445677788
11122334455667788
11122334455667789
11122334455667889
11122334455677889
11122334456677889
11122334556667788
11122334556677888
11122334556778899 2
11122344455667788 2
11122344555667788
11122344555667789
11122344556778899 2
11123344455667789
11123344455677889 2
11123344455677899 2
11123344456678899
11123344555667889
11123344556677889 2
11123344556677899
11123344556678889
11123344556678899
11123344556778899
11123444556677899
11123444556678899
11222333445556778
11222333445566788
11222333445667788
11222333445667888
11222333455667788
11222334445566778
11222334445566788
11222334455566778
11222334455666778
11222334455667788 3
11222334455667789 2
11222334455678889
11222334455678899
11222334456677899
11222334456778889
11222334556678999
11222334667788999
11222344555667888
11223334445568899 Note no "7"s
11223334445678899
11223334456667889
11223334556677889
11223344455666789
11223344456677789
11233344456667889 2
11233344566777899 2
11233444555678899
12223344455667789
12233445566677899 |
|
|
| Back to top |
|
|
Umfundi
Guest
|
| Posted: Fri Oct 28, 2005 3:31 am Post subject: Mathematics of Sudoku |
|
|
There is an interesting article in WikiPedia:
http://en.wikipedia.org/wiki/Sodoku
I just wish my math skills were not so rusty!
Keith |
|
| Back to top |
|
|
umfundi
Guest
|
| Posted: Fri Oct 28, 2005 4:10 am Post subject: Re: More mathematics - possibly esoteric |
|
|
[quote="John Ruddock"]
Given that I can't see why a classical 9 x 9 Sudoku grid can't have a solution in which the top left box, the centre middle box and the bottom right box are identical - can any of these solutions be solved from a 17 number starting grid?
=================
Here is a solution in which the diagonal boxes are identical (top left to bottom right)
1 2 3 9 7 8 5 6 4
4 5 6 3 1 2 8 9 7
7 8 9 6 4 5 2 3 1
6 4 5 1 2 3 9 7 8
9 7 8 4 5 6 3 1 2
3 1 2 7 8 9 6 4 5
8 9 7 5 6 4 1 2 3
2 3 1 8 9 7 4 5 6
5 6 4 2 3 1 7 8 9
I suspect the minimum starting point for this solution to be unique is a lot more than 17 numbers. In fact, it seems to me that the more symmetry in the solution, the more clues are needed to start.
Keith |
|
| Back to top |
|
|
|
|
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
|
Powered by phpBB © 2001, 2005 phpBB Group
|
FAQ
Search
Memberlist
Usergroups
Register
Profile
Log in to check your private messages
Log in
