Infinite Sudoku

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

Infinite Sudoku

Postby BlueSpark » Fri Nov 04, 2005 5:11 pm

First, an aside on chess:

A while back I thought of what it would be like to play Infinite Chess--wherein the current rules of chess apply but the board is infinitely long. The roles of the pieces definitely changed--some where relegated to purely defensive functions, for instance--but the game was playable.

So, I got to thinking about Infinite Sudoku, and dismissed it out of hand. After all, a sudoku that contains an infinite number of rows and an infinite number of columns (and an infinite number of infinity x infinity boxes each containing the numbers 1 through infinity) is quite ludicrous. For one thing, what is the square root of infinity? (A silly question.) I won't outline some of the other obvious problems with the notion of Infinite Sudoku.

However, thinking about ludicrous things can sometimes unearth useful notions. Any thoughts?
BlueSpark
 
Posts: 18
Joined: 04 October 2005

Postby gfroyle » Mon Nov 07, 2005 12:14 am

Actually, I can't see any real problems here.. about the only issue here is how to translate the defining condition from finite to infinite..

For convenience, let's fix the set of symbols that we are using to be the positive natural numbers N = {1, 2, 3, ... }

(A) An infinite Sudoku has the property that each row, column and box must contain each element of N exactly once

or

(B) An infinite Sudoku has the property that each row, column and box must not have any repeated elements


(For finite Sudoku, these conditions are the same.)


Now, consider the top-left box, which I will call the "base" box. Here is one possibility

Code: Select all
1  2  4  7 11...
3  5  8 12..
6  9 13..
10 14..
15..
...


No problem here.. it contains every natural number once each, and has an infinite number of rows and an infinite number of columns - this answers one of your questions, in that the square root of infinity is infinity (at least, the square root of THIS infinity is itself).

Now let's build the other boxes from this one...

Option B is simpler here: just define the (1,2) box (that is, the one that is in row 1, column 2 where here the "rows" and "columns" are the boxes, not the individual rows and columns) by shifting every row up by one (and losing the top row).

Code: Select all
3  5  8 12..
6  9 13..
10 14..
15..
...


Then the (1,3) box is obtained by shifting up by one again.

To get the (2,1) box, just shift the COLUMNS left by one, and the (3,1) box similarly and so on.

Then we have an infinite 2d-array of boxes, each box containing natural numbers with no repetitions, such that each individual row/column also contains no repetitions.... but of course each box no longer contains ALL of the natural numbers because we have dropped off the top rows or left-most columns...


For option (A) we have to be a little bit cleverer in order to permute the rows/columns in each box without throwing away any entries. But I think it can be done like this..

For box (1,2), take the rows of the base box in pairs and exchange them

Code: Select all
row 2
row 1
row 4
row 3
....


For box (1,3), take the rows of the base box in FOURS and reverse the order of them

Code: Select all
row 4
row 3
row 2
row 1
row 8
row 7
...


For box (1,4), take the rows in EIGHTS and in general for box (1,k) take the rows in groups of 2^(k-1) and reverse them.

I *THINK* that this gives a suitable infinite collection of permutations of the rows that does the trick. Then just do the same for columns to get the other boxes.

I don't like to think of how one would actually create a PUZZLE with this as the solution....

Gordon
gfroyle
 
Posts: 214
Joined: 21 June 2005

Postby r.e.s. » Mon Nov 07, 2005 1:02 am

gfroyle wrote:Actually, I can't see any real problems here.. about the only issue here is how to translate the defining condition from finite to infinite..

Did you forget to place a smiley there?:)

gfroyle wrote:For option (A) we have to be a little bit cleverer in order to permute the rows/columns in each box without throwing away any entries. But I think it can be done like this..[...]

Unless I misunderstand, the very first row of your attempted sudoku will be (row_1, row_2, row_4, row_8, row_16, ...)
where row_n (n = 1,2,3,...) is as defined in your "base box". But that won't work, since row_1 U row_2 U row_4 U ... =/= {1,2,3,4,5,...}.:?:
r.e.s.
 
Posts: 337
Joined: 31 August 2005

Postby kjellfp » Mon Nov 07, 2005 1:05 am

gfroyle wrote:Actually, I can't see any real problems here.. about the For box (1,3), take the rows of the base box in FOURS and reverse the order of them

Code: Select all
row 4
row 3
row 2
row 1
row 8
row 7
...


For box (1,4), take the rows in EIGHTS and in general for box (1,k) take the rows in groups of 2^(k-1) and reverse them.

You will miss to have row 3 on top then. But your idea is good.

Let the numbering start from 0. Use the same base box as you wrote up. Then, in box b and row r, use row number (b XOR r) from the original box. (XOR is bitwise). Do the same for columns.
kjellfp
 
Posts: 140
Joined: 04 October 2005

Postby dukuso » Mon Nov 07, 2005 8:20 am

normal sudoku can (and should!) be viewed as a map {1,2,3}^6 -->{0,1}
such that
(1) for all x1,x2,y1,y2 there is exactly one z1 and one z2 with
f(x1,x2,y1,y2,z1,z2)=1
[there is exactly one digit in cell (x1,x2,y1,y2) ]
(2) for all x1,x2,z1,z2 there is exactly one y1 and one y2 with
f(x1,x2,y1,y2,z1,z2)=1
[ digit (z1,z2) appears exactly once in row (x1,x2) ]
(3) for all y1,y2,z1,z2 there is exactly one x1 and one x2 with
f(x1,x2,y1,y2,z1,z2)=1
[ digit (z1,z2) appears exactly once in column (y1,y2) ]
(4) for all x1,y1,z1,z2 there is exactly one x2 and one y2 with
f(x1,x2,y1,y2,z1,z2)=1
[ digit (z1,z2) appears exactly once in block (x1,y1) ]


you could also view it as a map {1,2,3}^4 --> {1..9} instead,
and most of you would probably prefer to do this,
but that misses the nice symmetries/analogies in 6-space when
discussing sudoku-variants.
Also {1,2,3}^6 is somehow more canonical.




infinite sudoku would be a map f:|N^6-->{0,1} such that
(1),(2),(3),(4) hold.

can someone please enumerate these maps ? ;-)

can someone give Gordon's,Klell's construction as an
explicite function f ? Or at least a recursively
defined f ?


infinite latin square would only require (1),(2),(3).


-Guenter
dukuso
 
Posts: 479
Joined: 25 June 2005

Postby kjellfp » Mon Nov 07, 2005 10:50 am

dukuso wrote:can someone give Gordon's,Klell's construction as an
explicite function f ?


Let the "base box" be
Code: Select all
0 1 3 6 ...
2 4 7 ..
5 8 ..
9 ..
..

This is given as a mapping p:NxN --> N by

p(x,y) = [(x+y)^2+3x+y]/2

Then your mapping g:NxNxNxN --> N is given as

g(a,b,c,d) = p(a # d,b # c) where # is bitwise xor.

f:NxNxNxNxNxN --> {0,1} is given as

f(a,b,c,d,e,f) = D(g(a,b,c,d),p(e,f)) where D is the Cronecker delta.


dukuso wrote:can someone please enumerate these maps ? ;-)


Far more trivial than finite sudoku! The answer is c=2^Aleph_0

The cardinality of mappings N^6 --> {0,1} is clearly c.

On the other hand, given just one grid, there are c different ways to repermute the rows in the first band (The mapping sending a permutation to its fixed point set is a surjection [*] from the set of permutations to the set of subsets of N). So c is an upper and lower bound for your question.

Edit:
[*] not a surjection, just "almost". If M is a cofinite subset of N where the complement is a one-point set, then M is not the fixed point set of any permutation. Doesn't violate the cardinality conclusion anyway...
kjellfp
 
Posts: 140
Joined: 04 October 2005

Postby BlueSpark » Mon Nov 07, 2005 2:29 pm

gfroyle wrote:Actually, I can't see any real problems here.. about the only issue here is how to translate the defining condition from finite to infinite..


Then I look forward to your puzzle.:)
BlueSpark
 
Posts: 18
Joined: 04 October 2005

Postby dukuso » Mon Nov 07, 2005 2:42 pm

yes, the "xor-trick" is neat.
I changed it a bit, so it will produce a series of 2^k-sudokus,
each one being a subsudoku of the next one, so it defines
an infinite sudoku.
Unfortunately this can't be done with 3-sudoku,4sudoku,...
since this one has no solution as already mentioned:

12.......
34.......
.........
21.......
43.......
.........
.........
.........
.........



here is the small Basic-program to generate these:

10 N=12:DIM P(16,16),G(N,N,N,N)
20 Z=0:FOR X=1 TO 16:FOR Y=1 TO X-1:Z=Z+1:P(X,Y)=Z:Z=Z+1:P(Y,X)=Z:NEXT:
30 Z=Z+1:P(X,X)=Z:NEXT
40 FOR A=1 TO N:FOR B=1 TO N:FOR C=1 TO N:FOR D=1 TO N:
50 G(A,B,C,D)=P(((A-1) XOR (D-1))+1,((B-1) XOR (C-1))+1):
60 NEXT D,C,B,A



Code: Select all


1
 

12 34
34 12
   
21 43
43 21
   

125A 347C 689E BDFG
347C 125A BDFG 689E
689E BDFG 125A 347C
BDFG 689E 347C 125A
               
21A5 43C7 86E9 DBGF
43C7 21A5 DBGF 86E9
86E9 DBGF 21A5 43C7
DBGF 86E9 43C7 21A5
               
5A12 7C34 9E68 FGBD
7C34 5A12 FGBD 9E68
9E68 FGBD 5A12 7C34
FGBD 9E68 7C34 5A12
               
A521 C743 E986 GFDB
C743 A521 GFDB E986
E986 GFDB A521 C743
GFDB E986 C743 A521
               

125AHQbo 347CJSdq 689ELUfs BDFGNWhu IKMOPYjw RTVXZaly cegikmn+ prtvxz-*
347CJSdq 125AHQbo BDFGNWhu 689ELUfs RTVXZaly IKMOPYjw prtvxz-* cegikmn+
689ELUfs BDFGNWhu 125AHQbo 347CJSdq cegikmn+ prtvxz-* IKMOPYjw RTVXZaly
BDFGNWhu 689ELUfs 347CJSdq 125AHQbo prtvxz-* cegikmn+ RTVXZaly IKMOPYjw
IKMOPYjw RTVXZaly cegikmn+ prtvxz-* 125AHQbo 347CJSdq 689ELUfs BDFGNWhu
RTVXZaly IKMOPYjw prtvxz-* cegikmn+ 347CJSdq 125AHQbo BDFGNWhu 689ELUfs
cegikmn+ prtvxz-* IKMOPYjw RTVXZaly 689ELUfs BDFGNWhu 125AHQbo 347CJSdq
prtvxz-* cegikmn+ RTVXZaly IKMOPYjw BDFGNWhu 689ELUfs 347CJSdq 125AHQbo
                                                               
21A5QHob 43C7SJqd 86E9ULsf DBGFWNuh KIOMYPwj TRXVaZyl ecigmk+n rpvtzx*-
43C7SJqd 21A5QHob DBGFWNuh 86E9ULsf TRXVaZyl KIOMYPwj rpvtzx*- ecigmk+n
86E9ULsf DBGFWNuh 21A5QHob 43C7SJqd ecigmk+n rpvtzx*- KIOMYPwj TRXVaZyl
DBGFWNuh 86E9ULsf 43C7SJqd 21A5QHob rpvtzx*- ecigmk+n TRXVaZyl KIOMYPwj
KIOMYPwj TRXVaZyl ecigmk+n rpvtzx*- 21A5QHob 43C7SJqd 86E9ULsf DBGFWNuh
TRXVaZyl KIOMYPwj rpvtzx*- ecigmk+n 43C7SJqd 21A5QHob DBGFWNuh 86E9ULsf
ecigmk+n rpvtzx*- KIOMYPwj TRXVaZyl 86E9ULsf DBGFWNuh 21A5QHob 43C7SJqd
rpvtzx*- ecigmk+n TRXVaZyl KIOMYPwj DBGFWNuh 86E9ULsf 43C7SJqd 21A5QHob
                                                               
5A12boHQ 7C34dqJS 9E68fsLU FGBDhuNW MOIKjwPY VXRTlyZa gicen+km tvpr-*xz
7C34dqJS 5A12boHQ FGBDhuNW 9E68fsLU VXRTlyZa MOIKjwPY tvpr-*xz gicen+km
9E68fsLU FGBDhuNW 5A12boHQ 7C34dqJS gicen+km tvpr-*xz MOIKjwPY VXRTlyZa
FGBDhuNW 9E68fsLU 7C34dqJS 5A12boHQ tvpr-*xz gicen+km VXRTlyZa MOIKjwPY
MOIKjwPY VXRTlyZa gicen+km tvpr-*xz 5A12boHQ 7C34dqJS 9E68fsLU FGBDhuNW
VXRTlyZa MOIKjwPY tvpr-*xz gicen+km 7C34dqJS 5A12boHQ FGBDhuNW 9E68fsLU
gicen+km tvpr-*xz MOIKjwPY VXRTlyZa 9E68fsLU FGBDhuNW 5A12boHQ 7C34dqJS
tvpr-*xz gicen+km VXRTlyZa MOIKjwPY FGBDhuNW 9E68fsLU 7C34dqJS 5A12boHQ
                                                               
A521obQH C743qdSJ E986sfUL GFDBuhWN OMKIwjYP XVTRylaZ igec+nmk vtrp*-zx
C743qdSJ A521obQH GFDBuhWN E986sfUL XVTRylaZ OMKIwjYP vtrp*-zx igec+nmk
E986sfUL GFDBuhWN A521obQH C743qdSJ igec+nmk vtrp*-zx OMKIwjYP XVTRylaZ
GFDBuhWN E986sfUL C743qdSJ A521obQH vtrp*-zx igec+nmk XVTRylaZ OMKIwjYP
OMKIwjYP XVTRylaZ igec+nmk vtrp*-zx A521obQH C743qdSJ E986sfUL GFDBuhWN
XVTRylaZ OMKIwjYP vtrp*-zx igec+nmk C743qdSJ A521obQH GFDBuhWN E986sfUL
igec+nmk vtrp*-zx OMKIwjYP XVTRylaZ E986sfUL GFDBuhWN A521obQH C743qdSJ
vtrp*-zx igec+nmk XVTRylaZ OMKIwjYP GFDBuhWN E986sfUL C743qdSJ A521obQH
                                                               
HQbo125A JSdq347C LUfs689E NWhuBDFG PYjwIKMO ZalyRTVX kmn+cegi xz-*prtv
JSdq347C HQbo125A NWhuBDFG LUfs689E ZalyRTVX PYjwIKMO xz-*prtv kmn+cegi
LUfs689E NWhuBDFG HQbo125A JSdq347C kmn+cegi xz-*prtv PYjwIKMO ZalyRTVX
NWhuBDFG LUfs689E JSdq347C HQbo125A xz-*prtv kmn+cegi ZalyRTVX PYjwIKMO
PYjwIKMO ZalyRTVX kmn+cegi xz-*prtv HQbo125A JSdq347C LUfs689E NWhuBDFG
ZalyRTVX PYjwIKMO xz-*prtv kmn+cegi JSdq347C HQbo125A NWhuBDFG LUfs689E
kmn+cegi xz-*prtv PYjwIKMO ZalyRTVX LUfs689E NWhuBDFG HQbo125A JSdq347C
xz-*prtv kmn+cegi ZalyRTVX PYjwIKMO NWhuBDFG LUfs689E JSdq347C HQbo125A
                                                               
QHob21A5 SJqd43C7 ULsf86E9 WNuhDBGF YPwjKIOM aZylTRXV mk+necig zx*-rpvt
SJqd43C7 QHob21A5 WNuhDBGF ULsf86E9 aZylTRXV YPwjKIOM zx*-rpvt mk+necig
ULsf86E9 WNuhDBGF QHob21A5 SJqd43C7 mk+necig zx*-rpvt YPwjKIOM aZylTRXV
WNuhDBGF ULsf86E9 SJqd43C7 QHob21A5 zx*-rpvt mk+necig aZylTRXV YPwjKIOM
YPwjKIOM aZylTRXV mk+necig zx*-rpvt QHob21A5 SJqd43C7 ULsf86E9 WNuhDBGF
aZylTRXV YPwjKIOM zx*-rpvt mk+necig SJqd43C7 QHob21A5 WNuhDBGF ULsf86E9
mk+necig zx*-rpvt YPwjKIOM aZylTRXV ULsf86E9 WNuhDBGF QHob21A5 SJqd43C7
zx*-rpvt mk+necig aZylTRXV YPwjKIOM WNuhDBGF ULsf86E9 SJqd43C7 QHob21A5
                                                               
boHQ5A12 dqJS7C34 fsLU9E68 huNWFGBD jwPYMOIK lyZaVXRT n+kmgice -*xztvpr
dqJS7C34 boHQ5A12 huNWFGBD fsLU9E68 lyZaVXRT jwPYMOIK -*xztvpr n+kmgice
fsLU9E68 huNWFGBD boHQ5A12 dqJS7C34 n+kmgice -*xztvpr jwPYMOIK lyZaVXRT
huNWFGBD fsLU9E68 dqJS7C34 boHQ5A12 -*xztvpr n+kmgice lyZaVXRT jwPYMOIK
jwPYMOIK lyZaVXRT n+kmgice -*xztvpr boHQ5A12 dqJS7C34 fsLU9E68 huNWFGBD
lyZaVXRT jwPYMOIK -*xztvpr n+kmgice dqJS7C34 boHQ5A12 huNWFGBD fsLU9E68
n+kmgice -*xztvpr jwPYMOIK lyZaVXRT fsLU9E68 huNWFGBD boHQ5A12 dqJS7C34
-*xztvpr n+kmgice lyZaVXRT jwPYMOIK huNWFGBD fsLU9E68 dqJS7C34 boHQ5A12
                                                               
obQHA521 qdSJC743 sfULE986 uhWNGFDB wjYPOMKI ylaZXVTR +nmkigec *-zxvtrp
qdSJC743 obQHA521 uhWNGFDB sfULE986 ylaZXVTR wjYPOMKI *-zxvtrp +nmkigec
sfULE986 uhWNGFDB obQHA521 qdSJC743 +nmkigec *-zxvtrp wjYPOMKI ylaZXVTR
uhWNGFDB sfULE986 qdSJC743 obQHA521 *-zxvtrp +nmkigec ylaZXVTR wjYPOMKI
wjYPOMKI ylaZXVTR +nmkigec *-zxvtrp obQHA521 qdSJC743 sfULE986 uhWNGFDB
ylaZXVTR wjYPOMKI *-zxvtrp +nmkigec qdSJC743 obQHA521 uhWNGFDB sfULE986
+nmkigec *-zxvtrp wjYPOMKI ylaZXVTR sfULE986 uhWNGFDB obQHA521 qdSJC743
*-zxvtrp +nmkigec ylaZXVTR wjYPOMKI uhWNGFDB sfULE986 qdSJC743 obQHA521
                                                               


...
dukuso
 
Posts: 479
Joined: 25 June 2005

Postby BlueSpark » Tue Nov 08, 2005 2:45 pm

Edit: I think that my idea of an infinite sudoku is quite different from the approaches here, but I like your ideas better (much better). Thanks very much for the responses!:D Infinite sudoku is much more ludicrous than I thought!
BlueSpark
 
Posts: 18
Joined: 04 October 2005

Postby BlueSpark » Sat Nov 12, 2005 8:14 pm

Okay, how about this: a sudoku that has an infinite number of rows and an infinite number of columns, each of which is exhaustively infinite (contains ALL of the numbers from 1,2,3,...onwards), but only has 9 boxes like a standard sudoku, each of which is itself exhaustively infinite.

This is actually what I had in my mind when I was thinking of "infinite Sudoku". Why I wrote above "an infinity of infinity x infinity boxes" above I don't know--I guess I got on a roll typing the word infinity. So I apologize for that.

Of course, the 9-box infinite sudoku is not exactly sudoku-like in a pure sense: a sudoku with 9 answer-candidates has 9 boxes and a sudoku with 16 answer-candidates has 16 boxes, so an infinite sudoku would have an infinite number of boxes, as y'all have written about.

But an infinite sudoku in the standard sense seems a little too easy to fill in--since you always have an infinite number of boxes left. It's no harder than a regular sudoku, in that sense at least. Is this true of the 9-box infinite sudoku?

Edit: Oh, and I forgot to mention: I couldn't rid my mind of the pleasant "image" of an infinite sudoku in which the clues constitute a complete set of the prime numbers (I assume they are infinite in number) until I realized that such a puzzle could not possibly have a unique solution.
BlueSpark
 
Posts: 18
Joined: 04 October 2005


Return to General