Filling an 8x8 board with 21 triominoes (leaving 1 hole) with certain additional conditions

triomino tiling.ts

// Finding solutions for the triomino problem posed in
// https://math.stackexchange.com/questions/2746678/covering-an-8%c3%978-grid-with-three-colors-of-trominoes
// See also https://mathstodon.xyz/@mjd/117289161849417211
//
// Place a 1x1 "hole" and red, green and blue triominoes (7 of each color) on a
// 8x8 board such that:
// - All 64 squares of the board are covered without overlap.
// - There is no pair of same-color triominoes touching along an edge.
// - There is at most one pair of same-color triominoes touching at a vertex.
//
// We also try to avoid "redundant" solutions, that is, solutions that can be
// created from reported solutions by
// - reflecting or rotating
// - or by permuting the colors.
//
// Run this file with a JS/TS interpreter (such as node, deno or bun) in a
// terminal that understands ANSI escape codes for output coloring.
//
// -----------------------------------------------------------------------------

type Pos = {row: number, col: number};
const pos = (row: number, col: number): Pos => ({row, col});

const showPos = ({row, col}: Pos): string =>
  String.fromCharCode("A".charCodeAt(0) + col) + (row + 1);

// We only investigate possible hole placements in some triangle.
// Placing the hole elsewhere would lead to similar (i.e., rotated or reflected)
// solutions.  (Holes on the main diagonal may still lead to reflected
// solutions, but it turns out they don't lead to any solutions at all.)
const holePositions = [
  pos(0, 0),
  pos(1, 0), pos(1, 1),
  pos(2, 0), pos(2, 1), pos(2, 2),
  pos(3, 0), pos(3, 1), pos(3, 2), pos(3, 3),
];

function* edgeNeighbors({row, col}: Pos) {
  if (row > 0) yield pos(row-1, col);
  if (row < 7) yield pos(row+1, col);
  if (col > 0) yield pos(row, col-1);
  if (col < 7) yield pos(row, col+1);
}
function* vertexNeighbors({row, col}: Pos) {
  if (row > 0) {
    if (col > 0) yield pos(row-1, col-1);
    if (col < 7) yield pos(row-1, col+1);
  }
  if (row < 7) {
    if (col > 0) yield pos(row+1, col-1);
    if (col < 7) yield pos(row+1, col+1);
  }
}

// board traversal:
const startSquare = pos(0, 0);
/**
 * The next square position in board traversal order or `null`
 * if no square is left
 */
const nextSquare = ({row, col}: Pos): null | Pos =>
  col < 7 ? pos(row, col+1) : row < 7 ? pos(row+1, 0) : null;

// -----------------------------------------------------------------------------

const colors = ["R", "G", "B"] as const;

/** still to be filled */
const free = "?";

const hole = " ";

type Color = typeof colors[number];
type Value = Color | typeof free | typeof hole

const ansiColors: Record<Value, string> = {
  "R"   : "37;41",
  "G"   : "37;42",
  "B"   : "37;44",
  [free]: "30;43",
  [hole]: "39;49",
}

const highlight = (s: Value) =>
  `\x1b[${ansiColors[s] ?? "30;47"}m${s} \x1b[39;49m`;

// -----------------------------------------------------------------------------

const squares: Value[][] =
  Array.from({length: 8}, () => Array.from({length: 8}, () => free));

const square = (p: Pos): Value => squares[p.row]![p.col]!;
function setSquare(p: Pos, value: Value) { squares[p.row]![p.col]! = value; }

const isFree = (p: Pos): boolean => square(p) === free;

/** Ways to cover position `p` with a triomino */
function* triominoPlacements(p: Pos) {
  // We do not even consider placements involving squares that come earlier
  // in the traversal order since these are known to be covered already.
  const {row, col} = p;
  if (row < 7) {
    const d  = pos(row+1, col);
    if (col < 7) {
      const r  = pos(row  , col+1)
      const dr = pos(row+1, col+1);
      if (isFree(r) && isFree(d )) yield [p, r, d ];
      if (isFree(r) && isFree(dr)) yield [p, r, dr];
      if (isFree(d) && isFree(dr)) yield [p, d, dr];
    }
    if (col > 0) {
      const dl = pos(row+1, col-1);
      if (isFree(dl) && isFree(d )) yield [p, dl, d];
    }
  }
};

/** How many pieces of each color are still available? */
const pieces: Record<Color, number> = {R: 7, G: 7, B: 7};

/**
 * Description of equal-color pieces touching at a vertex;
 * empty if none has been detected yet
 */
let vertexClash: string = "";

/**
 * Helper for detecting color clashes between `neighbor` and `p`
 * if `p` were covered with `color`.
 *
 * Only the second such clash is reported.
 * More clashes do not occur because a search path is abandoned upon a second
 * clash.
 * 
 * The global variable `vertexClash` is used to record the first such clash.
 */
function isSecondVertexClash(p: Pos, neighbor: Pos, color: Color): boolean {
  if (square(neighbor) === color) {
    if (vertexClash) return true; // It's the second vertex clash
    // It's the first vertex clash.  Record it so that
    // - a future vertex clash will be detected as the second one
    // - and we can report the clash as part of the solution.
    vertexClash =
      `${showPos(neighbor)} = ${showPos(p)} = '${highlight(color)}'\n`;
  }
  // We come here if there is no current clash or it is the first one.
  return false;
}

/** How many solutions have we found so far? */
let nSolutions = 0;

const emitSolution = () =>
  console.log(
`Solution #${++nSolutions}:
  A B C D E F G H
${
  squares.map((row, i) =>
    `${i+1} ${row.map(highlight).join("")} ${i+1}\n`
  ).join("")
}  A B C D E F G H
${vertexClash}`
  );

/**
* Traverse the search tree depth-first (with backtracking).
* Each path of the search tree places triomino pieces in the board
* - from top to bottom and
* - from left to right
* 
* in row-major order.
* 
* The hole is assumed to be placed already.
* 
* Whenever we are at a square we try to place a triomino piece
* - of one of the available colors
* - in one of the possible rotations.
* 
* For each legal placement we continue a sub-branch.
* 
* @param current denotes the square position to be handled next or it is
* `null` to indicate that the entire board has been handled.
*/
function descend(current: Pos | null) {
  if (!current) {
    // Board completed.
    emitSolution();
    return;
  }
  if (!isFree(current)) {
    // Square already covered or a hole.  Continue with next square.
    descend(nextSquare(current));
    return;
  }
  // The square `current` is the first one that is empty.
  // Try to place a triomino in various ways to cover it.
  for (const placement of triominoPlacements(current)) {
    // Try all the colors for which triominoes are still available.
    // Exception:
    // For the first two pieces `R` and `G` are enforced to avoid trivial
    // duplicates where only the colors are permuted.)
    for (const color of (
      pieces.R === 7 ? ["R" as const] :
      pieces.G === 7 ? ["G" as const] :
      colors.filter(c => pieces[c] > 0)
    )) {
      if (!placement.some(p => edgeNeighbors(p).some(neighbor =>
        square(neighbor) === color
      ))) {
        const vertexClashBackup = vertexClash;
        if (!placement.some(p => vertexNeighbors(p).some(neighbor =>
          isSecondVertexClash(p, neighbor, color)
        ))) {
          // The piece's placement is legal.  So we
          // - actually place the piece,
          // - descend to the next level of the search tree,
          // - and remove the piece upon backtracking.
          placement.forEach(p => setSquare(p, color));
          pieces[color]--;
          descend(nextSquare(current));
          pieces[color]++;
          placement.forEach(p => setSquare(p, free));
        }
        // isSecondVertexClash(...) may have recorded a first clash.
        // Remove it upon backtracking:
        vertexClash = vertexClashBackup;
      }
    }
  }
}

for (const p of holePositions) {
  setSquare(p, hole);
  descend(startSquare);
  setSquare(p, free);
}