Footprint

From Sudopedia
Jump to navigationJump to search

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