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 goalsolve
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:
(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 to1
if the corresponding valueBx
isn't on/0
, or constraining them to their factor ifBx
is on/1
; I'd love to have a better way for this) - the goalfactor
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).