Skip to main content

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

A naive loose upper-bound on the number of valid filled grids, $K$, is to consider each of the remaining shaded rectangles as independent, giving $(6!)^5$ solutions. (The same logic applies to considering independent rows, or independent columns, or independent outlined rectangles.) But of course that bound will be extremely loose because it does not incorporate the many constraints.

A slightly tighter bound can be found by considering the left set of three shaded rectangles as independent, and then adding the row constraint for each aligned shaded rectangle on the right. In that way we get $(6!)^2 ((3!)^2)^3$. But of course that bound does not include all the constraints, such as the column constraint. A tight bound on the number of bits needed to specify a problem (initial cell specifications) having a unique solution is $\log_2 K$.

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^3$ alternatives (given all constraints), and the second row has $2^2$ alternatives. The third row has $2^2$ 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$.

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$.

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