Skip to main content
21 of 21
deleted 1 character in body
David G. Stork
  • 2.6k
  • 1
  • 21
  • 37

Number of solutions and minimal clues in Sixy Sudoku

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.

David G. Stork
  • 2.6k
  • 1
  • 21
  • 37