68 97 119 105 100 32 82 121 108 107 111

Domino tiling

 | 
Płytki domino rozłożone płasko na planszy.

Układanie płytek domino na kwadratowej planszy 2n x 2n nie wydaje się zbyt skomplikowane. Wyliczenie ilości możliwych układów w zależności od wymiaru planszy także nie powinno sprawić kłopotu. Problem pojawia się, gdy potrzebujemy to zrobić w rozsądnym limicie czasu.

1, 2, 36, 6728, 12988816, 258584046368, 53060477521960000, 112202208776036178000000, 2444888770250892795802079170816, 548943583215388338077567813208427340288, 1269984011256235834242602753102293934298576249856

Problem

Na ile różnych sposobów można pokryć całkowicie planszę 8 x 8 płytkami domino 2 x 1?

Rozwiązanie

W celu śledzenia stanu użyjemy maski bitowej. Rozważamy dwa główne scenariusze: obecna pozycja jest zajęta, i obecna pozycja jest wolna. Gdy pozycja jest wolna, funkcja rozważa umieszczenie domino w pionie oraz poziomie.

W poszukiwaniu układów płytek

Sercem solvera jest funkcja rekurencyjna searchTileArrangements. Funkcja ta przeszukuje możliwe układy płytek domino na planszy, wykorzystując programowanie dynamiczne w celu optymalizacji.

Parametry

Parametry tej funkcji to: tilingMatrix, rowCount, colCount, rowIndex, colIndex, currentMask, nextMask.

function searchTileArrangements(params) {
  const {
    tilingMatrix,
    rowCount,
    colCount,
    rowIndex,
    colIndex,
    currentMask,
    nextMask,
  } = params;

  ...
}

Zakończenie działania funkcji

Po destrukturyzacji parametrów rozpoczynamy serię sprawdzeń. Zakończenie działania następuje, gdy rowIndex jest równy rowCount.

if (rowIndex === rowCount) {
  return;
}

Gdy colIndex osiągnie wartość większą lub równą niż colCount, następuje aktualizacja macierzy układów dla kolejnego wiersza i maski. Sposób tej aktualizacji wskazuje na wykorzystanie wcześniej obliczonych wyników w celu generowania nowych.

if (colIndex >= colCount) {
  tilingMatrix[rowIndex + 1][nextMask] += tilingMatrix[rowIndex][currentMask];
  return;
}

Obliczanie bitów

Następnie obliczamy bity reprezentujące obecną oraz następną kolumnę.

const currentBit = 1 << colIndex;
const nextBit = 1 << (colIndex + 1);

Rekurencyjne wywołanie

Gdy aktualny bit jest zajęty, rozpoczynamy rekurencyjne wywołanie z aktualizacją colIndex + 1 (płytka domino w pionie). W sytuacji przeciwnej, oprócz aktualizacji colIndex + 1, aktualizujemy również nextMask poprzez operację bitową OR (nextMask | currentBit).

currentMask & currentBit
  ? searchTileArrangements({ ...params, colIndex: colIndex + 1 })
  : searchTileArrangements({
      ...params,
      colIndex: colIndex + 1,
      nextMask: nextMask | currentBit,
    });

Pominięcie dwóch bitów

Aktualizacja colIndex + 2 następuje, gdy można pominąć dwa bity.

if (canSkipTwoBits(colIndex, colCount, currentMask, currentBit, nextBit)) {
  searchTileArrangements({ ...params, colIndex: colIndex + 2 });
}

Funkcja sprawdzająca, czy możliwe jest pominięcie dwóch bitów (płytka domino w poziomie), prezentuje się następująco.

function canSkipTwoBits(colIndex, colCount, currentMask, currentBit, nextBit) {
  return (
    colIndex + 1 < colCount &&
    !(currentMask & currentBit) &&
    !(currentMask & nextBit)
  );
}

Obliczanie ilości uładów

Wyodrębnienie funkcji calculateTotalTilingCombinations to kwestia gustu.

function calculateTotalTilingCombinations({ rowCount, colCount }) {
...
}

Potrzebne było mi miejsce, gdzie będę mógł stworzyć i zainicjalizować macierz, ustawić punkt startowy dla algorytmu, rozpocząć iteracje oraz zwrócić wynik.

Utworzenie macierzy początkowej

Funkcja createInitialTilingMatrix tworzy i inicjalizuje macierz (dwuwymiarową tablicę), która jest używana do śledzenia liczby możliwych układów płytek domino. Macierz tilingMatrix przechowuje wyniki pośrednie, umożliwiając uniknięcie powtórnego obliczania tych samych wartości.

const tilingMatrix = createInitialTilingMatrix(rowCount, colCount);

Każdy wiersz odpowiada stanowi wiersza na planszy. Każda kolumna w wierszu odpowiada możliwemu układowi płytek w danym wierszu. Reprezentacja odbywa się za pomocą maski bitowej.

function createInitialTilingMatrix(rowCount, colCount) {
  return Array.from({ length: rowCount + 1 }, () =>
    new Array(1 << colCount).fill(0)
  );
}

Ustawienie punktu startowego

Pierwszy element to lewy górny róg macierzy. 1 oznacza, że mamy jedną kombinację dla pustej planszy.

tilingMatrix[0][0] = 1;

Iteracja

Poszukiwania rozpoczynamy od dwóch pętli for. Najpierw przez wszystkie wiersze macierzy, następnie wszystkie możliwe kombinacje (maski) dla danego wiersza.

for (let rowIndex = 0; rowIndex < rowCount; ++rowIndex) {
  for (let currentMask = 0; currentMask < 1 << colCount; ++currentMask) {
    searchTileArrangements({
      tilingMatrix,
      rowCount,
      colCount,
      rowIndex,
      colIndex: 0,
      currentMask,
      nextMask: 0,
    });
  }
}

Zwrócenie wyniku

return tilingMatrix[rowCount][0];

Uruchomienie

Rolę wejścia do programu pełni funkcja __main__.

function __main__() {
  const argsSchema = { "-r": "rowCount", "-c": "colCount" };
  const options = parseArgs(process.argv.slice(2), argsSchema);

  if (!options.rowCount || !options.colCount) {
    console.error(
      "Usage: node dominoTilingSolver.js -r <rowCount> -c <colCount>"
    );
    process.exit(1);
  }

  const result = calculateTotalTilingCombinations(options);
  console.log(result);
  process.exit(0);
}

Funkcja odpowiedzialna jest za:

  • pobranie argumentów z linii komend,
  • przetworzenie argumentów i ustawienie opcji,
  • obsługę błędów,
  • uruchomienie solvera,
  • wyświetlanie wyników.

Cały program

W celu otrzymania rozwiązań na liczbach wykraczających poza zakres Integer, solver został zmodyfikowany o wersję BigInt. Funkcje pomocnicze wykorzystywane w solverach oraz testach i benchmarkach znajdują się w folderze helpers. Całe programy można znaleźć poniżej lub na moim GitHubie. W celach testowych polecam pobrać cały folder, zamiast ręcznego tworzenia plików.

Cały program Integer - dominoTilingSolver.js

dominoTilingSolver.js

Uruchomienie:

node dominoTilingSolver.js -r <rowCount> -c <colCount>

Kod:

const { parseArgs } = require("./helpers");

function canSkipTwoBits(colIndex, colCount, currentMask, currentBit, nextBit) {
  return (
    colIndex + 1 < colCount &&
    !(currentMask & currentBit) &&
    !(currentMask & nextBit)
  );
}

function searchTileArrangements(params) {
  const {
    tilingMatrix,
    rowCount,
    colCount,
    rowIndex,
    colIndex,
    currentMask,
    nextMask,
  } = params;

  if (rowIndex === rowCount) {
    return;
  }

  if (colIndex >= colCount) {
    tilingMatrix[rowIndex + 1][nextMask] += tilingMatrix[rowIndex][currentMask];
    return;
  }

  const currentBit = 1 << colIndex;
  const nextBit = 1 << (colIndex + 1);

  currentMask & currentBit
    ? searchTileArrangements({ ...params, colIndex: colIndex + 1 })
    : searchTileArrangements({
        ...params,
        colIndex: colIndex + 1,
        nextMask: nextMask | currentBit,
      });

  if (canSkipTwoBits(colIndex, colCount, currentMask, currentBit, nextBit)) {
    searchTileArrangements({ ...params, colIndex: colIndex + 2 });
  }
}

function createInitialTilingMatrix(rowCount, colCount) {
  return Array.from({ length: rowCount + 1 }, () =>
    new Array(1 << colCount).fill(0)
  );
}

function calculateTotalTilingCombinations({ rowCount, colCount }) {
  const tilingMatrix = createInitialTilingMatrix(rowCount, colCount);
  tilingMatrix[0][0] = 1;

  for (let rowIndex = 0; rowIndex < rowCount; ++rowIndex) {
    for (let currentMask = 0; currentMask < 1 << colCount; ++currentMask) {
      searchTileArrangements({
        tilingMatrix,
        rowCount,
        colCount,
        rowIndex,
        colIndex: 0,
        currentMask,
        nextMask: 0,
      });
    }
  }

  return tilingMatrix[rowCount][0];
}

function __main__() {
  const argsSchema = { "-r": "rowCount", "-c": "colCount" };
  const options = parseArgs(process.argv.slice(2), argsSchema);

  if (!options.rowCount || !options.colCount) {
    console.error(
      "Usage: node dominoTilingSolver.js -r <rowCount> -c <colCount>"
    );
    process.exit(1);
  }

  const result = calculateTotalTilingCombinations(options);
  console.log(result);
  process.exit(0);
}

__main__();

Cały program BigInt - dominoTilingSolver-BigInt.js

dominoTilingSolver-BigInt.js

Uruchomienie:

node dominoTilingSolver-BigInt.js -r <rowCount> -c <colCount>

Kod:

const { parseArgs } = require("./helpers");

function canSkipTwoBits(colIndex, colCount, currentMask, currentBit, nextBit) {
  return (
    colIndex + 1 < colCount &&
    !(currentMask & currentBit) &&
    !(currentMask & nextBit)
  );
}

function searchTileArrangements(params) {
  const {
    tilingMatrix,
    rowCount,
    colCount,
    rowIndex,
    colIndex,
    currentMask,
    nextMask,
  } = params;

  if (rowIndex === rowCount) {
    return;
  }

  if (colIndex >= colCount) {
    tilingMatrix[rowIndex + 1][nextMask] += tilingMatrix[rowIndex][currentMask];
    return;
  }

  const currentBit = BigInt(1) << BigInt(colIndex);
  const nextBit = BigInt(1) << BigInt(colIndex + 1);

  currentMask & currentBit
    ? searchTileArrangements({ ...params, colIndex: colIndex + 1 })
    : searchTileArrangements({
        ...params,
        colIndex: colIndex + 1,
        nextMask: nextMask | currentBit,
      });

  if (canSkipTwoBits(colIndex, colCount, currentMask, currentBit, nextBit)) {
    searchTileArrangements({ ...params, colIndex: colIndex + 2 });
  }
}

function createInitialTilingMatrix(rowCount, colCount) {
  return Array.from({ length: rowCount + 1 }, () =>
    new Array(1 << colCount).fill(BigInt(0))
  );
}

function calculateTotalTilingCombinations({ rowCount, colCount }) {
  const tilingMatrix = createInitialTilingMatrix(rowCount, colCount);
  tilingMatrix[0][0] = BigInt(1);

  for (let rowIndex = 0; rowIndex < rowCount; ++rowIndex) {
    for (let currentMask = 0; currentMask < 1 << colCount; ++currentMask) {
      searchTileArrangements({
        tilingMatrix,
        rowCount,
        colCount,
        rowIndex,
        colIndex: 0,
        currentMask: BigInt(currentMask),
        nextMask: BigInt(0),
      });
    }
  }

  return tilingMatrix[rowCount][0];
}

function __main__() {
  const argsSchema = { "-r": "rowCount", "-c": "colCount" };
  const options = parseArgs(process.argv.slice(2), argsSchema);

  if (!options.rowCount || !options.colCount) {
    console.error(
      "Usage: node dominoTilingSolver-BigInt.js -r <rowCount> -c <colCount>"
    );
    process.exit(1);
  }

  const result = calculateTotalTilingCombinations(options);
  console.log(result.toString());
  process.exit(0);
}

__main__();

Funkcje pomocnicze - helpers

helpers

Poniższa funkcja (parseCommandLineArguments.js) użyta jest w dominoTilingSolver.js oraz dominoTilingSolver-BigInt.js. Pozostałe funkcje wykorzystywane są w programie testowym oraz benchmarku.

/**
 * Parses command line arguments based on a provided schema.
 * @param {string[]} args The command line arguments.
 * @param {Object} schema The schema defining argument mappings.
 * @returns {Object} Parsed options with their corresponding values.
 */
function parseCommandLineArguments(args, schema) {
  const options = {};

  for (let i = 0; i < args.length; i++) {
    const currentArg = args[i];
    const nextArg = args[i + 1];

    if (schema[currentArg] && nextArg !== void 0) {
      options[schema[currentArg]] = parseInt(nextArg, 10);
      i++;
    }
  }

  return options;
}

module.exports = parseCommandLineArguments;

Wynik

Dane testowe wykorzystywane w testRunner.js oraz benchmarkRunner.js znajdują się w katalogu test-data na GitHubie.

Test runner

Do przetestowania algorytmu utworzony został program testRunner.js.

Uruchamiamy program za pomocą komendy w konsoli:

node testRunner.js

Wynik w konsoli dla wersji podstawowej:

Starting test execution...
Executing test 1 of 7 for dominoTilingSolver.js... Passed!
Executing test 2 of 7 for dominoTilingSolver.js... Passed!
Executing test 3 of 7 for dominoTilingSolver.js... Passed!
Executing test 4 of 7 for dominoTilingSolver.js... Passed!
Executing test 5 of 7 for dominoTilingSolver.js... Passed!
Executing test 6 of 7 for dominoTilingSolver.js... Passed!
Executing test 7 of 7 for dominoTilingSolver.js... Passed!
All tests completed successfully.

Benchmark runner

Obliczanie wydajności algorytmu odbywa się za pomocą programu benchmarkRunner.js. Głównym celem przedstawionego benchmarku nie jest pomiar wydajności na konkretnym urządzeniu, ale demonstracja różnic w wynikach w zależności od rozmiarów planszy.

Uruchomienie programu odbywa się w konsoli za pomocą komendy:

node benchmarkRunner.js -n <numberOfExecutions>

Gdzie n to liczba egzekucji programu.

Wynik w konsoli dla wersji podstawowej, dla 10 egzekucji:

Starting benchmark execution with 10 executions each...
Executing benchmark 1 of 7 for dominoTilingSolver.js... File saved: benchmark/dominoTilingSolver.js_1x2.txt
Executing benchmark 2 of 7 for dominoTilingSolver.js... File saved: benchmark/dominoTilingSolver.js_2x2.txt
Executing benchmark 3 of 7 for dominoTilingSolver.js... File saved: benchmark/dominoTilingSolver.js_4x4.txt
Executing benchmark 4 of 7 for dominoTilingSolver.js... File saved: benchmark/dominoTilingSolver.js_6x6.txt
Executing benchmark 5 of 7 for dominoTilingSolver.js... File saved: benchmark/dominoTilingSolver.js_8x8.txt
Executing benchmark 6 of 7 for dominoTilingSolver.js... File saved: benchmark/dominoTilingSolver.js_10x10.txt
Executing benchmark 7 of 7 for dominoTilingSolver.js... File saved: benchmark/dominoTilingSolver.js_12x12.txt
All benchmarks completed successfully.

Zapisane wyniki znajdują się w folderze benchmark.

Benchmark Integer - dominoTilingSolver.js

RozmiarŚredni wynik [ms]Ilość egzekucji
1x224.9421000
2x225.7491000
4x424.8761000
6x627.6031000
8x835.4531000
10x1094.1601000
12x12505.8181000

Benchmark BigInt - dominoTilingSolver-BigInt.js

RozmiarŚredni wynik [ms]Ilość egzekucji
1x228.2801000
2x229.0051000
4x428.5941000
6x631.3351000
8x844.9041000
10x10145.0331000
12x12833.9031000
14x145,615.20010
16x1637,765.40010
18x18248,372.0001
20x201,640,246.0001

Źródła

  1. Richard Kenyon (2003), "An introduction to the dimer model", arXiv:math/0310326.
  2. The On-Line Encyclopedia of Integer Sequences (OEIS), "Number of domino tilings (or dimer coverings) of a 2n X 2n square", oeis.org/A004003.
  3. Wikipedia, "Domino tiling", en.wikipedia.org/wiki/Domino_tiling.
Profile picture

Dawid Ryłko
Github | Twitter | Linkedin

Copyright © 2024 Dawid Ryłko