|
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.
|
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..