Constraint solving CrossCells puzzle game solution

Question

There's a puzzle game called CrossCells (not affiliated; there's also multiple other ones with the same kind of idea, but slightly different layout and rule set) that I've been playing on and off. After getting a bit frustrated with one puzzle (they're getting larger and larger and I'm not very methodical with solving them anymore) I thought of what environment I'd use to solve them automatically (brute force not being a great idea).

This is also kind of spoiler-ish for puzzle 25, though I'm not printing the full solution, you'd have to run the code to see it.

---

I set up a quick hack in Prolog (SWI Prolog using one of the constraint solving modules; apt-get install swi-prolog should do the trick) and wanted to get some feedback on the solution, especially regarding

• whether this the go-to approach for this kind of puzzle, or whether a more simple approach would work too,
• whether a different environment would be a much better match for the kind of problem (I'm not familiar enough with Prolog, but the documentation was enough to let me at least get this done in a matter of hours; I'd be more happy with, say, Java/Python/..., anything where I can still switch to an imperative mode for e.g. I/O).

For the specifics of the code also

• how this could be shortened while still being readable. It took quite a while (after one failed attempt at expressing the equations) to actually write down the whole puzzle in a readable way. E.g. not having to write down all the variables explicitly in the goal and when invoking it would be fantastic.
• Whether the equations could be more concise. I deliberately wrote them down row by row and column by column to be able to visually compare them with the game's representation. But, that comes at the cost of additional variables (Nx) and screen space.
• (削除) Printing and comparing the solution is cumbersome, any hints how this could be improved? (削除ここまで) Edit: The second goal solve now prints each row, yet I can't think of a good way to truly show this as the original grid pattern, making comparing it with the real thing still a bit annoying. Still happy to find a better way!

Edit: Since there was no answer yet I trimmed it down a bit myself, the noise is manageable now, focus would be more on how the equations could be simplified even more.

---

Okay so the rules of the game for this particular puzzle:

screenshot of unsolved puzzle 25 of the game CrossCells

(Red was edited on top just in case.)

• Each cell can be toggled on (highlighted in blue by default), toggled off (barely visible, same as the background basically) or undecided (what's shown in the picture, dark gray). This corresponds to the "term" in the cell being part of the expression, not being part of the expression, or undecided. Only if all cells in the sequence are either on or off can the constraint be satisfied or not; if any cell is still in undecided state, the puzzle is not solved yet. (In the solution there's no need to model the undecided state, we always assign either on or off to each cell.)
• Precedence is the usual, except that there's implied parentheses between each cell; e.g. the first row reads (((+ 1) + 2) * 4) + 2 = 4! If the first two cells were off, it would be essentially (((0) + 0) * 4) + 2 = 4 though.
• Each column, row and sub-square can have a constraint. Those are always after all cells in the sequence / at the boundary of the square. In this one there's 10 of those for columns and rows and one for the highlighted square ("[6] tiles").
• The constraints are either number of tiles allowed to be set in the sequence ("[1] tiles") or the total of evaluating the arithmetic expression made up of the chosen cells ("24 total").

Part of the problem of expressing this is that you can't simply write (for the first row) (1 * A + 2 * B) * 4 * C + 2 = 4 (given A-D as integers between 0 and 1), because if e.g. "x4" is off, it's simply not part of the expression, instead the full expression would read (+)1 + 2 ___ + 2 = 4 (not ((+)1 + 2) * 0 + 2 = 4).

(Hope I didn't forget to explain anything, showing this interactively would be a little bit easier. Here's one YouTube link; of course there are others too and it might disappear.)

---

So the solution below

• uses variables Bx as integers 0 or 1 to express whether a cell (numbered from top left to bottom right, row by row) is present or not,
• uses variables Nx where necessary to deal with optional factors / "xA" cells (by, annoyingly, either constraining them to 1 if the corresponding value Bx isn't on/0, or constraining them to their factor if Bx is on/1; I'd love to have a better way for this) - the goal factor abstracts out this pattern,
• and finally simply lists the constraints row by row and column by column.

While puzzle25 computes the solution, solve (for the lack of a better name), prints the solution for a given puzzle goal (so solve(puzzle25). will solve it and show the solution), that's already preparing for more puzzles to come.

:- use_module(library(clpfd)).
factor(B, N, Factor) :-
 B #= 0 #==> N #= 1,
 B #= 1 #==> N #= Factor.
puzzle25(Rows) :-
 Rows = [ [B1, B2, B3, B4], % =4
 [B5, B6, B7, B8], % =5
 [B9, B10, B11, B12, B13, B14, B15, B16], % =24
 [B17, B18, B19, B20], % =2
 [B21, B22, B23, B24] % =6
 % =6 =12 [1] =6
 % and the inner block can only have 6 selected
 ],
 flatten(Rows, Flat),
 Flat ins 0..1,
 factor(B3, N3, 4),
 ((1 * B1) + (2 * B2)) * N3 + (2 * B4) #= 4,
 factor(B6, N6, 2),
 (2 * B5) * N6 + (2 * B7) + (1 * B8) #= 5,
 factor(B10, N10, 2),
 factor(B11, N11, 2),
 factor(B12, N12, 3),
 factor(B13, N13, 2),
 factor(B14, N14, 3),
 factor(B15, N15, 4),
 (1 * B9) * N10 * N11 * N12 * N13 * N14 * N15 + (8 * B16) #= 24,
 factor(B18, N18, 2),
 factor(B20, N20, 2),
 ((1 * B17) * N18 + (2 * B19)) * N20 #= 2,
 factor(B23, N23, 2),
 factor(B24, N24, 2),
 ((3 * B21) + (3 * B22)) * N23 * N24 #= 6,
 ((1 * B1) + (2 * B5)) * N11 + (1 * B17) + (3 * B21) #= 6,
 (2 * B2) * N6 * N12 * N18 + (3 * B22) #= 12,
 B3 + B7 + B13 + B19 + B23 #= 1,
 ((2 * B4) + (1 * B8)) * N14 * N20 * N24 #= 6,
 B1 + B2 + B3 + B5 + B6 + B7 + B11 + B12 + B13 + B17 + B18 + B19 #= 6.
solve(Puzzle) :-
 apply(Puzzle, [L]),
 flatten(L, M),
 label(M),
 forall(member(Row, L), write_term(Row, [nl(true)])).

I'm fairly certain this is correct, because the output works when put into the game and there's only a single solution (which is what I'd expect from how the game is set up, multiple solutions would be more complicated for the player).

• dfhwze: I'm not even a prolog beginner, but is so that you are brute forcing your way through the constraints with the possible candidates with backtracking?
• ferada: @dfhwze it's slightly fancier, Wikpedia has a good explanation.
• dfhwze: I was thinking about en.wikipedia.org/wiki/Knuth%27s_Algorithm_X. But you need to tweak it to take into account dynamic updates of the remaining constraints.
• RootTwo: Can a multiplication square be first in a row or column that has a numerical constraint? Can there be squares with '-' or '/' or '%' operators?
• ferada: @RootTwo Yes, but only because sometimes you have constraints on both sides, which requires you to satisfy them read from the left and read from the right. I'm relatively sure I haven't seen one when it wasn't set up like that though. There are no other constraint types I've encountered, no.

Answer 1

I haven't looked at any Prolog code in at least a decade. So, I really can't give any useful feedback on your code. However, the question piqued my interest, and you did say you'd be more happy with ... Python......

So I rolled my own solver in Python. It's rough and under-tested, has very little error checking, and could use some refactoring. But here it is:

import re
from collections import defaultdict
from enum import Enum
from operator import add, mul

Enum for the state of each square

class State(Enum):
 OFF = 0
 ON = 1
 UNASSIGNED = 2

Class for the squares

class Variable:
 def __init__(self, op, value):
 self.op = op
 self.value = int(value)
 self.state = State.UNASSIGNED
 self.shorthand = f"{op}{value}"
 self.func = {'+':add, '*':mul}[op]
 def evaluate(self, left):
 if self.state != State.ON:
 return left
 else:
 if left:
 return self.func(left, self.value) 
 else:
 return self.value
 def __str__(self):
 return f"Variable('{self.op}','{self.value}'): {self.state.name})" 
 def __repr__(self):
 return f"V('{self.op}','{self.value}')" 
 def code(self):
 # OFF ON UNKNOWN
 return ['', self.shorthand, '?' ][self.state.value]

Enum for status of a constraint

class Status(Enum):
 FAILED = 0
 PASSED = 1
 UNKNOWN = 2

Class for the constraints

class Constraint:
 def __init__(self, variables, op, value):
 self.variables = list(variables)
 self.op = op
 self.value = int(value)
 def check(self):
 if self.op == '#':
 value = 0
 for v in self.variables:
 if v.state==State.UNASSIGNED:
 return Status.UNKNOWN
 if v.state==State.ON:
 value += 1
 else:
 value = None
 for variable in self.variables:
 if variable.state == State.UNASSIGNED:
 return Status.UNKNOWN
 value = variable.evaluate(value)
 return Status.PASSED if value == self.value else Status.FAILED
 def __str__(self):
 variables = ','.join(repr(v) for v in self.variables)
 return f"Constraint([{variables}], '{self.op}', '{self.value}')"

Class for the puzzle

class Puzzle:
 def __init__(self, puzzle):
 self.puzzle = puzzle[:]
 self.constraints = []
 self.by_var = defaultdict(list)
 self.variables = []
 rows = defaultdict(list)
 cols = defaultdict(list)
 groups = defaultdict(list)
 last_var_row = 0
 # gather the variables
 for r,row in enumerate(puzzle):
 for match in re.finditer(r"(?P<op>[+*])(?P<val>\d+)(?P<group>\w?)", row):
 variable = Variable(match['op'], match['val'])
 self.variables.append(variable)
 rows[r].append(variable)
 for left,right in cols.keys():
 if match.start() <= right and match.end() >= left:
 key = (left, right)
 break
 else:
 key = (match.start(),match.end())
 cols[key].append(variable)
 if match['group']:
 groups[match['group']].append(variable)
 last_var_row = max(last_var_row, r)
 # gather the constraints
 for r,row in enumerate(puzzle):
 for match in re.finditer(r"(?P<group>\w?)(?P<op>[#=])(?P<val>\d+)", row):
 if match['group']:
 cvars = groups[match['group']]
 elif r <= last_var_row:
 cvars = rows[r]
 else:
 for left,right in cols.keys():
 if match.start() <= right and match.end() >= left:
 key = (left, right)
 break
 else:
 raise ValueError("Unaligned column constraint: {match[0]} @ line {r}, col {match.start()}")
 cvars = cols[key]
 constraint = Constraint(cvars, match['op'], match['val'])
 self.constraints.append(constraint)
 for v in cvars:
 self.by_var[v].append(constraint)
 def consistent(self, variable):
 for constraint in self.by_var[variable]:
 check = constraint.check()
 s = ' '.join(v.code() for v in constraint.variables)
 if check == Status.FAILED:
 return False
 return True
 def solve(self, pretty=False):
 def search(variables):
 if not variables:
 return [v.state.value for v in self.variables]
 first, *rest = variables
 for state in (State.ON, State.OFF):
 first.state = state
 check = self.consistent(first)
 if check:
 result = search(rest)
 if result is not None:
 return result
 first.state = State.UNASSIGNED
 return None
 solution = search(self.variables[:])
 if solution is not None:
 if pretty == True:
 index = 0
 def sub(match):
 nonlocal index
 state = self.variables[index].state
 index += 1
 return match[0] if state == State.ON else ' '*len(match[0])
 print(re.sub(r"(?P<op>[+*])(?P<val>\d+)(?P<group>\w?)", sub, '\n\n'.join(self.puzzle)))
 return solution

A puzzle is defined graphically by a list of strings as shown in the example below.

A square is an operator followed by an integer, and an optional group id (a letter). For example, '+12' or '*3f'. All squares and column constraints must line up under the top square in the column (they must overlap).

A constraint is an optional group id, and operator ('=' or '#'), and then an int. An '=' sign means the formula equals the int. A '#' means that many squares are ON. For example, '=8', '#1', or 'f#5'.

Puzzle.solver() returns a list of 0/1 that corresponds to the squares in left-to-right, top-to-bottom order. A '1' means the square is ON and a '0' means it's OFF.

Here's your example coded for this solver:

puzzle = [
 " +1a +2a *4a +2 =4",
 " +2a *2a +2a +1 =5",
 " +1 *2 *2a *3a *2a *3 *4 +8 =24",
 " +1a *2a +2a *2 =2",
 " +3 +3 *2 *2 =6",
 " =6 =12 #1 =6 ",
 "a#6"
 ]
p = Puzzle(puzzle)
p.solve()

If you pass pretty=True to the Puzzle.solver(), it also prints out a picture of the solution.

p.solve(pretty=True)
 +2a +2 =4
 +2a +2a +1 =5
 +1 *2 *3a *4 =24
 +1a *2a =2
 +3 *2 =6
 =6 =12 #1 =6 
a#6

• ferada: Thanks for your answer! I really like the much more readable representation of the puzzle too and how you did made it work with the parser, definitely something to learn from.