*Bounty: 50*

*Bounty: 50*

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~~Edit: The second goal

could be improved?`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:

(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).