1: 88 patterns 2: 43 patterns 3: 62 patterns 4: 92 patterns 5: 62 patterns 6: 107 patterns 7: 70 patterns 8: 43 patterns 9: 48 patternsNow one can turn a Sudoku puzzle into a jigsaw puzzle: make pieces for all possible digit patterns, and find one piece for each digit such that these pieces fit together and form the 9x9 grid.

Note that generating all possible patterns for each digit involves nine backtrack searches.

The numbers of possible patterns are smaller than in the example above (because there are more givens) but is still a bit large:

1: 32 patterns 2: 28 patterns 3: 9 patterns 4: 90 patterns 5: 3 patterns 6: 9 patterns 7: 12 patterns 8: 5 patterns 9: 16 patternsDo first some easy work, to get to

And now:

1: 7 patterns 2: 6 patterns 3: 1 pattern 4: 7 patterns 5: 2 patterns 6: 4 patterns 7: 2 patterns 8: 1 pattern 9: 10 patternsThat looks manageable, 40 jigsaw pieces. How to represent them?

4ab 6a |
8 | 1ab 4cd 9abcdefgh |
3 | 4efg 6bc |
2 | 5a 9ij |
1cde 7a |
1fg 5b 6d 7b |

1c 2ab 6bd |
5 | 1defg 2cdef |
7 | 9 | 8 | 4 | 3 | 1ab 6ac |

3 | 4efg 6c 9ij |
7 | 1 | 4abcd 6ad |
5 | 8 | 2acd 9abcd |
2bef 6b 9efgh |

1adf 5b 9aei |
1bceg 9bf |
8 | 6 | 2 | 7 | 3 | 4acef 9ghj |
4bdg 5a 9cd |

2ce 4cde 5a |
7 | 2ab 4abfg |
9 | 3 | 1 | 2df 5b |
6 | 8 |

2df 6c 9cgj |
6abd 9dh |
3 | 5 | 8 | 4 | 1 | 2be 7b 9efi |
2ac 7a 9ab |

1beg 4fg 9bdfh |
1adf 4abcd 9aceg |
5 | 2 | 7 | 3 | 6 | 8 | 1c 4e 9ij |

8 | 2 | 6 | 4 | 1 | 9 | 7 | 5 | 3 |

7 | 3 | 1c 4e 9ij |
8 | 5 | 6 | 2abce 9abcdefgh |
1abfg 2f 4bdg |
1de 2d 4acf |

The original Sudoku is a graph colouring problem. Here we have a clique-finding problem: find the unique 9-clique in the graph where compatible jigsaw pieces are joined. Two pieces are compatible when they do not overlap. (And both graph colouring and clique-finding are difficult in general.)

In the above example, positions (6,1) and (9,7) cover all 2-patterns
(that is, form a vulnerable 2-pair) and hence patterns `9c` and
`9g` are impossible. Positions (1,7) and (4,1) form a vulnerable 5-pair,
showing that `9i` is impossible.

Since `2abcdef` and `2abce9abdefh` (by (9,7)), we have
`2df = 9abdefh`. By (6,1) it follows that `2df6c9j`,
that is, `6c9abdefhj`. Since `9abdefhj` it follows
that `6c` is impossible.

Since `6abd` and `6abd9dh` (by (6,2)),
`9d` and `9h` are impossible.

By (3,8) we have `2acd9ab`. Now `2df = 9abef`
and `2bef = 9ab`, so that `2df` includes `2bef`,
and `2b` and `2e` are impossible, and
we have `2f = 9ab` and `2d = 9ef` and `9j = 2ac`.

From `2ac9abef` and `2ac7a9ab` (by (6,9))
it follows that `7a = 9ef` and `7b = 2ac9ab`.

From `5ab` and `5b9abef` (by (5,6))
it follows that `5a = 9abef` and `5b = 2ac`.
But `1fg5b6d7b` by (1,9), that is, `1fg2aacc6d9ab`.
By the 'precisely one' clause, this means that `2a` and `2c`
(and `9j`) are impossible. And hence `5a` is the right 5-pattern.

From `4abcdefg` and `4efg` (by (3,2))
and `4acef` (by (4,8)) and `4abfg` (by (5,3))
it follows that `4f` is the right 4-pattern.

From `1beg4f9bf` (by (7,1)) and `1de4f9ef` (by (9,9))
it follows that `1b`, `1d`, `1e`, `1g`,
`9b`, `9e`, `9f` are all impossible.

Examining what is left, we see `9a`, `6a` and `1c`.
Altogether, the solution to our puzzle is
`1c`, `2f`, `3`, `4f`, `5a`,
`6a`, `7b`, `8`, `9a`.

For a frightening example, see Taking on a killer Tso ... .