I made a puzzle solver
A couple of months ago I stumbled across the a-puzzle-a-day by dragonfjord
I bought one for me and one for a friend of mine.
A daily routine
We started sending photos of the puzzle each day, showing how we solved it that day. It was a fun little thing to do and it was a nice way to keep in touch.
Since both he and I are developers it did not take long before we started talking about how the underlying system worked and if one could solve it using code.
There are other solvers for this
Now this is not ground breaking. There are plenty of other websites, python scripts and other solver tools for this puzzle and I was not really interested in solving the puzzle.
I wanted to understand the inner workings of it and I really wanted to get the data on why some days felt impossible to solve and others seemed to solve themselves.
The research
I came across this paper on Algoritm X and some reverse searching lead to a python script that credited this paper.
The algorithm itself is not that complicated - well it is but it is not - but the way it is implemented is quite clever.
def solve(X, Y, solution=None):
if not X:
yield list(solution)
else:
c = min(X, key=lambda c: len(X[c]))
for r in list(X[c]):
solution.append(r)
cols = select(X, Y, r)
for s in solve(X, Y, solution):
yield s
deselect(X, Y, r, cols)
solution.pop()
def select(X, Y, r):
cols = []
for j in Y[r]:
for i in X[j]:
for k in Y[i]:
if k != j:
X[k].remove(i)
cols.append(X.pop(j))
return cols
def deselect(X, Y, r, cols):
for j in reversed(Y[r]):
X[j] = cols.pop()
for i in X[j]:
for k in Y[i]:
if k != j:
X[k].add(i)
def exact_cover(X, Y):
X = {j: set() for j in X}
for i, row in Y.items():
for j in row:
X[j].add(i)
return X
if __name__ == '__main__':
X = {1, 2, 3, 4, 5, 6, 7}
Y = {'A':[1,4,7], 'B':[1,4], 'C':[4,5,7], 'D':[3,5,6], 'E':[2,3,6,7], 'F':[2,7]}
X = exact_cover(X, Y)
solutions = solve(X, Y, [])
print(list(solutions))
It is basically recursively bruteforcing until it fits. We tell it how the game board looks and what the pieces look like and in the case of a-puzzle-a-day we “lock” two slots that cannot be covered by any puzzle piece. One for the month, one for the day.
Explanation
Algoritm X is based on the Exact Cover Problem which is useful for solving sudokus, tetris-like puzzles and even scheduling problems.
Imagine you have a bunch of requirements (represented by X) and a set of choices (represented by Y). Each choice covers some of the requirements.
Your goal is to pick a set of choices such that:
Every requirement is covered exactly once. You use the fewest possible choices.
Pentomino
There is a similar puzzle to a-puzzle-a-day, called Pentomino. It is a 5x12 grid and you have to fit all 12 pentominoes into the grid.
The same author for the algox.py also conveniently had a pentomino solver and even a a-puzzle-a-day solver that utilizes the pentomino solver.
After reading through the code I realized that I could use the same solution but in svelte.
My solver
I created this a-puzzle-a-day solver, I basically just copied the code from the python script and translated it to svelte, wrote an UI from scratch and that was it.
What I noticed was that the script was very fast in calculating the maximum number of solutions which was the data I was interested in.
Usage
By clicking a month you show the solutions for that month. By clicking a day you show the solutions for that day.
There are some statistics at the bottom of the page and I might keep developing this further so there may be more things I don’t write about here.