Nice! I rewrote it in z3 and was able to avoid the if-elses by tracking the occupancy of each cell as an integer, and constraining it to exactly 1: <a href="https://gist.github.com/rjeli/a1612da0e3c8b99ec4514e689ebdfa85" rel="nofollow">https://gist.github.com/rjeli/a1612da0e3c8b99ec4514e689ebdfa...</a>
Off topic from the solver, which is neat to read through - I’m still a big fan of this game. Looks like I’ve played 33 days of the past ~40 days. My only critique is that the UI design of the end state could be improved. Lots of very small fonts.
Constraint programming is awesome. I learned prolog in college which can accomplish similar stuff. One of thw things thats cool is you are badically just describing the problem and the rules. As soon as you are done with that the problem is already solved.
I love seeing this worked through step by step. Does anyone know of other blog posts where constraint programming is applied step by step to a problem?
I know these are the times of big machine learning models, but my favourite kind of AI are the classics like CSAT solvers, minimax with alpha beta pruning, markov chains, and good old search trees. These algorithms have superhuman powers solving so many challenging games and problems just by converting the problem space into a search tree. Love it.
Nice, I haven't come across this library before.<p>One minor suggestion: You could remove all of the corner and border special cases for overlap testing by making the grid 2 columns wider and 2 rows taller, offsetting all coordinates by 1, and pretending that the outer "border" on all sides of this slightly larger grid is covered with black cells.
It's definitely not optimal, but I love doing this stuff with TLA+. You define rules for state transitions, and constraints that cannot happen, and then you run a model check.<p>There's probably better ways of doing it, but I already know TLA+ and TLC does a breadth-first search so it'll find the shortest path.
This is a solver for the game Domino Fit that was talked about on HN last month: <a href="https://news.ycombinator.com/item?id=39420966">https://news.ycombinator.com/item?id=39420966</a>