Algorithm X

Futoshiki Solver (Revisited)

Puzzle: Futoshiki Solver

Author: @Sundiver

Published Difficulty: Medium

Algorithm X Complexity: Great Confidence Builder

Strategy

The first time Futoshiki was discussed in this playground, a few key distinctions were made.

• Just like Sudoku, Futoshiki is a special kind of Latin Square.

• Inequalities allow for important problem-space reduction.

I think we all like to reuse code wherever possible. Here are a couple of conceptual ideas we know to be true:

In the final Sudoku Challenge, I suggested each cell having pointers to the groups to which it belongs. In Futoshki, each cell only belongs to a row and a column. There are no boxes. Rather than addressing this difference between a SudokuCell and FutoshikiCell, I suggest going back to the basic version of a SudokuCell that did not know about its groups. The basic version is plenty to completely solve all Futoshiki test cases.

The Futoshiki input is somewhat tougher to parse, but you can use your exact same Sudoku code to create n * n instances of the SudokuCell class. You can even use your previous code to create SudokuGroups for each row and each column of the Futoshiki grid. Keep in mind, Futoshiki does not have boxes (sub-grids) like Sudoku. These groups will be important if you hope to solve all the Futoshiki test cases completely with logic, but they are not necessary if you plan to do backtracking with Algorithm X.

What I am about to say should not be a surprise and I hope I have not made a mistake by not issuing a spoiler alert, but… the inequalities are really important. They are so important; I suggest you add another class to your object model.

Every Inequality needs two pointers. The first points to the SudokuCell that must be less than the other side. The second pointer points to the SudokuCell that must be greater than the other side. The only critical Inequality method is reduce_().

You will need to fill in the details of what it means to reduce an inequality. As you know, reduction in this type of puzzle is all about eliminating candidates from cells. What candidates can be eliminated from the cells on either side of the inequality based on the rules that govern how inequalities work?

Finally, I will copy the exact reduction code structure from the earlier Sudoku discussion into the FutoshikiSolver class constructor.

        finished_reducing = False
        while not finished_reducing:
            finished_reducing = True
            for inequality in self.inequalities:
                if inequality.reduce_():
                    finished_reducing = False

Test Case 2: Comparisons only horizontal and Test Case 3: Comparisons only vertical are the only two interesting test cases you can completely solve simply by reducing the problem space based on inequalities. However, this one small reduction effort puts Algorithm X in position to find solutions to all remaining test cases very fast.

As I alluded to earlier, a bit more than just basic SudokuGroup reduction logic is necessary to solve all test cases strictly with logic, no guessing, but it is very doable. If you would like to take on that challenge, I will get you started with the reduction loop, which probably does not come as a surprise by now.

        finished_reducing = False
        while not finished_reducing:
            finished_reducing = True
            for inequality in self.inequalities:
                if inequality.reduce_():
                    finished_reducing = False

            for group in rows + cols:
                if group.reduce_():
                    finished_reducing = False

Solving Logic Puzzles Logically

Many Futoshiki puzzles can be solved without making any guesses. Click here to see my progress toward solving as many logic puzzles as possible, strictly with logic, no guessing.