| each row | permutation of { 1 … 9 } |
| each column | permutation of { 1 … 9 } |
| each 3x3 block | permutation of { 1 … 9 } |
| maybe | unique solution |
to solve: focus on cells/numbers, crosshatch, search/backtrack
notation
grid puzzle instance (aka position)
square cell
unit row, column, or block/box (aka hyperedge)
peers for each cell c, all others cells in some unit with c
solved grid each unit has permutation of digits 1 .. 9
representation
cross product to initialize units
units dictionary: for each cell c, list of all units containing c
peers dictionary: for each cell c, set of all cells (other than c) in some unit with c
grids
grid input puzzle instance
represented by string (faster copying)
values current (partial) solution status of grid
dictionary: for each cell, all possible values (as string, faster copying)
parsing from grid to values
zip function pairs each cell with its initial character value
constraint propagation
assign(values, c, d) ?
more clever than values[c] <- d
1) if cell c has value d, eliminate d from c's peers
2) if unit has unique remaining location for d, put d there
key observation
is fundamental op assigning a value to a cell?
no, fundamental op is eliminating a value for a cell
hence eliminate(values, c, d)
then assign(values, c, d) is eliminate all values for c except d
python: shallow copy, deep copy
shallow copy
immutable (eg. string) : create a separate copy
mutable (eg. list): provide another pointer
deep copy
mutable: create a separate copy (takes longer than shallow copy)
strings immutable, so shallow copy sufficient
lists with deep copy would be slower
that's why norvig used strings where he did
what if constraint propagation rules above aren't enough?
search !
recursive depth-first search, new copy of values for each call
alternative is backtracking: more complicated
in dfs
which cell c to try next? variable ordering
minimum remaining values heuristic
for that c, which value d to try next? value ordering
any order, e.g. consider values in order 1 .. 9