After doing some research
& experimentation, I have come to the conclusion that using
simply 3 generic rules, the vast majority of Sudoku can be solved
efficiently programmatically. Many online sites list dozens of solution
strategies, however the majority of the strategies are usually instances
of one of the three generic approaches.
These reudctions have the greatest use for creating Sudoku. Many
creation algorithms call for 'placing a number' followed by 'checking
to see if the board has a unique solution', if not, then 'placing
another number' etc. Using these three reducitons exclusively when
'checking to see if the board has a unique solution' can greatly
speed up Sudoku cration time.
Reduction 1 (Subset Reduction):
In an N^{2} x N^{2} grid, for each Row/Column/Block,
if there are K cells which together contain exactly K candidate
values, those candidates may be removed from all other cells in
that Row/Column/Block. Complexity: O(N^{4}*2^{N^2}).
This generalized rule covers the popular rules:
Naked Single/Pair/Triplet/Etc., Hidden Single/Pair/Triplet/Etc.,
Single/Double Block Line, Single Solution, Single Cell, Disjoint
Chain
Reduction 2 (Xor Reduction):
In an N^{2} x N^{2} grid, take any Row or Column
denoted P and a Block denoted B where C = P Ç
B and C > Ø. Any candidate values not represented within
the set PC can be removed from all items in the set BC. Likewise,
any values not represented within the set BC can be removed from
all items in the set PC. Complexity: O(N^{5}).
This generalized rule covers the popular rules:
Single Box, Intersection Removal, Pointing Pairs
Reduction 3 (Symbol Reduction):
In an N^{2} x N^{2} grid, for each possible value
V, if there are K rows which together contain exactly K possible
columns for the value V, then any other rows with candidates of
value V in those columns can have the candidates removed. This argument
can be applied to Columns as well. Complexity: O(2^{N+1}*(N^{2}
Choose N)). Symbol Reduction is only valid when applied directly
after Subset Reduction.
This generalized rule covers the popular rules:
XWing, Swordfish, Jellyfish, Squirmbag, 6Gronk, 7Gronk, NFish
Rules not covered directly by reductions 13:
Coloring, Remote Pairs, XYChains, Forcing Chains, Nishio, XY/XYZWing,
Aligned Pairs, Single Chains, YWing Chains
