Main Page - Back

A Set Theory Approach to Sudoku Strategies

From sudokuwiki.org, the puzzle solver's site
breakline

Abstract: 'Generalizing Sudoku Strategies'

View Paper
View Paper
Numerous strategies exist for solving Sudoku puzzles, often given evocative names such as “X-wing” and “Swordfish”. Many of these strategies consider specific configurations or states of the Sudoku puzzle. As such, many are related.

This paper seeks to define a smaller set of more generalized strategies, which make the relationship among some of the named strategies more explicit, suggest other strategies for solving puzzles, and offer a path to simplify Sudoku solvers.

Using set notation, this paper defines six generalized strategies which encompass sixteen or more individual strategies. These generalized strategies may be implemented in computerized algorithms.

The paper concludes with some thoughts on ranking puzzle difficulty, and on open questions involving the completeness and efficiency of Sudoku solution strategies.

by Kevin Gromley, March 2014



This is a fascinating paper by Kevin Gromley who has set out a way to group families of logical strategies based on 'constraint sets'. I'm not nearly mathematical enough to appreciate the set theory formulas but we have exchanged ideas about the conclusions of this paper and discussed some of the open questions. I'd like to pick out a few points and write about them here.



Time by Clue Density
Time by Clue Density

I knocked up a quick graph to show the very rough relationship between logical strategies and brute-force - the two competing approaches to finding solutions. Brute Force is incredibly fast at high numbers of clues. I've dropped in 17 as the minimum number of clues on a normal Sudoku - my implementation can take a few seconds on these puzzles. The 8 is the smallest number of clues in a Jigsaw Sudoku - expotentialism takes over and I've never waited long enough to see how long it takes.

The straight green line should be a rather hazy line because clue density has almost no bearing on the complexity of the puzzle except in the gross sense of less or more availability for steps. There are trivial 17 clue puzzles and horrendous 30 clue ones. But logical strategies only take 5-10 seconds on the hardest puzzles and so the time spread is fairly flat.

- Andrew Stuart