Solving domino fit using constraint programming | Hacker News Reader

Solving domino fit using constraint programming

pedtsr.ca

59 pointspolivier13 comments

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: https://gist.github.com/rjeli/a1612da0e3c8b99ec4514e689ebdfa...

Well done! My CP formulation is definitely not the best here. I put this model together late one night while drinking a few beers :)

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?

All my CP-related blog posts show a step-by-step formulation of the model. Here is an example showing my thought process while modeling the generation of crossword grids using CP (note that this is substantially more complex than the Domino Fit model): https://pedtsr.ca/2023/generating-crossword-grids-using-cons...

Oddly fitting, I wrote this many years ago that you might like: https://andreasscherman.com/posts/an-introduction-to-constra...

https://quantumprolog.sgml.io/container-planning-demo/part1....

(with editable Prolog code ready to execute in the browser even)

I have a hunch that we're going to see this on next year's Advent of Code...

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.

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.

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: https://news.ycombinator.com/item?id=39420966

Reply on news.ycombinator.com