Pseudoku
tc...@lsa.umich.edu
http://alum.mit.edu/www/tchow/g4g7.pdf
Ken Jacobs suggested the term "Pseudo Sudoku," or "Pseudoku" for short.
There exist other variants of Sudoku, but I believe these variants are new.
I just acquired the Martin Gardner CD with all his Scientific American
Mathematical Games books and found that he has also written about de Bruijn
sequences and Kirkman triple systems, but I didn't discover this fact until
after G4G7.
--
Tim Chow tchow-at-alum-dot-mit-dot-edu
The range of our projectiles---even ... the artillery---however great, will
never exceed four of those miles of which as many thousand separate us from
the center of the earth. ---Galileo, Dialogues Concerning Two New Sciences
tc...@lsa.umich.edu
>I composed some variants of Sudoku for G4G7, the 7th Gathering for Gardner.
> http://alum.mit.edu/www/tchow/g4g7.pdf
Since Sudoku variants are a dime a dozen, let me say a bit more, to induce
some people to click on the above link.
Here's the first variant. Complete the "Latin tableau" below. Each row
must contain some permutation of the numbers from 1 to r, where r is the
length of that particular row, and each column must contain some permutation
of the numbers from 1 to c, where c is the height of that particular column.
. . . 6 . . . 5 . .
. 7 . . . . . . . 2
. . 9 . . . 1 . . .
. . . . . . . .
8 . . . 3 6 . .
. . . . . .
4 . . . .
. . . . 5
. 3 .
. . 1
The other variants involve combinatorial objects other than Latin squares
(de Bruijn sequences, graceful labelings, Kirkman triple systems).
>Ken Jacobs suggested the term "Pseudo Sudoku," or "Pseudoku" for short.
I've since learned that the term "Pseudoku" was coined some time ago.
Patrick Hamlyn
>In article <44205e7c$0$568$b45e...@senator-bedfellow.mit.edu>, I wrote:
>>I composed some variants of Sudoku for G4G7, the 7th Gathering for Gardner.
>> http://alum.mit.edu/www/tchow/g4g7.pdf
>
>Since Sudoku variants are a dime a dozen, let me say a bit more, to induce
>some people to click on the above link.
>
>Here's the first variant. Complete the "Latin tableau" below. Each row
>must contain some permutation of the numbers from 1 to r, where r is the
>length of that particular row, and each column must contain some permutation
>of the numbers from 1 to c, where c is the height of that particular column.
>
>. . . 6 . . . 5 . .
>. 7 . . . . . . . 2
>. . 9 . . . 1 . . .
>. . . . . . . .
>8 . . . 3 6 . .
>. . . . . .
>4 . . . .
>. . . . 5
>. 3 .
>. . 1
>
>The other variants involve combinatorial objects other than Latin squares
>(de Bruijn sequences, graceful labelings, Kirkman triple systems).
>
>>Ken Jacobs suggested the term "Pseudo Sudoku," or "Pseudoku" for short.
>
>I've since learned that the term "Pseudoku" was coined some time ago.
I knocked over the Pseudoku puzzles in a few minutes, nice difficulty level for
ordinary humans, but the others have had me stumped for a week. For instance, I
can't find any way to attack the graceful labelling puzzles apart from making
lists of which labels can go on which vertices and then backtracking using the
most constrained lists first - v.unsatisfying compared to the Pseudokus which
can be worked out 'linearly'. In fact I'm unlikely to make significant headway
without a computer program unless I find another technique.
--
Patrick Hamlyn posting from Perth, Western Australia
Windsurfing capital of the Southern Hemisphere
Moderator: polyforms group (polyforms...@egroups.com)
tc...@lsa.umich.edu
In article <e6ui22lgpad8kcaur...@4ax.com>,
Patrick Hamlyn <path@multipro.N_OcomSP_AM.au> wrote:
>I knocked over the Pseudoku puzzles in a few minutes, nice difficulty
>level for ordinary humans, but the others have had me stumped for
>a week. For instance, I can't find any way to attack the graceful
>labelling puzzles apart from making lists of which labels can go on
>which vertices and then backtracking using the most constrained lists
>first - v.unsatisfying compared to the Pseudokus which can be worked out
>'linearly'. In fact I'm unlikely to make significant headway without a
>computer program unless I find another technique.
A hint for the graceful labelings: Think about the large edge labels first.
Of the 7 puzzles, the icosahedron is the only one that might require some
backtracking, and it is still doable by hand. To solve the Kirkman triple
system, you will most likely need to write down some auxiliary lists to
organize the information more effectively, but again if you spot the right
deductions, no backtracking is necessary.
Patrick Hamlyn
>[Re: http://alum.mit.edu/www/tchow/g4g7.pdf]
>
>In article <e6ui22lgpad8kcaur...@4ax.com>,
>Patrick Hamlyn <path@multipro.N_OcomSP_AM.au> wrote:
>>I knocked over the Pseudoku puzzles in a few minutes, nice difficulty
>>level for ordinary humans, but the others have had me stumped for
>>a week. For instance, I can't find any way to attack the graceful
>>labelling puzzles apart from making lists of which labels can go on
>>which vertices and then backtracking using the most constrained lists
>>first - v.unsatisfying compared to the Pseudokus which can be worked out
>>'linearly'. In fact I'm unlikely to make significant headway without a
>>computer program unless I find another technique.
>
>A hint for the graceful labelings: Think about the large edge labels first.
I started doing the second of these, it looks easier. In fact labelling one of
the vertices fixes about 10 vertices/edges.
>Of the 7 puzzles, the icosahedron is the only one that might require some
>backtracking, and it is still doable by hand. To solve the Kirkman triple
>system, you will most likely need to write down some auxiliary lists to
>organize the information more effectively, but again if you spot the right
>deductions, no backtracking is necessary.
I shall renew my efforts. I already had made a few lists for the Kirkman
triples. Nice set of puzzles BTW.
r.e.s.
>>I composed some variants of Sudoku for G4G7, the 7th Gathering for
>>Gardner.
>> http://alum.mit.edu/www/tchow/g4g7.pdf
I've taken the liberty of posting a link to your paper at
http://www.sudoku.com/forums/viewtopic.php?p=24071#24071
Here's an example generalising the "Latin tableau" puzzle
(fixed-width font required for viewing) ...
3 1 . .
3 . . 5
. 6 5 . .
. 8 4 0 . . . . 1 .
. .
. .
4 . 3 . .
. . 8 5 .
. . 5 8
The only rule:
Replace each dot with a number, making each row & column
contain a permutation of some set of consecutive numbers.
Does this construction also have a "standard" name?
--r.e.s.
tc...@lsa.umich.edu
r.e.s. <r...@ZZmindspring.com> wrote:
>I've taken the liberty of posting a link to your paper at
>http://www.sudoku.com/forums/viewtopic.php?p=24071#24071
Thanks!
>Replace each dot with a number, making each row & column
>contain a permutation of some set of consecutive numbers.
Interesting concept.
>Does this construction also have a "standard" name?
I doubt it. Prior to the publication of the paper mentioned in the
endnotes of my G4G7 puzzles, even Latin tableaux apparently had no
official name.