The New Sudoku Players' Forum

[Mathimagics]

Surendra asked about solving Kakuro by "pure logic" (cf. this thread).

Now we all agree that pure logic vs trial-and-error is a somewhat fuzzy area, but it occurred to me that when it comes to software, we can be a little more definitive.

I decided to experiment with a stripped down DFS solver, using these simple data structures:

• Grid(R,C) (contains cell values)

• Domain(R,C,N) ( 1 if cell can be N, otherwise 0)

• Hsum(R,C) (horizontal sum for cell)
  Vsum(R,C) (vertical sum for cell)

This elementary DFS solver has a domain-shaver that uses just one test function, CanBe(R,C,N), which returns 1 if this cell can be N. This function tests the horizontal and vertical runs containing the given cell, using the current domains, to see if there is at least one combination of values which has N in position R,C.

So this solver has no "frills" like hidden/naked pairs, triples, etc.

I then ripped out the recursion, leaving a purely iterative solver that just keeps shaving until it draws blood - ie. nothing changes. If all cells are set, it has a solution, otherwise it fails.

An interesting question now arises - can we take any well-formed puzzle (that has a unique solution), and change the clues (sums) so that the puzzle becomes pure, ie. that can be solved by this simple process?

[Mathimagics]

The answer appears to be yes.

I have found "pure" puzzles for all minimal template forms for grid sizes up to 14 x 14. These minimal forms are grids with the bare minimum of black cells.

I have also tested 124 grids (size 24 x 14) that I lifted from a book of "absolutely nasty" Kakuro puzzles, and found pure puzzle forms in all cases. What is really interesting is that the pure puzzles seem to be just as difficult.

This seems to indicate that puzzle difficulty is dependent on both form (grid layout) and content.

The pure puzzles are a reasonable indicator of minimum difficulty.