Мобильная версия
Я отметил зеленым цветом ячейки, которые может посещать начальная позиция. Вы можете двигаться только вверх, вниз, влево или вправо, но вы можете перемещаться на переменное расстояние. Например, вы можете переместить одну или три плитки вправо. Возвращаясь к этому примеру, я мог бы перейти на позиции 1, 2, 3, 4, 8 и 12 (я бы повторил это для всех 16 возможных стартовых позиций). Как набор пар это (0, 1), (0, 2), ..., (0, 12). Это вторая итерация.
Затем для каждой пары получим все возможные тройки. В примере, который я использую (0, 8). Итак, это (0, 1, 8), (0, 2, 8), (0, 3, 8), (0, 4, 8), (0, 8, 9), (0, 8, 10). , (0, 8, 11) и (0, 8, 12).
Я продолжаю повторять итерации до тех пор, пока не останется пустого места, но это медленно и использует много памяти. Я сохраняю позиции в виде битбордов. Он использует поиск в ширину. Мои оптимизации могут сократить слишком много и слишком рано, что приведет к тому, что не все комбинации будут найдены.
Код: Выделить всё
internal class ValidPositionGenerator
{
// Used to store new bitboards we need to check
private readonly Queue bitBoards = new Queue();
// Used to store unique bitboards we have found
private readonly HashSet visited = [];
public ValidPositionGenerator(int maxTiles)
{
int i = 0;
// This corresponds to the first iteration
while (i < 64)
{
bitBoards.Enqueue(CanonicalizeBitboard((ulong)Math.Pow(2, i)));
i++;
}
GenerateValid(bitBoards, maxTiles);
}
private void GenerateValid(Queue bitBoards, int maxTiles)
{
int i = 0;
while (bitBoards.Count != 0)
{
ulong board = bitBoards.Dequeue();
if (visited.Contains(board))
{
continue;
}
if (BitOperations.PopCount(board) > maxTiles)
{
continue;
}
visited.Add(board);
GetNewPositions(board, bitBoards, visited);
i++;
}
}
private static void GetNewPositions(ulong board, Queue bitBoards, HashSet visited)
{
// Get the active bits from board
List indices = GetIndices(board);
int i;
ulong canonical;
// Loop over each one and attempt to add each one to the output
foreach (int index in indices)
{
(int, int) pair = GetXYPairFromIndex(index);
// Up
i = 1;
while (pair.Item2 - i > -1)
{
// Check if the next bit is already set: Optimization 1
if (Util.GetBitboardCell(board, pair.Item1, pair.Item2 - i) == true)
{
break;
}
// Optimization 2, 3, and 4 happens inside CanonicalizeBitboard()
canonical = CanonicalizeBitboard(SetBitboardBit(board, pair.Item1, pair.Item2 - i, true));
if (!visited.Contains(canonical))
{
bitBoards.Enqueue(canonical);
}
i++;
}
// I've removed the rest to keep the code shorter
// Left
// Right
// Down
}
}
}
private static List GetIndices(ulong board)
{
ulong temp = board;
List indices = new List();
int index = 0;
while (board > 0)
{
if ((board & 1) == 1)
{
indices.Add(index);
}
board >>= 1;
index++;
}
return indices;
}
// Convert index to an x, y pair
private static (int, int) GetXYPairFromIndex(int index)
{
return (index % 8, index / 8);
}
}
Если я найду уже активную позицию, я могу остановиться, потому что могу продолжить оттуда. В приведенном ниже примере я нахожусь на (0, 2) и сканирую биты справа от 0. Когда я достигаю 2, это уже активно, поэтому я могу остановиться. Затем я продолжаю двигаться вниз влево, прежде чем сканировать биты около 2. Отсюда я продолжу движение вправо, получая все, что пропустил. Я не проверял, улучшит ли это что-либо.
Я думаю, оптимизация заключается в том, чтобы создать еще один битборд со всеми посещенными местами и остановиться, когда я найду что-то уже найденное. Потому что как только я доберусь до 2, он начнет сканировать влево к 0, но уже нашел все в этом направлении. Я думаю, что смогу объединить это с первой оптимизацией. Кажется, это продолжение.
Оптимизация 2: не сохранять зеркала и вращения
Каждая комбинация обладает симметрией, и мне нужно сохранить только одну . canonicalizeBitboard проверяет повороты и отражения, что уменьшает пространство поиска. Вместо хранения 16 возможностей в первой итерации мне нужно сохранить только 3: 0, 1 и 5.
Оптимизация 3: не хранить похожие переводы
Две сетки ниже для меня одинаковы. Поэтому, когда я канонизирую битборд, я также смещаю его так, чтобы он переместился в верхний левый угол.
[img]https:/ /i.sstatic.net/Qsc8BhLn.png[/img]
Оптимизация 4: Сокращенная версия
Учитывая следующие два битборда, меня интересуют только уникальные комбинации перемещения вверх, вниз, влево или вправо. Если я начну с 0, я смогу двигаться вправо и вниз в обоих из них, поэтому мне нужен только один. Я думаю, мне все равно придется сохранить его, когда я проверю наличие новых растровых изображений, но он мне не нужен для вывода. Меня это смущает и по поводу других моих оптимизаций. Я думаю, мне все равно следует их проверить, потому что позиция, которую я могу получить от них, может не соответствовать их сокращенной версии.
Заключение
Это все оптимизации, которые я могу придумать. Все, что я делаю, это нахожу все возможные комбинации/перестановки вверх, вниз, влево или вправо, где сумма левого и правого равняется размеру ширины битборда - 1, и аналогично с верхним и нижним, но с некоторыми дополнительными правилами. . Я думаю, что может быть способ отображения строки вверх, вниз, влево и вправо, которая отображается на каноническом битборде.
Что я пробовал
Мой код работает. Мне интересно, есть ли лучший способ. Когда я вызываю ValidPositionGenerator() с входным значением 6, это занимает 6 секунд и полгигабайта памяти. На 7 это занимает 2 минуты и 16 гигабайт. Очередь bitBoards взрывается, и это может быть неизбежно. Существует 2^64 возможных битборда, но я надеюсь, что мои оптимизации сделают это управляемым.
Подробнее здесь: https://stackoverflow.com/questions/793 ... binatorics
