## Infinite Sudoku

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

### Infinite Sudoku

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

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 2row 1row 4row 3....`

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

Code: Select all
`row 4row 3row 2row 1row 8row 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

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

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 4row 3row 2row 1row 8row 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

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

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

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

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

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! Infinite sudoku is much more ludicrous than I thought!
BlueSpark

Posts: 18
Joined: 04 October 2005

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