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?
Best Answer
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.