3 ms·
The site uses Answer Set Programming with the Clingo engine to compute the optimal solutions for smaller grids. Maximizing grids like this is probably NP-hard.
by Scaevolus 9mo ago
The site uses Answer Set Programming with the Clingo engine to compute the optimal solutions for smaller grids. Maximizing grids like this is probably NP-hard.
Note that traditional SAT and SMT solvers are quite inefficient at computing flood-fills.
The ASP specifications it uses to compute optimal solutions are surprisingly short and readable, and look like:
#const budget=11.
horse(4,4).
cell(0,0).
boundary(0,0).
cell(0,1).
boundary(0,1).
% ...truncated for brevity...
cell(3,1).
water(3,1).
% ...
% Adjacent cells (4-way connectivity)
adj(R,C, R+1,C) :- cell(R,C), cell(R+1,C).
adj(R,C, R-1,C) :- cell(R,C), cell(R-1,C).
adj(R,C, R,C+1) :- cell(R,C), cell(R,C+1).
adj(R,C, R,C-1) :- cell(R,C), cell(R,C-1).
% Walkable = not water
walkable(R,C) :- cell(R,C), not water(R,C).
% Choice: place wall on any walkable cell except horse and cherries
{ wall(R,C) } :- walkable(R,C), not horse(R,C), not cherry(R,C).
% Budget constraint (native counting - no bit-blasting!)
:- #count { R,C : wall(R,C) } > budget.
% Reachability from horse (z = enclosed/reachable cells)
z(R,C) :- horse(R,C).
z(R2,C2) :- z(R1,C1), adj(R1,C1, R2,C2), walkable(R2,C2), not wall( R2,C2).
% Horse cannot reach boundary (would escape)
:- z(R,C), boundary(R,C).
% Maximize enclosed area (cherries worth +3 bonus = 4 total)
#maximize { 4,R,C : z(R,C), cherry(R,C) ; 1,R,C : z(R,C), not cherry( R,C) }.
% Only output wall positions
#show wall/2.
- stabbles 9mo agoNice, you don't see clingo mentioned often. We use it in the Spack package manager for resolving dependencies [1] [1] https://github.com/spack/spack/blob/develop/lib/spack/spack/solver/concretize.lp https://github.com/spack/spack/blob/develop/lib/spack/spack/...
- freakynit 9mo agoIm over 35 years of age. I have 15+ years of programming experience. And I generally consider myself as someone who has good breadth of tech in general. Yet, this is the first time in my life I've heard of ASP. And gosh. I was completely blown away by this as I read more about it and went through some examples (https://github.com/domoritz/clingo-wasm/blob/main/examples/examples/traveling-salesperson.lp https://github.com/domoritz/clingo-wasm/blob/main/examples/e...) Therefore, like a good little llm bitch that I have become recently, I straight away went to chatgpt/sonnet/gemini and asked them to compile me a list of more such "whatever this is known as". And holy cow!! This is a whole new world. My ask to HN community: any good book recommendations related to "such stuff"? Not those research kinds as I don't have enough brain cells for it. But, a little easier and practical ones? Thanks..
- ctxc 9mo agoHas to be my favourite comment, haha!
- freakynit 9mo ago:)
- Scaevolus 9mo agoThe pre-machine-learning formulations of AI focused on symbolic reasoning through the dual problems of search and logic. Many problems can be reduced to enumerating legal steps, and SAT/SMT/ASP and related systems can churn through those in a highly optimized and genetic manner.
- freakynit 9mo agoThanks... noted a few keywords to expand on further: 1. Symbolic reasoning 2. SAT/SMT/ASP 3. pre-machine-learning formulations of AI
- sfink 9mo ago"Logic programming"[0] is what I've always heard this stuff called. I was introduced to it with Prolog. "Declarative programming"[1] is kind of a superset of logic programming, which may or may not be the aspect that piques your interest. "Constraint programming"[2] and "Constraint logic programming"[3] are also a perspective on it. [0] https://en.wikipedia.org/wiki/Logic_programming https://en.wikipedia.org/wiki/Logic_programming [1] https://en.wikipedia.org/wiki/Declarative_programming https://en.wikipedia.org/wiki/Declarative_programming [2] https://en.wikipedia.org/wiki/Constraint_programming https://en.wikipedia.org/wiki/Constraint_programming [3] https://en.wikipedia.org/wiki/Constraint_logic_programming https://en.wikipedia.org/wiki/Constraint_logic_programming
- freakynit 9mo agoThanks a lot. These are what I was hoping to know.