most recent 30 from http://mathoverflow.net 2013-05-21T16:36:54Z http://mathoverflow.net/feeds/question/51100 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/51100/simplest-examples-of-unique-solution-and-unsolvable-without-backtracking-sudoku-l Ewan Delanoy 2011-01-04T09:38:29Z 2011-01-04T18:06:57Z

<p>A</p> <p>The Sudoku game admits a broad generalization as follows : let $r$ be an integer $\geq 2$ and let $X$ be a finite set, and ${\cal X}$ be a collection of $r$-subsets of $X$ (i.e, a $r$-uniform hypergraph on $X$). We call any mapping $X \to \lbrace 1,2, \ldots ,r\rbrace$ a coloring of $X$.</p> <p>Then, the Sudoku-like problem associated to any partial colouring $g$ of $X$ (i.e. $g$ is a mapping from a subset of $X$ to $\lbrace 1,2, \ldots ,r$) is to extend $g$ to a colouring $f$ such that $f$ restricts to a bijection onto $\lbrace 1,2, \ldots ,r\rbrace$ (a "rainbow coloring") on each $X\in {\cal X}$. To avoid trivialties, we always assume that $X$ is not fully colored from the start, i.e. that $g$ is not defined on the whole of $X$.</p> <p>We say that a Sudoku-like problem is perfect if it admits a unique solution, and reducible if there is a non-backtracking rule that allows one to deduce the color of an initially uncolored vertex $x\in X$ (formally this means that $g$ is not defined at $x$ and that there is a color $c\in \lbrace 1,2, \ldots ,r$ such that either (1) for any color $c' \neq c$ there is a $Y\in {\cal X}$ containing $x$ such that $c'\in g(Y)$ or (2) for any vertex $x' \neq x$ there is a $Y\in {\cal X}$ containing $x'$ such that $c\in g(Y)$). </p> <p>Perfect irreducible Sudoku-like problems do exist (the ordinary Sudoku problem in the end of David Eppstein's arXiv paper <a href="http://arxiv.org/abs/cs/0507053v1" rel="nofollow">http://arxiv.org/abs/cs/0507053v1</a> is one such). It is natural then to look for "simpler" perfect irreducible Sudoku-like problems, i.e. with the smallest possible value for $r$, and with as few hypergarph edges as possible. It is easy to see that we must have $r>2$. Are there examples with $r=3$ ?</p>

http://mathoverflow.net/questions/51100/simplest-examples-of-unique-solution-and-unsolvable-without-backtracking-sudoku-l/51142#51142 Gerhard Paseman 2011-01-04T17:50:11Z 2011-01-04T17:50:11Z

<p>I have a hard time interpreting "simple" in this context. "Simple" might be a fully colored object (so there is no work to do), or an object with few r-subsets present. Let me suggest a related but possibly alternative route.</p> <p>Given an underlying set X and a collection of r-subsets of X all of which are to be rainbow colored, we call a subset U of X universal iff [for any (unique) allowed coloring of X, there is a unique induced coloring on U and vice versa] . U is a minimal universal set if no proper subset stirctly contained in U is universal. Simple here is again ambiguous: X may be a simple universal set, or X - {x} for any singleton set {x}. Or it may be those U which are minimal universal. I prefer to look at the latter out of mathematical interest.</p> <p>Some unverified results of mine are minimal universal sets of size 5 for the 4-color, 16-square sudoku, and 48 for the popular 81-square version. It strikes me that projective planes and certain other combinatorial designs are also good candidates for the study of your generalized Sudoku problems.</p> <p>Gerhard "Ask Me About System Design" Paseman, 2011.01.04</p>