In this article, we hypothesize that non-obvious and yet fundamental constraints (“second-order constraints”), emerging from obvious rules (“first-order constraints”), may help solve computationally intractable puzzles.

Puzzles as Constraint-Logic Games

Puzzles can be defined as one-player constraint-logic games (Hearn, Robert A., and Erik D. Demaine. Games, Puzzles, and Computation. AK Peters, 2009, p. 55). Generally speaking, these constraints are “rules defining legal moves” (Hearn, Robert A. Games, Puzzles, and Computation. Ph.D. dissertation, Massachusetts Institute of Technology, 2006, p. 18) toward a solution.

Hearn and Demaine use this terminology in the context of constraint graphs. For our demonstration, we place it in the general context of constraint satisfaction. On this basis, it is an apparent fact that, the more a puzzle is constrained, the more it is solvable efficiently: each constraint diminishes the size of the search space.

First-Order Constraints

The core rules of a puzzle are what I would like to call “first-order constraints.” They are defining the game itself.

Let’s take a 9x9 Sudoku square as an example. Its rules are well known (Knuth, Donald Ervin. The Art of Computer Programming. Addison-Wesley, 2020, vol. 4, fascicle 5, p. 72):

• “every row contains each of the digits [1 to 9] exactly once;
• every column contains each of the digits [1 to 9] exactly once;
• every box contains each of the digits [1 to 9] exactly once.”

By definition, these rules constitute first-order constraints: they are used for solving the puzzle (by pruning the search space); they validate that a puzzle has been solved.

TetraVex, an edge-matching puzzle, is characterized by the following first-order constraints:

• all tiles have to be placed on the grid (one tile per location), each exactly once;
• tiles cannot be rotated;
• edges of adjacent tiles must match (by color, number, or pattern).

First-order constraints are enough to verify whether a puzzle has been solved or not.

When the size and complexity of a game are computationally tractable, simple backtracking solvers can solve them in a reasonable time. They are using first-order constraints not only at the verification stage (to verify that the puzzle has been solved) but also to reduce the size of the search tree during the solving process (e.g., for a TetraVex solver: for the next node, only select tiles which are edge-matching the current one).

Direct Optimizations and Use of Heuristics

To be more efficient, solvers are generally optimized. They can notably:

• Use parallel and memory-aware algorithms;
• Pre-compute data (for instance, create 2x2 TetraVex tiles);
• Use heuristics, based on the study of the behavior of a given algorithm (e.g., Algorithm X’s minimum-remaining-values heuristic: Knuth, Donald Ervin. The Art of Computer Programming. Addison-Wesley, 2020, vol. 4, fascicle 5, p. 67). (Side note: this is particularly true for genetic algorithms).

Solvers optimized that way are generally very efficient. However, they fail to solve puzzles that are deemed intractable due to their size. Over a certain threshold, they cannot solve in a reasonable time.

Indirect Optimization: Translate, then Solve

An advanced solving technique is the translation (or encoding, or conversion, …) of a puzzle into another class of problem. It offers the advantage of the possibility to use solvers dedicated to solving the latter. In other words, the general idea is to benefit from these highly optimized solvers. This is an indirect optimization: instead of optimizing the solver itself, the solving process is delegated to another tool or algorithm.

A Sudoku can be translated into a propositional formula (typically into the CNF format) to be solved by a SAT-solver (e.g., zChaf). It can also be encoded into a binary matrix solvable by algorithm X/dancing links. A Sudoku can additionally be solved by being translated into a graph. (Another example can be given with Instant Insanity, easily solvable after having been translated into a graph).

In other words and respectively, a Sudoku can be translated into a propositional satisfiability problem, an exact cover problem, or a graph coloring problem, then solved accordingly.

Intellectually stimulating for modest puzzles, this approach has its limits. Larger puzzles are translated into large objects: they produce large formulas, matrices, graphs, etc. The translation does not reduce per se the complexity of the original representation of a puzzle.

It is just another representation of an NP-complete problem. You had one problem. Now, you have two.

Intractable Puzzles

Example of 256-pieces edge-matching puzzle (source)

First-order constraints, even supplemented with direct optimization and/or translation into other problems, are insufficient to solve some puzzles because of the combinatorial explosion.

Eternity 2, a puzzle launched in 2007, is a perfect illustration: this 256-piece edge-matching puzzle has still not been solved. It is intractable.

Its first-order constraints are:

• all 256 tiles have to be placed on the board (one tile per location), each exactly once;
• edges of adjacent tiles must match (by pattern);
• tiles adjacent to the board must edge-match the board (corners, borders).

There is also a rule that distinguishes it from TetraVex puzzles: its tiles can be rotated. This rule can be formulated as a constraint:

• each tile has to be rotated at 0°, 90°, 180°, or 270°.

Considerable computing and brain power have been thrown into this NP-complete problem. Sophisticated solvers have been created, greatly optimized for parallelism, allowing some mismatches between the edges to reach an optimal overall score, etc. But none of them has been able to solve it.

Some people have suggested translating Eternity 2 into a SAT problem, a binary matrix, a graph, etc., à la Sudoku. In our opinion, merely translating this puzzle and using solvers dedicated to these classes of problem just translates this intractable edge-matching problem into an intractable SAT/exact cover/graph problem.

We are optimistic that this puzzle can be solved but differently, by discovering and using constraints complementary to the first-order ones.

We call them “second-order constraints.”

Second-Order Constraints

Second-order constraints can be defined as non-obvious constraints that are emerging from the first-order ones. They are as fundamental yet can go unnoticed. They are implicit but necessary rules.

The following table compares these two classes of constraint.

Sudokus give an example of a second-order constraint: the Phistomefel Ring. In a solved Sudoku, the numbers in the central ring are always the same as in the four corners, as illustrated by this image (in this instance, both corners and ring contain the numbers { 1, 1, 2, 2, 2, 3, 4, 4, 5, 5, 6, 7, 7, 8, 8, 9 }):

An illustration of a Phistomefel Ring (source)

This singular characteristic is demonstrated in a video.

The Phistomefel Ring second-order constraint, inherent to all Sudokus, is so non-obvious that it has been discovered in 2020 while modern Sudokus exist since 1979. It has always been there, but nobody noticed it for several decades.

Detecting Second-Order Constraints

The Phistomefel Ring has been discovered by someone searching for patterns. According to its discoverer: “I was pondering a bit about the geometry of the Sudoku grid the other day and came across an interesting find.” (Source in German).

This interesting find is the observation of the existence of an invariant—the equality between two sets (ring = corners) of numbers. In other words: observationally, second-order constraints are non-obvious invariants in solved instances of a puzzle.

The existence of second-order constraints inherent to puzzles deemed intractable as Eternity 2 is an open question.

If they exist, they have not been found yet. Or, if some of them have been found, they are not critical enough to solve the puzzle.

A pessimistic view would conclude that this puzzle does not contain any second-order constraint. A more optimistic stance (ours) believes that Eternity 2 contains several of them, but they remain latent.

To reveal them, one approach could be to purposely study solved Eternity 2-like puzzles. Edge-matching puzzles similar to Eternity 2 could be randomly generated; then, an algorithm could try to detect invariants in these instances; finally, a puzzle would be solved using both first-order and second-order constraints.

The nature of this algorithm (basically: a second-order constraints detector) is unknown, though. At this stage, it is purely speculative. But it is probably worth investigating. In particular—and before tackling the gargantuan Eternity 2 puzzle—it would be interesting to test this hypothesis by constructing an algorithm able to detect by itself the Phistomefel Ring (alongside potential other second-order constraints) in Sudokus.