69
$\begingroup$

A standard Sudoku is a $9\times 9$ grid filled with digits such that every row, column, and $3\times 3$ box contains all the integers from $1$ to $9$.

I am thinking about a generalization of Sudoku which I call "continuous Sudoku", which consists of a unit square where every point on that square corresponds to a real number. The rules for continuous Sudoku are designed to be analogous to the rules for standard Sudoku, and I've devised two different rulesets:

  • The first ruleset I call "weak" continuous Sudoku. In weak continuous Sudoku, the only restriction is that every row and column of the square contains every real number in the interval $[0,1]$ exactly once.
  • The second ruleset I call "strong" continuous Sudoku. In strong continuous Sudoku, the rules of weak continuous Sudoku apply, and, in addition, every square sub-region of the unit square contains every real number in the interval $[0,1]$ at least once. This is analogous to the $3\times 3$ box restriction in standard Sudoku.

Let $U = [0,1]$ and $U^2 = U\times U$. More precisely, a weak continuous Sudoku is essentially a function $f:U^2\to U$, which satisfies the following four properties:

  1. If $x,y_1,y_2\in U$ and $y_1\neq y_2$, then $f(x,y_1)\neq f(x,y_2)$.
  2. If $x_1,x_2,y\in U$ and $x_1\neq x_2$, then $f(x_1,y)\neq f(x_2,y)$.
  3. If $x\in U$ then $\{z: f(x,y)=z,y\in U\} = U$.
  4. If $y\in U$ then $\{z: f(x,y)=z,x\in U\} = U$.

Now, strong continuous Sudoku is a bit harder to define precisely. A set $S$ is a square sub-region of $U^2$ iff $S\subseteq U^2$ and there exists $z = (z_1,z_2)\in U^2$ and $r>0$ such that $S = \{(x,y)\in U^2:z_1\leq x\leq z_1+r,z_2\leq y\leq z_2+r\}$. Thus, using this definition, a strong continuous Sudoku is a weak continuous Sudoku which satisfies the following additional property:

  1. If $S$ is a square sub-region of $U^2$, then $f(S) = U$.

I've been trying to look for specific examples of both strong and weak continuous Sudoku grids, but have so far been unsucessful.

I'm not sure whether any weak continuous Sudoku exists. My first attempt: $$ f(x,y)=\begin{cases} x+y &\text{if }x+y\leq 1 \\ x+y-1 & \text{if }x+y>1\end{cases} $$ almost works. It satisfies properties $3$ and $4$, and almost, but not quite, satisfies $1$ and $2$. The issue occurs only at boundaries of the square, for example, $f(0.5,0) = 0.5$ and $f(0.5,1)=0.5$.

Any example of a strong continuous Sudoku will likely need to be an extremely discontinuous pathological function, similar to the Conway base 13 function. Obviously, if there are no weak continuous Sudoku grids, then there are no strong continuous Sudoku grids. Even if there are no weak Sudoku grids, it may be possible to slightly modify the definitions to permit small exceptions such as in the above example.

The main question I'm asking is: Do any weak continuous Sudoku grids exist, and if they do, do any strong continuous Sudoku grids exist?

$\endgroup$
  • 10
    $\begingroup$ the name "continuous" might be a bit misleading here since the function $f$ is not continuous. Maybe "uncountable sudoku" would be better. $\endgroup$ – supinf Oct 28 at 8:59
  • 5
    $\begingroup$ I meant "continuous" to refer to the grid, not the function. That is, there's infinitely many terms in between every two distinct terms on the square grid, without gaps or holes (if you imagine the numbers all laid out on top of the square as in standard Sudoku). But, you're right that it could be confusing, I hope that I've presented it clearly though @supinf $\endgroup$ – ZKG Oct 28 at 9:08
  • $\begingroup$ ok I understand your point. I think I found a weak solution (see my answer). I am confident a strong solution exists, but it would take me some time to write about it. $\endgroup$ – supinf Oct 28 at 9:22
  • 7
    $\begingroup$ I agree about "continuous" being misleading. Perhaps "continuum"? Or "real-valued"? $\endgroup$ – Teepeemm Oct 28 at 19:01
  • 1
    $\begingroup$ You might be happier with $U = [0,1)$. Then your square tiles the plane, just as the discrete Sudoku square tiles the discrete plane. $\endgroup$ – Eric Towers Oct 28 at 19:12
32
$\begingroup$

Weak continuous Sudoku:

A weak continuous Sudoku can be constructed based on the ideas that you already provided.

First, we construct a weak continuous Sudoku for the set $U=(0,1]$ instead of $U=[0,1]$. Here, a weak continuous Sudoku can be constructed by using the function $f$ from your attempt but as a function $f:(0,1]^2\to (0,1]$ (since one boundary is gone, the problems that you observed are now gone, too). Then, choose a bijection $h:[0,1]\to (0,1]$ (an explicit bijection can be constructed if you prefer a constructive soution). Then we define $$ g:[0,1]^2\to [0,1], \qquad (x,y)\mapsto h^{-1} (f(h(x),h(y))). $$ This function $g$ then can be shown to be a weak continuous Sudoku.

Strong continuous Sudoku:

As for strong continuous Sudoku, things get more complicated and it would be a lot of work to explain my construction in full detail, but I can provide a sketch.

First, the bijection $h$ above should be chosen such that each interval in $[0,1]$ contains a subinterval $[ a,b ]$ such that $h(x)=x$ for all $x\in[a,b]$, see the comments below for such a construction. Furthermore, it uses a bijection $j:[0,1]\to [0,1]$ such that $j((c,d))$ is dense in $[0,1]$ for all intervals $(c,d)$, see the comments below for such a construction for $j$.

Then one can mix the rows or columns of the previous weak Sudoku according to $j$, i.e. $\tilde g(x,y)=g(j(x),y)$. This function $\tilde g$ should then be a strong continuous Sudoku. Let me provide a rough sketch how this can be done.

Let $S$ be a square sub-region of $[0,1]^2$. Let $S_2=[a,b]\times [c,d]\subset S$ be a smaller square sub-region, where $a<b,c<d$ are such that $h(x)=x$ holds for all $x\in[a,b]\cup[c,d]$ (such a sub-region exists due to the comments above on the choice of $h$). It suffices to show that $\tilde g(S_2)=[0,1]$ instead of $\tilde g(S)=[0,1]$.

Let $t\in [0,1]$ be given. Let $m:=(c+d)/2$. Since $j([a,b])$ is dense in $[0,1]$, the function values $\{\tilde g(x,m)| x\in[a,b]\}$ are also dense in $[0,1]$. Let $s\in[a,b]$ be such that $\tilde g(s,m)$ is close to $t$ in the sense that $$ t-\frac{d-c}{2} < \tilde g(s,m) < t+\frac{d-c}{2}. $$ By exploiting the definitions of $\tilde g,g,f$ we have $\tilde g(s,m+x)=\tilde g(s,m)+x$ for $x\in (-\frac{d-c}{2},\frac{d-c}{2})$ (with the exception that the values wrap around at $1$). By setting $x=\tilde g(s,m)-t$, we get $t=\tilde g(s,m+x)$ and $(s,m+x)\in S_2 = [a,b]\times [c,d]$. Thus $t$ can be reached and the condition (5.) for strong continuous Sudoku is satisfied.

on the existence of a function $h$:

We can define $h:[0,1]\to (0,1]$ by setting $h(0)=1/2$, $h(1/2)=1/3$, $h(1/3)=1/4$, etc., and $h(x)=x$ for all other $x$. Then for each interval one can find a sufficiently small subinterval $[a,b]$ such that $h(x)=x$ for all $x\in[a,b]$.

on the existence of a function $j$:

This is more complicated, so let me provide a rough sketch. Let $(q_k)_k$ be an enumeration of the rational numbers in $[0,1]$ and let $I_k$ be an interval of length $2^{3-2k}$ centered at $q_k$. We define the sets $$ A_k := I_k\setminus \bigcup_{l>k} I_l.$$ These sets form a partition of $[0,1]$ and each set $A_k$ has cardinality equal to $[0,1]$.

Let $(B_k)_k$ be another sequence of subsets of $[0,1]$ which form a partition of $[0,1]$ such that each $B_k$ is dense and has cardinality equal to $[0,1]$ (such a partition exists, one can append dense countable sets with enough other elements to form sets $B_k$, but I think this requires the axiom of choice). Then we construct $j$ by (bijectively) mapping $A_k$ to $B_k$.

Since the lengths of the sets $A_k$ get smaller and smaller and the rationals $q_k$ are dense, each interval has a subinterval of the form $I_k$. Since $I_k$ contains $A_k$ and $A_k$ is mapped to a dense set $B_k$, we obtain the desired property that $j(I_k)$ is dense in $[0,1]$.

| cite | improve this answer | |
$\endgroup$
  • 2
    $\begingroup$ To define $j$ in an “arithmetic” way: consider a countable disjoint reunion $A_{k,l}$ of infinite sets of $\mathbb{Q} \cap [0,1]$ (for $0 \leq k < p_l^{l+2}$), each set being dense, and the complement $B$ being infinite. Let $I_{k,l}$ be the set of rationals between $k/p_l^{l+2}$ (included) and $(k+1)/p_l^{l+2}$ (excluded except if it is $1$) whose denominator is a power of $p_l$. Let $Z$ be the (infinite) complement of the reunion of the $I_{k,l}$. Then realize $j$ as the identity on the irrationals, a bijection between $Z$ and $B$, and a bijection between every $A_{k,l}$ and $I_{k,l}$. $\endgroup$ – Mindlack Oct 28 at 21:01
  • 2
    $\begingroup$ The idea being that each open interval of $[0,1]$ contains an $I_{k,l}$ so its image under $j$ contains some $A_{k,l}$ so is dense. Very nice solution (I didn’t have room in the previous comment), congratulations! $\endgroup$ – Mindlack Oct 28 at 21:09
  • 5
    $\begingroup$ Perhaps worthy of publication in the MAA Monthly (or similar publication). $\endgroup$ – John Coleman Oct 30 at 12:19
23
$\begingroup$

Here's a weak solution. Using your favorite bijection, replace $[0,1]$ with the Cantor group $2^\mathbb N$ of infinite binary sequences. Then let $f(x,y)=x+y$. That is, just use the group operation: pointwise XOR.

| cite | improve this answer | |
$\endgroup$
  • 6
    $\begingroup$ @Paul That's not quite a bijection though. It doesn't map different reals to $[1,0,0,0,\ldots]$ and $[0,1,1,1,\ldots]$. $\endgroup$ – Chris Culter Oct 28 at 18:35
  • 1
    $\begingroup$ @Paul Then what real number maps to $[1,0,0,0,\ldots]$? $\endgroup$ – Chris Culter Oct 28 at 18:56
  • 1
    $\begingroup$ That would be $[1,0,0,0,\dots] \to 0.1000_2 = 0.5$ $\endgroup$ – Paul Oct 28 at 19:02
  • 5
    $\begingroup$ @Paul But you'd still have [0,0,1,1,1,1,...]=[0,1,0,0,0,...]. Generally, anytime you'd have a finite number of zeros it'd have another representation with a finite number of ones. $\endgroup$ – Teepeemm Oct 28 at 19:06
  • 4
    $\begingroup$ @Teepeemm Ah, I get it now. Okay, so my idea doesn't work. $\endgroup$ – Paul Oct 28 at 19:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.