Tag: sudoku

Via the Arcadian functor I learned of the existence of the Sudokube (picture on the left).

Sudokube is a variation on a Rubik’s Cube in which each face resembles one-ninth of a Sudoku grid: the numbers from one to nine. This makes solving the cube slightly more difficult than a conventional Rubik’s Cube because each number must be in the right place and the centre cubies must also be in the correct orientation.

A much more interesting Sudoku-variation of the cube was invented two weeks ago by one of my freshmen-grouptheory students and was dubbed the mini-sudokube by him. Here’s the story.

At the end of my grouptheory course I let the students write a paper to check whether they have research potential. This year the assignment was to read through the paper mini-sudokus and groups by Carlos Arcos, Gary Brookfield and Mike Krebs, and do something original with it.

Mini-Sudoku is the baby $2 \times 2 $ version of Sudoku. Below a trivial problem and its solution

Of course most of them took the safe road and explained in more detail a result of the paper. Two of them were more original. One used the mini-sudoku solutions to find solutions for 4×4 sudokus, but the most original contribution came from Ibrahim Belkadi who wanted to count all mini-sudokubes. A mini-sudokube is a cube with a mini-sudoku solution on all 6 of its sides BUT NUMBERS CARRY OVER CUBE-EDGES. That is, if we have as the mini-sudoku given by the central square below on the top-face of the cube, then on the 4 side-faces we have already one row filled in.

The problem then is to find out how many compatible solutions there are. It is pretty easy to see that top- and bottom-faces determine all squares of the cube, but clearly not all choices are permitted. For example, with the above top-face fixed there are exactly 4 solutions. Let ${ a,b } = { 1,4 } $ and ${ c,d } = { 2,3 } $ then these four solutions are given below

Putting one of these solutions (or any other) on a $4 \times 4 $-Rubik cube would make a more interesting puzzle, I think. I’ve excused Ibrahim from having to take examination on condition that he writes down what he can prove on his mini-sudokubes by that time. Looking forward to it!

Here is
a ‘difficult but not unsolvable’ Sudoku from David Eppstein‘s paper Nonrepetitive paths and cycles
in graphs with application to Sudoku.

$\begin{sudoku-block} |5| | | | |1| | |8|. | | | | | | |6| | |.
| | | | |6|2|5|7| |. | |9| |2| |5|1| | |. | | |4| |1| |3| | |. | |
|8|3| |9| |2| |. | |7|6|9|8| | | | |. | | |5| | | | | | |. |8| | |1|
| | | |3|. \end{sudoku-block}y1 $

As always I try to solve
Sudokus without having to use backtracking (that
is, making a guess and working from there on to a solution or a
contradiction in which case one uses the other option). Clearly, this is
not well defined. When one starts solving Sudokus one often resorts to
backtracking but after a while one discovers rules which seem to avoid
backtracking (but in a sense are still). For example, if two cells in a
same block (or row or column) can only be filled with two numbers one
can use this fact by forbidding other numbers to occupy those cells.
However, this is a mini-backtracking strategy. Still, I allow all such
rules. More precisely, any formal rule is non-backtracking in my
dictionary. In Eppstein’s paper there is a good summary of the rules
most people apply when starting a Sudoku. He calls them the ‘local
rules’. Here they are

• If a digit x has only one remaining
  cell that it can be placed in, within some row, column, or square, then
  we place it in that cell. Any potential positions of x incompatible with
  that cell (because they lie in the same row, column, or square) are
  removed from future consideration.
• If a cell has only one
  digit x that can be placed in it, we place x in that cell. Incompatible
  positions for x are removed from future consideration.
• If
  some three cells, formed by intersecting a row or column with a square,
  have three digits whose only remaining positions within that row,
  column, or square are among those three cells, we prevent all other
  digits from being placed there. We also remove positions for those three
  forced digits outside the triple but within the row, column, or square
  containing it.
• If the cells of a square that can contain a
  digit x all lie in a single row or column, we eliminate positions for x
  that are outside the square but inside that row or column. Similarly, if
  the cells that can contain x within a row or column all lie in a single
  square, we eliminate positions that are inside that square but outside
  the row or column.
• If two digits x and y each share the same
  two cells as the only locations they may be placed within some row,
  column, or square, then all other digits must avoid those two cells.
• If the placement of digit x in cell y can not be extended to a
  placement of nine copies of x covering each row and column of the grid
  exactly once, we eliminate cell y from consideration as a placement for
  x.
• If the placement of a digit x in cell y within a single
  row, column, or square can not be extended to a complete solution of
  that row, column, or square, then we eliminate that placement from
  consideration.

But even if one manages to use all
these rules (and frankly I only use a subset) one might get stuck. I
don’t know how many cells you can fill in the above problem with these
local rules, I’m afraid I only managed $5 $… At such
moments, the bivalue Sudoku-graph may come in handy. Eppstein defines
this as follows

In this graph, we create a vertex
for each cell of the Sudoku grid that has not yet been filled in but for
which we have restricted the set of digits that can fill it to exactly
two digits. We connect two such vertices by an edge when the
corresponding two cells both lie in a single row, column, or square, and
can both be filled by the same digit; the label of the edge is the
digit they can both be filled by.

Eppstein then goes
on to define new rules (each of which is a mini-backtracking strategy)
which often help to crack the puzzle. Here are Eppstein’s ‘global
rules’

• If an edge in the bivalue graph belongs to a
  nonrepetitive cycle, the digit labeling it must be placed at one of its
  two endpoints, and can be ruled out as a potential value for any other
  cell in the row, column, or square containing the edge.
• If
  the bivalue graph has a cycle in which a single pair of consecutive
  edges has a repeated label, that label can not be placed at the cell
  shared by the two edges, so that cell must be filled by the other of its
  two possible values.
• If the bivalue graph contains two
  paths, both starting with the same label from the same cell, both
  ending at cells in the same row, column, or square, and such that in the
  two ending squares the values not occurring on the incident edge labels
  are equal, then the cell at the start of the paths can not be filled by
  the start label of the paths, and must be filled by the other of its two
  possible values.

For example, in the above problem it
is not hard to verify that the indicated places X,Y and Z form a
nonrepetitive cycle in the bivalue graph so applying the first global
rule we have two choices of filling these places (one leading to a
solution, the other to a contradiction)

$\begin{sudoku-block} |5| | | | |1| | |8|. | | | | | | |6| | |.
| | | | |6|2|5|7| |. | |9| |2| |5|1| | |. | | |4| |1| |3| | |.
|X|Y|8|3| |9| |2|Z|. | |7|6|9|8| | | | |. | | |5| | | | | | |. |8| |
|1| | | | |3|. \end{sudoku-block}y2 $

In fact, it turns out
that making this choice is enough to solve the puzzle by simple local
rules. So, if I change the original puzzle by filling in the cell X

$\begin{sudoku-block} |5| | | | |1| | |8|. | | | | | | |6| | |.
| | | | |6|2|5|7| |. | |9| |2| |5|1| | |. | | |4| |1| |3| | |. |6|
|8|3| |9| |2| |. | |7|6|9|8| | | | |. | | |5| | | | | | |. |8| | |1|
| | | |3|. \end{sudoku-block}y3 $

you will have no problem
solving the puzzle.

As a
quick reply to last posts comment :

Another
interesting question: How many clues (numbers allready in the grid) do
we need a Sudoku puzzle to have in the beginning in order to obtain a
unique solution? Comment by A.R.Ray

At
least one student proved that in micro-Sudoku (on a 4×4 grid)
one needs just 4 hints to get any unique solution (and that 4 is
minimal). It is an application of the fact that the micro-Sudoku group
acts on the set of all solutions with just two orbits so one needs to
check just these two solutions…