jordancurve icon

Clingo code to solve "I trominos on chessboard" puzzle

jordancurve | PRO | 07/28/18 11:07:24 PM UTC | 0 ⭐ | 477 👁️ | Never ⏰ | []
text |

2.25 KB

|

None

|

0 👍

/

0 👎

% 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