The method I'm using is very easy to understand and I'm not sure how I could make it any faster but maybe there's another method. I'm trying to find if all the 0s of a bitboard form a polyomino. The definition I'm using is any arrangement of squares such that they are all connected edgewise. I'm not disqualifying one because I've seen a mirrored, rotated version of it already or because it's been flipped over or has hole.
I do this by counting the number of 0s. Then I find the first 0 and from there perform a search looking for anything that is connected edgewise. If the number of cells it finds equals the number of 0s, then it was a polyomino. Otherwise, there would be cells it couldn't reach and therefore not be a polyomino.
Another idea I had involves going through each row and finding islands of 0s. To make it easier to understand, I would invert it and try to find islands of 1s.
Say we have two rows:
1 1 1 0 0 1 1 1
0 0 1 1 1 1 0 0
The first row contains two islands, 11100000 and 00000111 which I'll label a and b. The second row is only 1 island 00111100 which I'll label c.
If I AND a and c, then I can tell they are connected because they have elements in common. That is a AND c > 0. Next, b and c are also greater than 0. This means I can merge islands a and b. And then repeat. Basically, loop over each island which every other island and merge them if they have things in common. When it's done, if every row gets merged down to one island, then it's a polyomino. I'm just not sure if that would be faster because breaking it apart into islands seems like it would be a lot of work.
I'm indexing the bitboard starting in the upper left corner, going left to right. So index + 1 is the cell to the right of the index while index - 8 is the cell above index.
public static bool PolyominoChecker(ulong bitboard)
{
// This should count the zeros
int population = 64 - BitOperations.PopCount(bitboard);
HashSet<int> visited = new HashSet<int>();
Queue<int> queue = new Queue<int>();
// 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 << index)) != 0;
}
It looks like your bitboard uses 64 bits to represent an 8x8 grid.
At this size, it's practical to optimize this with a precomputed lookup table.
transition = transitions[state][new_byte]; state = transition&4095; islands += transition>>12. The table values are 16-bit integers, with the new state in the lower 12 bits and the cut-off island count in the upper 4 bits.The total number of islands cut off is then the total number of islands in the bit board.
With 835 states, the transitions table, which you would precompute, requires only 213760 16-bit integers, or about 512KB.
To determine all possible states, I suggest you make state 0 = no-land-at-all, and then recursively DFS over the tree of all states reachable from that. Use this row-based algorithm to calculate each new state from the previous one: Algorithm: use union find to count number of islands
Note that you are never required to actually determine what a state number means, so you don't need to invent some complicated encoding for column connectivities.
When you're calculating the table, each state can be a string of 8 digits, for example, where each digit is either 0 for water, the next unused non-zero digit for land that is not connected to anything on the left, or the previously used digit of land that it connects to.
You can then use a map from strings to integers to get a number for a state whenever you want.
Here's the whole state table computation, the bitboard testing function, and some tests:
/// <summary>
/// Map from the long-form state code for each state to the state number
/// see expandState.
///
/// This is only used during state table construction.
/// </summary>
Dictionary<string, ushort> stateNumbers = new Dictionary<string, ushort>();
/// <summary>
/// Packed map from (state*256 + next_row_byte) -> transition
///
/// transition is next_state + (island_count<<12), where island_count is the
/// number of islands cut off from the further rows
/// </summary>
List<ushort> transitions = new List<ushort>();
/// <summary>
/// The byte representing a row of all water. Note that this code counts
/// 0-islands, not 1-islands
/// </summary>
const byte ALL_WATER = (byte)0xFF;
#region Disjoint Set
/*
* Disjoint set the proper way. The sets are integers in an array:
* For each integer i
* - i === 0 => set is uninitialized (not yet a set)
* - i < 0 => set is a link to ~i
* - i >= 0 => set is of size i
*/
// find with path compression.
int find(int[] sets, int s)
{
int parent = sets[s];
if (parent > 0)
{
return s;
}
else if (parent < 0)
{
parent = find(sets, ~parent);
sets[s] = ~parent;
return parent;
}
else
{
sets[s] = 1;
return s;
}
}
// union by size
bool union(int[] sets, int x, int y)
{
x = find(sets, x);
y = find(sets, y);
if (x == y)
{
return false;
}
int szx = sets[x];
int szy = sets[y];
if (szx < szy)
{
sets[y] += szx;
sets[x] = ~y;
}
else
{
sets[x] += szy;
sets[y] = ~x;
}
return true;
}
#endregion
/// <summary>
/// Expands the specified state code.
///
/// A state code is a string of digits.
/// 0 => water
/// x => island number x. new islands are numbered from left to right
/// </summary>
/// <param name="stateCode">The state code to expand.</param>
/// <param name="nextrow">the lower 8 bits represent the next row. 0-bits are land</param>
/// <returns>The transition code for the transition from stateCode to nextrow</returns>
ushort expandState(string stateCode, int nextrow)
{
// convert the next row into a disjoint set array
// if you want to count 1-islands instead of 0-islands, change `~nextrow` into `nextrow` below,
// and fix the ALL_WATER constant
int[] sets = new int[8];
for (int i = 0; i < 8; ++i)
{
sets[i] = (~nextrow >> i) & 1;
}
for (int i = 0; i < 7; ++i)
{
if (((~nextrow >> i) & 3) == 3)
{
union(sets, i, i + 1);
}
}
// map from state code island to first attached set in sets
int[] links = [-1, -1, -1, -1, -1, -1, -1, -1];
int topIslandCount = 0;
for (int i = 0; i < 8; ++i)
{
char digit = stateCode[i];
int topisland = digit - '1';
topIslandCount = Math.Max(topIslandCount, topisland + 1);
if (sets[i] != 0 && topisland >= 0)
{
// connection from prev row to nextrow
int bottomSet = links[topisland];
if (bottomSet < 0)
{
// this island is not yet connected
links[topisland] = i;
}
else
{
// the top island is already connected. union bottom sets
union(sets, bottomSet, i);
}
}
}
// count the number of top-row islands that don't connect to the next row.
int cutOffCount = 0;
for (int i = 0; i < topIslandCount; ++i)
{
if (links[i] < 0)
{
++cutOffCount;
}
}
// turn the new union-find array into a state code
char nextSet = '1';
char[] newChars = "00000000".ToCharArray();
for (int i = 0; i < 8; ++i)
{
links[i] = -1;
}
for (int i = 0; i < 8; ++i)
{
if (sets[i] != 0)
{
int set = find(sets, i);
int link = links[set];
if (link >= 0)
{
newChars[i] = newChars[link];
}
else
{
newChars[i] = nextSet++;
links[set] = i;
}
}
}
string newStateCode = new string(newChars);
// get the state number
if (stateNumbers.ContainsKey(newStateCode))
{
// state already exists and is/will be expanded
return (ushort)(stateNumbers[newStateCode] | (cutOffCount << 12));
}
ushort newState = (ushort)stateNumbers.Count;
stateNumbers.Add(newStateCode, newState);
// fill out the state table
while (transitions.Count <= (newState + 1) * 256)
{
transitions.Add(0);
}
for (int i = 0; i < 256; ++i)
{
transitions[newState * 256 + i] = expandState(newStateCode, i);
}
return (ushort)(newState | (cutOffCount << 12));
}
int startState = expandState("00000000", ALL_WATER);
Console.WriteLine(startState);
Console.WriteLine(stateNumbers.Count);
int Count0Islands(ulong bitboard)
{
int state = 0;
int count = 0;
for (int i = 0; i < 8; ++i)
{
var transition = transitions[state * 256 + (int)(bitboard & 0xFF)];
count += transition >> 12;
state = transition & 0xFFF;
bitboard >>= 8;
}
// transition to ALL_WATER to count last islands
count += transitions[state * 256 + ALL_WATER] >> 12;
return count;
}
ulong[] tests = {
0x7e220a7e4a58580Ful,
0x7e22087e4a58580Ful,
0xFFFFFFFFFFFFFFFFul,
0x813c425a5a423c81ul
};
foreach (ulong test in tests)
{
Console.WriteLine();
Console.WriteLine();
for (int row = 0; row < 8; ++row)
{
int rowByte = (int)(test >> (row * 8)) & 0xFF;
string rowStr = Convert.ToString(rowByte, 2).PadLeft(8, '0');
rowStr = rowStr.Replace("1", " ");
rowStr = rowStr.Replace("0", "#");
Console.WriteLine(rowStr);
}
Console.WriteLine();
Console.WriteLine("Islands: " + Count0Islands(test));
}
Note that this counts 0-islands as you require. Comments in the code indicate how to switch it to counting 1-islands if you like.