[HN Gopher] Solving domino fit using constraint programming
       ___________________________________________________________________
        
       Solving domino fit using constraint programming
        
       Author : polivier
       Score  : 39 points
       Date   : 2024-03-27 16:14 UTC (2 days ago)
        
 (HTM) web link (pedtsr.ca)
 (TXT) w3m dump (pedtsr.ca)
        
       | polivier wrote:
       | This is a solver for the game Domino Fit that was talked about on
       | HN last month: https://news.ycombinator.com/item?id=39420966
        
       | bronco21016 wrote:
       | 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?
        
         | polivier wrote:
         | 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...
        
         | andreasscherman wrote:
         | Oddly fitting, I wrote this many years ago that you might like:
         | https://andreasscherman.com/posts/an-introduction-to-constra...
        
         | tannhaeuser wrote:
         | https://quantumprolog.sgml.io/container-planning-demo/part1....
         | 
         | (with editable Prolog code ready to execute in the browser
         | even)
        
       | evrimoztamur wrote:
       | I have a hunch that we're going to see this on next year's Advent
       | of Code...
        
       | tombert wrote:
       | 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.
        
       | uxamanda wrote:
       | 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.
        
       | from-nibly wrote:
       | 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.
        
       | rjeli wrote:
       | 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...
        
         | polivier wrote:
         | Well done! My CP formulation is definitely not the best here. I
         | put this model together late one night while drinking a few
         | beers :)
        
       ___________________________________________________________________
       (page generated 2024-03-29 23:01 UTC)