Skip to main content
4 of 21
added 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

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

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