Old Human Solve

Note this is an old description of how HumanSolve used to work back when we did this overly-complex branching thing for Guesses where we solved each branch earnestly. That turns out to be unnecessarily dumb because it made the machinery very complex and we never really proved to the user that we had done the branching anyway. The new method is to solve the puzzle via brute force and just pick the guess that we know will turn out to be right. This documentation is kept for historical value.

The HumanSolve method is very complex due to guessing logic. Without guessing, the approach is very straightforward. Every move either fills a cell or removes possibilities. But nothing does anything contradictory, so if they diverge in path, it doesn't matter--they're still working towards the same end state (denoted by @)

                   |
                  /|\
                 / | \
                |  |  |
                \  |  /
                 \ | /
                  \|/
                   |
                   V
                   @

In human solve, we first try the cheap techniques, and if we can't find enough options, we then additionally try the expensive set of techniques. But both cheap and expensive techniques are similar in that they move us towards the end state.

For simplicity, we'll just show paths like this as a single line, even though realistically they could diverge arbitrarily, before converging on the end state.

This all changes when you introduce branching, because at a branch point you could have chosen the wrong path and at some point down that path you will discover an invalidity, which tells you you chose wrong, and you'll have to unwind.

Let's explore a puzzle that needs one branch point.

We explore with normal techniques until we run into a point where none of the normal techinques work. This is a DIRE point, and in some cases we might just give up. But we have one last thing to try: branching. We then run the guess technique, which proposes multiple guess steps (big O's, in this diagram) that we could take.

The technique will choose cells with only a small number of possibilities, to reduce the branching factor.

                  |
                  |
                  V
                  O O O O O ...

We will randomly pick one cell, and then explore all of its possibilities. CRUCIALLY, at a branch point, we never have to pick another cell to explore its possibilities; for each cell, if you plug in each of the possibilites and solve forward, it must result in either an invalidity (at which point you try another possibility, or if they're all gone you unwind if there's a branch point above), or you picked correctly and the solution lies that way. But it's never the case that picking THIS cell won't uncover either the invalidity or the solution. So in reality, when we come to a branch point, we can choose one cell to focus on and throw out all of the others.

                  |
                  |
                  V
                  O

But within that cell, there are multiple possibilty branches to consider.

                  |
                  |
                  V
                  O
                 / \
                1   3
               /     \
              |       |

We go through each in turn and play forward until we find either an invalidity or a solution. Within each branch, we use the normal techniques as normal--remember it's actually branching but converging, like in the first diagram.

                  |
                  |
                  V
                  O
                 / \
                1   3
               /     \
              |       |
              X       @

When we uncover an invalidity, we unwind back to the branch point and then try the next possibility. We should never have to unwind above the top branch, because down one of the branches (possibly somewhere deep) There MUST be a solution (assuming the puzzle is valid) Obviously if we find the solution on our branch, we're good.

But what happens if we run out of normal techinques down one of our branches and have to branch again?

Nothing much changes, except that you DO unravel if you uncover that all of the possibilities down this side lead to invalidities. You just never unravel past the first branch point.

                  |
                  |
                  V
                  O
                 / \
                1   3
               /     \
              |       |
              O       O
             / \     / \
            4   5   6   7
           /    |   |    \
          |     |   |     |
          X     X   X     @

Down one of the paths MUST lie a solution.

The search will fail if we have a max depth limit of branching to try, because then we might not discover a solution down one of the branches. A good sanity point is DIM*DIM branch points is the absolute highest; an assert at that level makes sense.

In this implementation, humanSolveHelper does the work of exploring any branch up to a point where a guess must happen. If we run out of ideas on a branch, we call into guess helper, which will pick a guess and then try all of the versions of it until finding one that works. This keeps humanSolveHelper pretty straighforward and keeps most of the complex guess logic out.