There’s a puzzle game called
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 thisEdit: The second goal
could be improved?
solvenow 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 = 4though.
- 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 (“ tiles”).
- The constraints are either number of tiles allowed to be set in the
sequence (“ 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
Bxas integers 0 or 1 to express whether a cell
(numbered from top left to bottom right, row by row) is present or
- uses variables
Nxwhere necessary to deal with optional factors /
“xA” cells (by, annoyingly, either constraining them to
1if the corresponding value
0, or constraining them to their factor if
1; I’d love to have a better way for this) – the goal
factorabstracts out this pattern,
- and finally simply lists the constraints row by row and column by column.
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  =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).