4 ms·
Solving domino fit using constraint programming
- polivier 3y agoThis is a solver for the game Domino Fit that was talked about on HN last month: https://news.ycombinator.com/item?id=39420966 https://news.ycombinator.com/item?id=39420966
- bronco21016 3y agoI 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?
- polivier 3y agoAll 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-constraint-programming.html https://pedtsr.ca/2023/generating-crossword-grids-using-cons...
- andreasscherman 3y agoOddly fitting, I wrote this many years ago that you might like: https://andreasscherman.com/posts/an-introduction-to-constraint-programming/ https://andreasscherman.com/posts/an-introduction-to-constra...
- tannhaeuser 3y agohttps://quantumprolog.sgml.io/container-planning-demo/part1.html https://quantumprolog.sgml.io/container-planning-demo/part1.... (with editable Prolog code ready to execute in the browser even)
- evrimoztamur 3y agoI have a hunch that we're going to see this on next year's Advent of Code...
- tombert 3y agoIt'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.
- uxamanda 3y agoOff 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.
- from-nibly 3y agoConstraint 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.
- rjeli 3y agoNice! 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/a1612da0e3c8b99ec4514e689ebdfa85 https://gist.github.com/rjeli/a1612da0e3c8b99ec4514e689ebdfa...
- polivier 3y agoWell done! My CP formulation is definitely not the best here. I put this model together late one night while drinking a few beers :)
- ulchar 3y agoI 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.
- akoboldfrying 3y agoNice, 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.