Sudoku on a countably infinite board

Consider the game of Sudoku played on an infinite board where the subsquares are also infinite, i.e. our board is indexed by $\mathbb{N}^2 \times \mathbb{N}^2$. Let's call a solution to such a game a function $f(a, b, m, n)$ which assigns a natural number to each space $(m,n)$ in each subsquare $(a,b)$, such that each row, column, and subsquare contains every natural number exactly once.

It is clear that such a solution exists, as for any finite board state, given any natural number and any row, column, or subsquare, there are always at most a finite number of "collision" squares, and so with infinite spaces at our disposal we can always pick a space to put this number in, and continue to do this infinitely until we have filled the board.

However, I'm having trouble constructing an explicit example of such a solution, which does not rely on this choice-like magic. My initial thought was to use products of primes to guarantee that you don't have a collision, but while I can get plenty of solutions with no repetitions, guaranteeing that every row, column, and subsquare contains every label seems like a lot harder of a challenge. But, I suspect I'm missing a very elegant / basic solution. Any ideas / hints?

Solution 1:

Let $p$ be a bijection from $\mathbb N^2$ to $\mathbb N$. One example is $p(x,y)=2^x(2y+1)-1$ (assuming that $0\in \mathbb N$).

Let $\oplus$ be an operation on $\mathbb N$ for which $(\mathbb N,\oplus)$ is a group. For example, $\oplus$ could be nimber addition.

Then you can check that $$ f(a,b,m,n)=p(a\oplus n,b\oplus m) $$ is a valid sudoku function. We just need to to check $3$ things:

• For each row, meaning with $a$ and $m$ fixed and $b$ and $n$ varying, the group properties of $\oplus$ imply that every ordered pair of natural numbers is represented as $(a\oplus n,b\oplus m)$ exactly once, so the fact $p$ is a bijection means every natural number appears exactly once in every row.

• The same logic applies to the columns.

• For the boxes, we instead have $a$ and $b$ fixed. Again, as $m,n$ vary, $(a\oplus n,b\oplus m)$ will assume each ordered pair of natural numbers exactly once.

Solution 2:

It is a well-known constructive (diagonal argument) theorem that there exists a bijection $$ \mathbb N \leftrightarrow \mathbb N^2. $$ This gives you the first (top-left) square, as well as the first column. Now consider this pattern:

1 2 3 4 5 6 7 8
2 1 4 3 6 5 8 7
3 4 1 2 7 8 5 6
4 3 2 1 8 7 6 5

etc.

This pattern is actually a pattern of successive squares, each with a side-length of $2^n$. The first square is just $1$, and the $n$-th square is formed from the $n-1$st by taking the original square $A$, obtaining another square by adding $2^{n-1}$ to it and then setting the next square to be

A B
B A.

This way, we get every natural number in every row and every column of an infinite square. By taking $n$ to stand for the $n$-th columns of the top-left square and ordering all columns of the squares below it in this way, we obtain the first column of the Sudoku.

Now using this method applied to rows instead of columns, we build the solution left to right.

This works because the property of having all numbers in a column does not change when permuting the rows of a square.

Solution 3:

Just to make clear, you do not have to be 'clever enough' to come up with a 'closed-form' solution. Having 'finitely many obstructions' is enough to rigorously prove the existence of a solution. Here is one way.

The board is divided into big-rows, each of which has infinitely many small-rows. Same for big-columns and small-columns. Call the $j$-th small-row in the $i$-th big-row row $(i,j)$, and similarly for column $(i,j)$. The board is also divided into subsquares, each of which is the intersection of a big-row and a big-column. Call the intersection of the $i$-th big-row and $j$-th big-column square $(i,j)$.

There are a few requirements we need to satisfy besides no collisions:

• $R(i,j,k)$: Row $(i,j)$ has an occurrence of $k$.
• $C(i,j,k)$: Column $(i,j)$ has an occurrence of $k$.
• $S(i,j,k)$: Square $(i,j)$ has an occurrence of $k$.
• $D(i,j,k,l)$: The cell $(i,j,k,l)$ is filled.

In each round $m∈ℕ$, we can satisfy all the requirements $R(i,j,k)$, $C(i,j,k)$, $S(i,j,k)$, $D(i,j,k,l)$ where $\max(i,j,k,l) = m$ by handling them one by one, since there are only finitely many of them. To see why we can succeed for each requirement, note that at any point we have filled only finitely many cells. Thus for each of the $R,C,S$ requirements we can easily pick an empty cell to satisfy it. And for each $D$ requirement we can easily pick a natural number that we have not used yet. We can even make this choice deterministically, by picking for each of the $R,C,S$ requirements the uppermost then leftmost cell that works, and by picking for each $D$ requirement the smallest natural number that works.

At the end, we have satisfied all the requirements and still have no collisions, and hence have a filled infinite sudoku board as desired.