Advertisement
jordancurve

Clingo code to solve "I trominos on chessboard" puzzle

Jul 28th, 2018
207
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.25 KB | None | 0 0
  1. % Clingo code to solve @TamasGorbe's "I trominos on chessboard" puzzle
  2. % https://twitter.com/TamasGorbe/status/1023134575571202048
  3. %
  4. % Author: @jordancurve
  5. %
  6. % Usage: save as trom.lp, then run:
  7. %
  8. % clingo -n 0 --project trom.lp
  9. %
  10. % To pretty-print solutions as in https://pastebin.com/XAg0WHuv, run:
  11. %
  12. % 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"'
  13. %
  14. % You can also run it in your browser by pasting the contents of this
  15. % file in to the textarea at https://potassco.org/clingo/run/, clicking
  16. % the 'project' box, setting the reasoning mode to 'enumerate all', and
  17. % clicking 'Run!'.
  18.  
  19.  
  20. row(1..8).
  21. col(1..8).
  22. board(R, C): row(R), col(C).
  23.  
  24. #const ntrom = 21.
  25. % v(Y, X) - the orientation of the tromino with upper left corner at (Y,X) vertical.
  26. % ulc(Y, X) - there is a tromino with its upper-left corner at (Y,X).
  27.  
  28. % pick a location for each tromino.
  29.  
  30. ntrom { ulc(Y, X) : row(Y), col(X) } ntrom.
  31.  
  32. % Force there to be a horizontal tromino with its upper-left corner at (1,1).
  33. :- not ulc(1,1).
  34. :- v(1,1).
  35.  
  36. % Optionally set other tromino's orientation to vertical.
  37. 0 { v(Y,X) } 1 :- ulc(Y, X).
  38.  
  39. % Each tromino must fit on the board.
  40. :- ulc(Y, X), v(Y, X), not row(Y+2).
  41. :- ulc(Y, X), not v(Y, X), not col(X+2).
  42.  
  43. % cover(Y,X,A,B) :- square (Y,X) is covered by the tromino with an upper-left corner at (A,B).
  44. cover(Y..Y+2,X,Y,X) :- ulc(Y, X), v(Y, X).
  45. cover(Y,X..X+2,Y,X) :- ulc(Y, X), not v(Y, X).
  46.  
  47. % Each square can be covered by at most one tromino.
  48. :- cover(Y, X, A,B), cover(Y, X, C, D), A != C.
  49. :- cover(Y, X, A,B), cover(Y, X, C, D), B != D.
  50.  
  51. % Without loss of generality, force the blank square
  52. % to be in the upper-left quadrant.
  53. covered(Y,X) :- cover(Y, X, _, _).
  54. blank(Y,X) :- col(Y), col(X), not covered(Y,X).
  55. :- blank(Y,_), Y > 4.
  56. :- blank(_,X), X > 4.
  57.  
  58. #show ulc/2.
  59. #show v/2.
  60. #show blank/2.
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement