Füllen eines Gitters mit unregelmäßigen Formen

Question

Ich bin auf der Suche nach einem Algorithmus zu bestimmen, wie viele verschiedene Möglichkeiten gibt es ein 6x10 Gitter mit 12 spezifischen Tetris wie Stücke zu füllen.

Alle Teile bestehen aus jeweils fünf Blöcken und können frei gespiegelt und gedreht werden. Sie müssen alle in das Raster passen (ohne Überlappung) und es sollten keine Leerzeichen übrig bleiben.

Zusätzlich wird eine Anordnung nur dann als unterscheidbar angesehen, wenn es sich nicht um ein gespiegeltes oder gedrehtes Bild einer zuvor bestehenden Anordnung handelt.

habe ich gewählt jeden Rotationsschritt geben eigene Matrix ist, und die Darstellung der T-Blöcke würde wie folgt aussehen:

[ 
    0, 0, 0, 0, 0, 
    0, 1, 1, 1, 0, 
    0, 0, 1, 0, 0, 
    0, 0, 1, 0, 0, 
    0, 0, 0, 0, 0 
], 
[ 
    0, 0, 1, 0, 0, 
    0, 0, 1, 1, 1, 
    0, 0, 1, 0, 0, 
    0, 0, 0, 0, 0, 
    0, 0, 0, 0, 0 
], 
[ 
    0, 0, 1, 0, 0, 
    0, 0, 1, 0, 0, 
    0, 1, 1, 1, 0, 
    0, 0, 0, 0, 0, 
    0, 0, 0, 0, 0 
], 
[ 
    0, 0, 0, 1, 0, 
    0, 1, 1, 1, 0, 
    0, 0, 0, 1, 0, 
    0, 0, 0, 0, 0, 
    0, 0, 0, 0, 0 
] 

Mein erster Ansatz Brute-Force war; versuche jeden einzelnen Startpunkt mit einer Form und versuche dann alle anderen Teile nacheinander zu montieren, angefangen von der oberen linken Ecke.

Allerdings bin ich neugierig, ob jemand eine bessere Herangehensweise an dieses Problem hat?

Answer 1

Ich glaube im Allgemeinen können Sie nur Brute Force, wenn Sie einen bestimmten Fall haben (z. B. alle Stücke sind 2x2 Würfel). Sie können einige Tricks anwenden, wenn:

• wenn es nur ein „S“ -Form ist, können Sie ohne Beschränkung der Allgemeinheit annehmen, dass es in den linken oberen Quadranten ist, und multiplizieren das Ergebnis mit 4 plus vielleicht einigen Fällen, weil es auf der Achse ist;

• "nehmen Sie eine Kachel auf und versuchen Sie alle Positionen rekursiv" kann sich anders verhalten als "die erste verfügbare Position übernehmen und alle möglichen Kachelpassungen ausprobieren, die sie abdecken";

• Wenn es ein Loch einer Größe gibt, die nicht durch 4 teilbar ist, können Sie brechen;

• Wenn es ein Loch gibt, können Sie die Berechnung teilen (Anzahl der Möglichkeiten, um alles zu füllen = Anzahl der Möglichkeiten, das Loch zu füllen * Anzahl der Möglichkeiten, den Rest zu füllen);

und vielleicht einige mehr.