4
$\begingroup$

Sixy Sudoku is a variation on Latin squares and traditional sudoku played on a $6 \times 6$ grid with an initial clue of several cells filled in with a subset of the digits $1$–$6$. The task is to fill in the remaining cells such that each digit appears once in each

  • $1 \times 6$ row
  • $6 \times 1$ column
  • $2 \times 3$ shaded rectangle
  • $3 \times 2$ outlined rectangle

enter image description here

Questions

  • Given a grid with no initial filled cells, how many valid filled grids, $K$, exist (up to digit-permutation symmetry)?
  • What is the minimum number of filled cells, $n^*$, that guarantees a unique puzzle solution?
  • For that minimum $n^*$, how many distinct placements of filled cells ensure a unique solution (up to digit-permutation symmetry)?

For the first problem, without loss of generality, we can set the digits in the upper-left shaded rectangle as shown here:

enter image description here

Guided by @GerardPaseman (below), we can see that there are $2^7$ ways to fill the top half of the puzzle (given the assigned upper-left shaded rectangle): The top row has $2^2$ alternatives (given all constraints), and the second row has $2^2$ alternatives. The third row has $2^3$ alternatives. Putting together: $2^7$. But then there are the cells in the bottom half of the puzzle. The naive (but slightly tighter) bound is thus $(2^7)^2$.

The red show the number of independent alternatives in some of the cells starting at the right top shaded rectangle, then beneath it, then moving to the left:

enter image description here

(The blue arrows show the sequence of cell fillings using all prior constraints. One can work in a different sequence of cell constraints, if desired.)

For the last two problems it will be interesting to see how close the information defined by the number of minimal filled cells, $n^*$ (where $n^* \geq 5$ for digit specification), and candidate placements approximates the information bound given by $K$.

Addendum:

Today's Sixy Sudoku puzzle in The New York Times magazine is a variation on the traditional puzzle in which the bordered rectangles are replaced by $6$-element locking polyominoes, as shown:

5-clue puzzle

I confirmed that this puzzle is solvable. Note that it has just $n=5$ clue cells. This suggests (but of course doesn't prove) that $n^* = 5$ for the traditional rectangular Sixy Sudoku.

Improve this question
$\endgroup$
16
  • $\begingroup$ Have you looked at 'Taking Sudoku Seriously', by Rosenhouse and Taalman? They work out answers to analogous questions for 4 by 4 Sudoku. $\endgroup$
    – Stopple
    Commented Oct 7, 2019 at 16:43
  • $\begingroup$ @Stopple: Yes, I have read Taking Sudoku seriously---a wonderful book. My problem is a bit different from the one they treated in the extend of the constraints. $\endgroup$
    – David G. Stork
    Commented Oct 7, 2019 at 16:44
  • $\begingroup$ There are 32 ways to fill the top remaining twelve squares, and 729 ways to fill the remaining squares for each of the 32 ways. I suspect the constraints will eliminate at least 2/3 of these combinations, leaving less than 8000 possibilities. A brute force breadth first search by computer should answer all of your questions. Gerhard "Small Is The New Big" Paseman, 2019.10.07. $\endgroup$
    – Gerhard Paseman
    Commented Oct 7, 2019 at 17:09
  • $\begingroup$ No. I am upper bounding. The top three squares admit four possibilities, as do the second row (so 128, not 32, sorry for the mistake). The eight possibilities for the third row should be obvious. Then column constraints give 6^6 (instead of 3^6) ways to fill the bottom half. So I was off by a factor 2^8, but still this is well within computer search. I am not using all constraints. Gerhard "729 Times 8192 Still Small" Paseman, 2019.10.07. $\endgroup$
    – Gerhard Paseman
    Commented Oct 7, 2019 at 17:18
  • 1
    $\begingroup$ @DavidRoberts: Not silly at all. Sixy Sudoku puzzles are printed ever week in the Sunday New York Times magazine. Also, see here: amazon.com/… and page 67 here: issuu.com/paulguarino710/docs/nyt_magazine_-_09.22.2019 $\endgroup$
    – David G. Stork
    Commented Oct 8, 2019 at 6:15

1 Answer 1

Reset to default
2
$\begingroup$

As for the first question, a backtracking algorithm, see sixy.c at

https://github.com/wilberdk/sixy

shows there are 1936 completions of

$$\matrix{1&2&3&4&5&6\cr *&*&*&*&*& *\cr *&*&*&*&*&*\cr *&*&*&*&*&*\cr *&*&*&*&*&*\cr *&*&*&*&*&*&}$$

The answer to the second question is $n^*=7$. The answer to the third question is $908\,928$. These are more tricky. For instance, there are 2752 ways to chose five cells in

$$\matrix{ *&*&*&*&*& *\cr *&*&*&*&*& *\cr *&*&6&*&*&*\cr *&*&*&*&*&*\cr *&*&*&*&6&*\cr *&*&*&*&*&*}$$ to construct an initial clue like $$\matrix{ *&*&*&*&*& *\cr *&*&*&*&*& 1\cr *&*&6&*&2&*\cr *&3&*&*&*&*\cr *&4&*&*&6&5\cr *&*&*&*&*&*}$$ that ensures a unique solution. Here the construction fills the chosen cells with 1 through 5 consistent with the lexicographic order.

One sees that $n^*=7$ by replacing $$\matrix{ *&*&*&*&*& *\cr *&*&*&*&*& *\cr *&*&6&*&*&*\cr *&*&*&*&*&*\cr *&*&*&*&6&*\cr *&*&*&*&*&*}$$ with starting configurations that have just one filled cell. There is a symmetry group $G$ of order 128 with just three orbits of cells, and we tried all 6 times 3 orbits of configurations that have just one filled cell. The group $G$ is generated by the following three operations: turn the grid upside down; reflect the grid in the main diagonal; interchange the first two rows.

To be more specific about the answer to the third question, let us make some definitions. Call a clue valid, if it has seven filled cells and a unique solution. Given a valid clue, its core is obtained by deleting all integers that occur only once. The core size of a valid clue is the number of filled cells in its core. For instance the core size of $$\matrix{ *&*&*&*&*& *\cr *&*&*&*&*& 1\cr *&*&6&*&2&*\cr *&3&*&*&*&*\cr *&4&*&*&6&5\cr *&*&*&*&*&*}$$ is two. Possible core sizes are two, three and four.

One tries all $G$-orbits of possible cores.

There are $6!$ times $396\,800$ valid clues with core size 2 and they form $6!$ times $12\,242$ $G$-orbits.

There are $6!$ times $16\,000$ valid clues with core size 3 and they form $6!$ times $226$ $G$-orbits.

There are $6!$ times $496\,128$ valid clues with core size 4 and they form $6!/2$ times $5320$ orbits under a group which is twice as large as $G$.

$396800 + 16000 + 496128 = 908928$.

The programs we wrote for this task can be found at

https://github.com/wilberdk/sixy

Improve this answer
$\endgroup$
1
  • $\begingroup$ Hmmm... Could you show an $n^* = 7$ solution? And how have you shown $n^* \neq 6$? $\endgroup$
    – David G. Stork
    Commented Oct 11, 2019 at 15:09

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .