Gibt es eine schnellere Möglichkeit zu überprüfen, ob die Nullen eines Bitboards ein Polyomino bilden? ⇐ C#

[Guest]

Die Methode, die ich verwende, ist sehr einfach zu verstehen und ich bin mir nicht sicher, wie ich sie schneller machen könnte, aber vielleicht gibt es eine andere Methode. Ich versuche herauszufinden, ob alle Nullen eines Bitboards ein Polyomino bilden. Die Definition, die ich verwende, ist eine beliebige Anordnung von Quadraten, sodass sie alle hochkant verbunden sind. Ich disqualifiziere eines nicht, weil ich bereits eine gespiegelte, gedrehte Version davon gesehen habe oder weil es umgedreht wurde oder ein Loch hat.
Ich mache das, indem ich die Anzahl der Nullen zähle. Dann finde ich die erste 0 und führe von dort aus eine Suche nach allem durch, was hochkant verbunden ist. Wenn die Anzahl der gefundenen Zellen der Anzahl der Nullen entspricht, handelt es sich um ein Polyomino. Andernfalls gäbe es Zellen, die es nicht erreichen könnte, und daher kein Polyomino.
Eine andere Idee, die ich hatte, bestand darin, jede Zeile durchzugehen und Inseln mit Nullen zu finden. Um das Verständnis zu erleichtern, würde ich es umdrehen und versuchen, Einseninseln zu finden.
Angenommen, wir haben zwei Zeilen:

Code: Select all

1 1 1 0 0 1 1 1
0 0 1 1 1 1 0 0

Die erste Zeile enthält zwei Inseln, 11100000 und 00000111, die ich mit a und b beschriften werde. Die zweite Reihe ist nur 1 Insel 00111100, die ich mit c beschriften werde.
Wenn ich a und c mit UND verknüpfe, kann ich erkennen, dass sie verbunden sind, weil sie gemeinsame Elemente haben. Das heißt a UND c > 0. Als nächstes sind auch b und c größer als 0. Das bedeutet, dass ich die Inseln a und b zusammenführen kann. Und dann wiederholen. Machen Sie grundsätzlich eine Schleife über jede Insel und jede andere Insel und führen Sie sie zusammen, wenn sie Gemeinsamkeiten haben. Wenn es fertig ist und jede Reihe zu einer Insel zusammengeführt wird, dann ist es ein Polyomino. Ich bin mir nur nicht sicher, ob das schneller gehen würde, denn es scheint eine Menge Arbeit zu sein, es in Inseln aufzuteilen.
Ich indiziere das Bitboard beginnend in der oberen linken Ecke , von links nach rechts gehen. Index + 1 ist also die Zelle rechts vom Index, während Index - 8 die Zelle über dem Index ist.

Code: Select all

public static bool PolyominoChecker(ulong bitboard)
{
// This should count the zeros
int population = 64 - BitOperations.PopCount(bitboard);

HashSet visited = new HashSet();
Queue queue = new Queue();

// Gets the first empty cell
visited.Add(BitOperations.TrailingZeroCount(~bitboard));
queue.Enqueue(BitOperations.TrailingZeroCount(~bitboard));

// This is a basic BFS
while (queue.Count > 0)
{
int index = queue.Dequeue();
// Checks the cell left of index
if(index % 8 > 0 && GetBitboardCell(bitboard, index - 1) == false)
{
if (!visited.Contains(index - 1))
{
visited.Add(index - 1);
queue.Enqueue(index - 1);
}
}
// Check the cell above index
if (index >= 8 && GetBitboardCell(bitboard, index - 8) == false)
{
if (!visited.Contains(index - 8))
{
visited.Add(index - 8);
queue.Enqueue(index - 8);
}
}
if (index + 8 < 64 && GetBitboardCell(bitboard, index + 8) == false)
{
if (!visited.Contains(index + 8))
{
visited.Add(index + 8);
queue.Enqueue(index + 8);
}
}
if (index % 8 < 7 && GetBitboardCell(bitboard, index + 1) == false)
{
if (!visited.Contains(index + 1))
{
visited.Add(index + 1);
queue.Enqueue(index + 1);
}
}
}

// If we visit all the empty cells, then it will equal the population of the empty cells
return visited.Count == population

public static bool GetBitboardCell(ulong bitboard, int index)
{
return (bitboard & (1UL