Human Strategies

[Emerentius]

The crate should contain a new public struct for solving sudokus like a human would. This struct is to contain additional information about the state of the sudoku, that allow efficient application of the various strategies. An example would be a cache of the possitions that are still possible for a certain number in a row, column or block so that one does not have to iterate over the entire grid.

It should be possible to supply a set of strategies at runtime i.e. as a Vec<Strategy> and have it solve the sudoku using only these and return the finished sudoku or however far it got. It should also be possible to simply get a hint, i.e. the result of one strategy being applied only once. The hint should carry the reason why the deduction is valid and not just a set of deduced entries or impossibilities.

I have started work on this in the strategy_solver branch. So far 8 strategies (8 structs) are implemented (not yet unit tested) and a solver that drives the sudoku to completion with the given strategies.

Todo: - [ ] Decide on function signature of Strategy trait

• [x] Decide how to Implement hinting
  • [x] single hinting
  • [x] full solution as series of deduction steps
• [x] Clean up API and publish v0.7

After that comes the eternal task of implementing more strategies (here is an overview)

[Emerentius]

The Strategy trait and the attempt to use generators have proven to be more hassle than they are worth. Instead I'm going to use a Strategy enum. The current state of the sudoku and all of its properties (possible digits in cells, possible digits in rows/cols/boxes etc.) are stored in a struct together with a history of all deductions and what strategies were used to get there. The properties are lazily updated from the history so that caches for unused strategies do not end up costing runtime. The pooling avoids duplicate computations for different strategies.

A strategy must support two operations:

1. Find one deduction
2. Find all deductions (can be optimized)

Outlining of of the reasoning at each step can be added later. For now this will only solve the sudoku and give a sequence of strategies that were successful. This is enough for basic difficulty grading.

[Emerentius]

Prior work:

• SudokuExplainer Java An old and powerful, but slow solver. Is the standard rater in the patterns game (goal: generating maximally difficult sudokus with some pattern) on forum.enjoysudoku.com. Has been the basis for some later raters. SE itself is a GUI program. serater is a CLI built on it.

• Hodoku Java Another powerful GUI program. No idea about speed.

• Andrew Stuart's sudoku solver Javascript; http://www.sudokuwiki.org/sudoku.htm A web solver. Contains many strategies but fails on some of the harder sudokus. No idea about speed, but probably not peak performant given that it's in JS.

• skfr C++ Based on SudokuExplainer but expanded to check more solution paths to find shorter paths. Also much faster (>100x). Similar ratings but sometimes a little lower, rarely a bit higher.

• 2 more solvers based on skfr by same author C++ even faster

[Emerentius]

A first prototype is now published. Future extensions and API improvements will still come, but this issue won't be open to cover this neverending task.