Footprint
From Sudopedia
Jump to navigationJump to searchDefinitions
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).