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.

## Comments