DEV Community

Cover image for Domino tiling
Dawid Ryłko
Dawid Ryłko

Posted on • Originally published at dawidrylko.com on

Domino tiling

#math #javascript #datascience

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;

  ...
}
Enter fullscreen mode Exit fullscreen mode

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;
}
Enter fullscreen mode Exit fullscreen mode

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;
}
Enter fullscreen mode Exit fullscreen mode

Obliczanie bitów

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

const currentBit = 1 << colIndex;
const nextBit = 1 << (colIndex + 1);
Enter fullscreen mode Exit fullscreen mode

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,
    });
Enter fullscreen mode Exit fullscreen mode

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 });
}
Enter fullscreen mode Exit fullscreen mode

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)
  );
}
Enter fullscreen mode Exit fullscreen mode

Obliczanie ilości uładów

Wyodrębnienie funkcji calculateTotalTilingCombinations to kwestia gustu.

function calculateTotalTilingCombinations({ rowCount, colCount }) {
...
}
Enter fullscreen mode Exit fullscreen mode

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);
Enter fullscreen mode Exit fullscreen mode

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),
  );
}
Enter fullscreen mode Exit fullscreen mode

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;
Enter fullscreen mode Exit fullscreen mode

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,
    });
  }
}
Enter fullscreen mode Exit fullscreen mode

Zwrócenie wyniku 

return tilingMatrix[rowCount][0];
Enter fullscreen mode Exit fullscreen mode

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);
}
Enter fullscreen mode Exit fullscreen mode

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>
Enter fullscreen mode Exit fullscreen mode

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__();
Enter fullscreen mode Exit fullscreen mode

Cały program BigInt - dominoTilingSolver-BigInt.js

dominoTilingSolver-BigInt.js

Uruchomienie:

node dominoTilingSolver-BigInt.js -r <rowCount> -c <colCount>
Enter fullscreen mode Exit fullscreen mode

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__();
Enter fullscreen mode Exit fullscreen mode

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;
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

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.
Enter fullscreen mode Exit fullscreen mode

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>
Enter fullscreen mode Exit fullscreen mode

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.
Enter fullscreen mode Exit fullscreen mode

Zapisane wyniki znajdują się w folderze benchmark.

Benchmark Integer - dominoTilingSolver.js

Rozmiar Średni wynik [ms] Ilość egzekucji
1x2 24.942 1000
2x2 25.749 1000
4x4 24.876 1000
6x6 27.603 1000
8x8 35.453 1000
10x10 94.160 1000
12x12 505.818 1000

Benchmark BigInt - dominoTilingSolver-BigInt.js

Rozmiar Średni wynik [ms] Ilość egzekucji
1x2 28.280 1000
2x2 29.005 1000
4x4 28.594 1000
6x6 31.335 1000
8x8 44.904 1000
10x10 145.033 1000
12x12 833.903 1000
14x14 5,615.200 10
16x16 37,765.400 10
18x18 248,372.000 1
20x20 1,640,246.000 1

Ź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.

Top comments (0)

The discussion has been locked. New comments can't be added.

Read next

rezaghorbani profile image

Preact Setup: A Beginner's Guide

Reza Ghorbani -

joseph42a profile image

JavaScript Closures in Action: Real-World Applications

Joseph42A -

sanx profile image

Authentication and Authorization in Web Applications

Sanjay R -

thatohatsi880 profile image

The Document Object Model

Thatohatsi Matshidiso Tilodi -