---

Footprint

Definitions

The footprint of a pattern of solved cells is a list of 27 sets, where:

• set 1 = values in row 1 of the pattern
• set 2 = values in row 2 of the pattern
• ...
• set 9 = values in row 9 of the pattern
• sets 10-18 = values in columns 1-9 of the pattern
• sets 19-27 = values in boxes 1-9 of the pattern

A solution to a given footprint is any assignment of values to cells that has the prescribed row/column/box memberships.

A pattern whose footprint has more than one solution is unavoidable (and conversely).

Example

The unavoidable set ...

1  .  .  |  2  .  .  |  .  .  .
2  .  .  |  3  .  .  |  .  .  .
3  .  .  |  1  .  .  |  .  .  .
---------+-----------+---------
.  .  .  |  .  .  .  |  .  .  .
.  .  .  |  .  .  .  |  .  .  .
.  .  .  |  .  .  .  |  .  .  .
---------+-----------+---------
.  .  .  |  .  .  .  |  .  .  .
.  .  .  |  .  .  .  |  .  .  .
.  .  .  |  .  .  .  |  .  .  .

... has footprint

• {1,2} in row 1
• {2,3} in row 2
• {1,3} in row 3
• {1,2,3} in column 1
• {1,2,3} in column 4
• {1,2,3} in box 1
• {1,2,3} in box 2
• (all other rows, columns and boxes empty)

This footprint has two solutions: the one given above, and this:

2  .  .  |  1  .  .  |  .  .  .
3  .  .  |  2  .  .  |  .  .  .
1  .  .  |  3  .  .  |  .  .  .
---------+-----------+---------
.  .  .  |  .  .  .  |  .  .  .
.  .  .  |  .  .  .  |  .  .  .
.  .  .  |  .  .  .  |  .  .  .
---------+-----------+---------
.  .  .  |  .  .  .  |  .  .  .
.  .  .  |  .  .  .  |  .  .  .
.  .  .  |  .  .  .  |  .  .  .

The two solutions are sometimes described as dual (but the terminology is not standardised).

This page was last modified 19:07, 29 December 2006.  

---