% Clingo code to solve @TamasGorbe's "I trominos on chessboard" puzzle
% https://twitter.com/TamasGorbe/status/1023134575571202048
%
% Author: @jordancurve
%
% Usage: save as trom.lp, then run:
%
% clingo -n 0 --project trom.lp
%
% To pretty-print solutions as in https://pastebin.com/XAg0WHuv, run:
%
% clingo -n 0 --project trom.lp | | perl -ne '/ulc/ || next; my @board; my %v; while(/\bv[(](\d+),(\d+)[)]/g) { $v{"$1,$2"} = 1 } while(/\bulc[(](\d+),(\d+)[)]/g) { my ($y,$x) = ($1,$2); if ($v{"$y,$x"}) { $board[$y][$x]=$board[$y+1][$x]=$board[$y+2][$x]="V" } else { $board[$y][$x]=$board[$y][$x+1]=$board[$y][$x+2] = "H" }} while(/blank[(](\d+),(\d+)[)]/g) { my ($y,$x) = ($1,$2); $board[$y][$x] = "."} my @rows = map(join("", @$_), @board); shift @rows; print join("\n", @rows), "\n\n"'
%
% You can also run it in your browser by pasting the contents of this
% file in to the textarea at https://potassco.org/clingo/run/, clicking
% the 'project' box, setting the reasoning mode to 'enumerate all', and
% clicking 'Run!'.
row(1..8).
col(1..8).
board(R, C): row(R), col(C).
#const ntrom = 21.
% v(Y, X) - the orientation of the tromino with upper left corner at (Y,X) vertical.
% ulc(Y, X) - there is a tromino with its upper-left corner at (Y,X).
% pick a location for each tromino.
ntrom { ulc(Y, X) : row(Y), col(X) } ntrom.
% Force there to be a horizontal tromino with its upper-left corner at (1,1).
:- not ulc(1,1).
:- v(1,1).
% Optionally set other tromino's orientation to vertical.
0 { v(Y,X) } 1 :- ulc(Y, X).
% Each tromino must fit on the board.
:- ulc(Y, X), v(Y, X), not row(Y+2).
:- ulc(Y, X), not v(Y, X), not col(X+2).
% cover(Y,X,A,B) :- square (Y,X) is covered by the tromino with an upper-left corner at (A,B).
cover(Y..Y+2,X,Y,X) :- ulc(Y, X), v(Y, X).
cover(Y,X..X+2,Y,X) :- ulc(Y, X), not v(Y, X).
% Each square can be covered by at most one tromino.
:- cover(Y, X, A,B), cover(Y, X, C, D), A != C.
:- cover(Y, X, A,B), cover(Y, X, C, D), B != D.
% Without loss of generality, force the blank square
% to be in the upper-left quadrant.
covered(Y,X) :- cover(Y, X, _, _).
blank(Y,X) :- col(Y), col(X), not covered(Y,X).
:- blank(Y,_), Y > 4.
:- blank(_,X), X > 4.
#show ulc/2.
#show v/2.
#show blank/2.
Comments