Pentomino tiling

# 20201028 Raku programming solution

my \F = [ <1 -1 1 0 1 1 2 1>,  <0 1 1 -1 1 0 2 0>,   <1 0 1 1 1 2 2 1>,
          <1 0 1 1 2 -1 2 0>,  <1 -2 1 -1 1 0 2 -1>, <0 1 1 1 1 2 2 1>,
          <1 -1 1 0 1 1 2 -1>, <1 -1 1 0 2 0 2 1> ];

my \I = [ <0 1 0 2 0 3 0 4>, <1 0 2 0 3 0 4 0> ];

my \L = [ <1 0 1 1 1 2 1 3>,  <1 0 2 0 3 0 3 1>,   <0 1 0 2 0 3 1 3>,
          <0 1 1 0 2 0 3 0>,  <0 1 1 1 2 1 3 1>,   <0 1 0 2 0 3 1 0>,
          <1 0 2 0 3 -1 3 0>, <1 -3 1 -2 1 -1 1 0> ];

my \N = [ <0 1 1 -2 1 -1 1 0>, <1 0 1 1 2 1 3 1>,   <0 1 0 2 1 -1 1 0>,
          <1 0 2 0 2 1 3 1>,   <0 1 1 1 1 2 1 3>,   <1 0 2 -1 2 0 3 -1>,
          <0 1 0 2 1 2 1 3>,   <1 -1 1 0 2 -1 3 -1> ];

my \P = [ <0 1 1 0 1 1 2 1>,  <0 1 0 2 1 0 1 1>, <1 0 1 1 2 0 2 1>,
          <0 1 1 -1 1 0 1 1>, <0 1 1 0 1 1 1 2>, <1 -1 1 0 2 -1 2 0>,
          <0 1 0 2 1 1 1 2>,  <0 1 1 0 1 1 2 0> ];

my \T = [ <0 1 0 2 1 1 2 1>,  <1 -2 1 -1 1 0 2 0>,
          <1 0 2 -1 2 0 2 1>, <1 0 1 1 1 2 2 0> ];

my \U = [ <0 1 0 2 1 0 1 2>, <0 1 1 1 2 0 2 1>,
          <0 2 1 0 1 1 1 2>, <0 1 1 0 2 0 2 1> ];

my \V = [ <1 0 2 0 2 1 2 2>,   <0 1 0 2 1 0 2 0>,
          <1 0 2 -2 2 -1 2 0>, <0 1 0 2 1 2 2 2>  ];

my \W = [ <1 0 1 1 2 1 2 2>, <1 -1 1 0 2 -2 2 -1>,
          <0 1 1 1 1 2 2 2>, <0 1 1 -1 1 0 2 -1>  ];

my \X = [ <1 -1 1 0 1 1 2 0> , ]; # self-ref: reddit.com/r/rakulang/comments/jpys5p/gbi71jt/

my \Y = [ <1 -2 1 -1 1 0 1 1>, <1 -1 1 0 2 0 3 0>, <0 1 0 2 0 3 1 1>,
          <1 0 2 0 2 1 3 0>,   <0 1 0 2 0 3 1 2>,  <1 0 1 1 2 0 3 0>,
          <1 -1 1 0 1 1 1 2>,  <1 0 2 -1 2 0 3 0> ];

my \Z = [ <0 1 1 0 2 -1 2 0>, <1 0 1 1 1 2 2 2>,
          <0 1 1 1 2 1 2 2>,  <1 -2 1 -1 1 0 2 -2> ];

our @shapes =  F, I, L, N, P, T, U, V, W, X, Y, Z ;

my @symbols = "FILNPTUVWXYZ-".comb;
my %symbols = @symbols.pairs;
my $nRows = my $nCols = 8; my $blank = 12;
my @grid = [ [-1 xx $nCols ] xx $nRows ];
my @placed;

sub shuffleShapes {
   my @rand = (0 ..^+@shapes).pick(*);
   for (0 ..^+@shapes) -> \i {
      (@shapes[i],  @shapes[@rand[i]])  = (@shapes[@rand[i]],  @shapes[i]);
      (@symbols[i], @symbols[@rand[i]]) = (@symbols[@rand[i]], @symbols[i])
   }
}

sub solve($pos,$numPlaced)  {
   return True if $numPlaced == +@shapes;

   my \row = $pos div $nCols;
   my \col = $pos mod $nCols;

   return solve($pos + 1, $numPlaced) if @grid[row;col] != -1;

   for ^+@shapes -> \i {
      if !@placed[i] {
         for @shapes[i] -> @orientation {
            for @orientation -> @o {
               next if !tryPlaceOrientation(@o, row, col, i);
               @placed[i] = True;
               return True if solve($pos + 1, $numPlaced + 1);
               removeOrientation(@o, row, col);
               @placed[i] = False;
            }
         }
      }
   }
   return False
}

sub tryPlaceOrientation (@o, $r, $c, $shapeIndex) {

   loop (my $i = 0; $i < +@o; $i += 2) {
      my \x = $c + @o[$i + 1];
      my \y = $r + @o[$i];
      return False if
         (x < 0 or x ≥ $nCols or y < 0 or y ≥ $nRows or @grid[y;x] != -1)
   }

   @grid[$r;$c] = $shapeIndex;
   loop ($i = 0; $i < +@o; $i += 2) {
      @grid[ $r + @o[$i] ; $c + @o[$i + 1] ] = $shapeIndex;
   }
   return True
}

sub removeOrientation(@o, $r, $c) {
   @grid[$r;$c] = -1;
   loop (my $i = 0; $i < +@o; $i += 2) {
      @grid[ $r + @o[$i] ; $c + @o[$i + 1] ] = -1;
   }
}

sub PrintResult {
   my $output;
   for @grid[*] -> @line {
      $output ~= "%symbols{$_}  " for @line;
      $output ~= "\n"
   }
   if my \Embedded_Marketing_Mode = True {
      $output .= subst('-', $_.chr) for < 0x24c7 0x24b6 0x24c0 0x24ca >
   }
   say $output
}

#shuffleShapes(); # xkcd.com/221

for ^4 {
   loop {
      if @grid[my \R = (^$nRows).roll;my \C = (^$nCols).roll] != $blank
         { @grid[R;C] = $blank and last }
   }
}

PrintResult() if solve 0,0

Output:

F F Ⓡ I I I I I
Ⓐ F F N L L L L
P F N N X U U L
P P N X X X U Ⓚ
P P N W X U U T
V Z Ⓤ W W T T T
V Z Z Z W W Y T
V V V Z Y Y Y Y

Last updated