Create simple backtracking solver

[DylanSp]

Use basic techniques, just test on 4x4 and 9x9 boards

[DylanSp]

Summary of solver algorithm from Norvig post:

1. Apply basic strategies:
   1. If a cell's value is known, eliminate that value as a possibility from its peers.
   2. if there's only one possible place for a value in a house, fill it in.
2. If there are still unknowns remaining - apply recursive backtracking search, where each search step tries a possible value for an unknown cell and checks if it creates a solution or a contradiction. Once this fills a cell, go back to step 1.

[DylanSp]

I'll probably want to make a Set[T] struct for easily representing sets of possible values that's more ergonomic than map[T]struct{}.

• Struct will have an underlying map[T]struct{}.
• Methods (probably, introduce as needed):
  • Add(element T)
  • Has(element T) bool
  • Delete(element T)
  • Clear() - remove all elements
  • Entries() []T (not sure on name) - return all elements in the set
• Make sure the zero value of the struct is valid for all methods (the zero value of a map is nil, so initialize it to an empty map if it's nil).

[DylanSp]

When designing the needed data structures for representing the grid, possible solutions, and so on - look at ideas from Philosophy of Software Design, such as "Design it twice".

[DylanSp]

Data structures from Bendersky's codebase:

• https://github.com/eliben/go-sudoku/blob/main/sudoku.go#L13-L14 - how a grid is indexed
• https://github.com/eliben/go-sudoku/blob/main/sudoku.go#L29-L53 - various data structures for values, houses (he calls them "units"), peers, etc.

[DylanSp]

Set[T] struct added in https://github.com/DylanSp/sudoku-toolkit/commit/4a23e237fe6c48846aa79a90e5f10890f1b87230.

[DylanSp]

Parser for 4x4 puzzle added in https://github.com/DylanSp/sudoku-toolkit/commit/36b3d89db3d31620600231c450fde165ca762d26, as well as some examples, for easier testing.

[DylanSp]

As of https://github.com/DylanSp/sudoku-toolkit/commit/94665c4fb7b1083e2eee4444868d5271fc69eb7f, I've implemented a solver that works with just the basic strategies (eliminating all possibilities that are already on the board, filling in cells with only a single possible value). This works correctly for the 4x4 example puzzles and the first 9x9 puzzle in easy50.txt, so its logic is correct. It's not sufficient to solve the second 9x9 puzzle in easy50.txt, so that can be used to test the backtracking solver.

[DylanSp]

Started working on backtracking search in https://github.com/DylanSp/sudoku-toolkit/commit/22240a768f536b35c96d7cbd6e02352059ab878d - needs to be able to detect when a chosen search path has lead to a contradiction (some empty cell has no remaining valid possibilities), then return false in that case.

Probably create a function to check if a puzzle has a contradiction (figure out a better name), call it at this point in the search loop - https://github.com/DylanSp/sudoku-toolkit/blob/main/sudoku/solver.go#L76.

[DylanSp]

As of https://github.com/DylanSp/sudoku-toolkit/commit/2ffce05d6533f7b6233ce425ffe383142bbbf3f4 on the immutable-puzzle branch, backtracking search works on all puzzles in the easy50 list, though there's a point where I apparently have incorrect assumptions about my code's behavior - I want to understand that before merging into main.