На самом деле не существует решения для квадратов на изображении.Я заставил это работать, изменив зеленое / синее основание на правой стороне последнего части к красному / белому основанию (как у части выше это имеет справа).
Рандомизация - плохая идея, этоЛучше сделать исчерпывающий поиск, где вы попробуете любую возможность, как ответил Петр Минчев.Вы можете ускорить его, предварительно обработав.За исключением первого фрагмента, вы всегда будете знать одну или две стороны, которые должны соответствовать.Каждый тип имеет только от 3 до 6 экземпляров среди всех 9 штук.Представьте, что у вас есть следующие пробелы:
0 1 2
3 4 5
6 7 8
Первоначально я сделал это, заполнив позицию 4, затем 1, 3, 5, 7 и, наконец, углы.Это нашло 4 решения за 3,5 миллисекунды с 2371 рекурсивными вызовами.Изменив порядок на 4, 1, 5, 2, 7, 8, 3, 0, 6, он упал до 1,2 миллисекунды только с 813 рекурсивными вызовами, потому что было меньше вариантов для размещения в углах.Если подумать об этом сейчас, то порядок будет где-то посередине, но измененный порядок будет таким же быстрым (0, 1, 3, 4, 2, 5, 6, 7, 8).Важно то, что проверка двух совпадений уменьшает количество повторных вызовов.
Step[] Steps = {
new Step() { Type = 0, Position = 4 },
new Step() { Type = 1, Position = 1, MatchP1 = 4, MatchO1 = 0 },
new Step() { Type = 1, Position = 5, MatchP1 = 4, MatchO1 = 1 },
new Step() { Type = 2, Position = 2, MatchP1 = 5, MatchO1 = 0, MatchP2 = 1, MatchO2 = 1 },
new Step() { Type = 1, Position = 7, MatchP1 = 4, MatchO1 = 2 },
new Step() { Type = 2, Position = 8, MatchP1 = 7, MatchO1 = 1, MatchP2 = 5, MatchO2 = 2 },
new Step() { Type = 1, Position = 3, MatchP1 = 4, MatchO1 = 3 },
new Step() { Type = 2, Position = 0, MatchP1 = 1, MatchO1 = 3, MatchP2 = 3, MatchO2 = 0 },
new Step() { Type = 2, Position = 6, MatchP1 = 3, MatchO1 = 2, MatchP2 = 7, MatchO2 = 3 },
};
Вот как настроены мои карты, обратите внимание, что я поменял одну из сторон напоследняя карта, чтобы получить решение.1 - красный, 2 - толстый, 3 - синий / зеленый и 4 - желтый.Я xor с 0x10, чтобы показать, что это низ того же цвета.Таким образом, вы можете xor 2 типа и сравнить с 0x10, чтобы увидеть, если они совпадают, или вы можете xor типа с 0x10, чтобы найти тип, который вы ищете.
Card[] cards = {
new Card(0x01, 0x03, 0x14, 0x12),
new Card(0x02, 0x14, 0x13, 0x01),
new Card(0x03, 0x11, 0x12, 0x04),
new Card(0x01, 0x13, 0x12, 0x04),
new Card(0x11, 0x13, 0x04, 0x03),
new Card(0x04, 0x11, 0x12, 0x01),
new Card(0x04, 0x02, 0x14, 0x13),
new Card(0x02, 0x14, 0x13, 0x01),
// new Card(0x01, 0x13, 0x12, 0x04) // no solution
new Card(0x01, 0x11, 0x12, 0x04) // 4 solutions
};
При предварительной обработке, я хочуУ меня есть массив, индексированный по типу, который я ищу, который даст мне все карты с этим типом и в какой ориентации этот тип включен.Я также добавляю NextType (по часовой стрелке), чтобы упростить сравнение углов:
public CardImageOrientation[][] Orientations { get; set; }
public struct CardImageOrientation
{
public int CardIndex;
public int TypePosition;
public int NextType;
}
// Orientations[1] is an array of CardImageOrientation structs
// that tell me what cards contain a side with type 1, what position
// it is in, and what the next type clockwise is
Вот мой основной рекурсивный метод:
public bool Method1Step(int stepIndex)
{
StepCalls++;
if (stepIndex > 8) // found a match
{
FindCount++;
return !Exhaustive; // false return value will keep going if exhaustive flag is true
}
Step step = Steps[stepIndex];
switch (step.Type)
{
case 0:
// step 0 we just loop through all cards and try them in position 4 with orientation 0
for (int i = 0; i < 9; i++)
{
PlaceCard(i, 4, 0);
steppedUp = true;
if (Method1Step(stepIndex + 1))
// found a solution, return true (will be false below for exhaustive)
return true;
RemoveCard(4);
}
break;
case 1:
case 2:
// step type 1 we simply try to match one edge with another, find card in position we are matching with
Card card = Cards[CardIndices[step.MatchP1]];
// to find the actual type in that position, we take the position we are looking for, subtract card orientation, add 4 and take the lowest two bits
int type = card.Types[(step.MatchO1 - card.Orientation + 4) & 0x03];
// find opposite orientation where we need to put the match in the empty spot
int orientation2 = (step.MatchO1 + 2) & 0x03;
// looking for type that is the opposite of the existing type
int searchType = type ^ 0x10;
for (int i = 0; i < Orientations[searchType].Length; i++)
{
// try one card value that matches
CardImageOrientation cio = Orientations[searchType][i];
// make sure it isn't in use
if (Cards[cio.CardIndex].Position < 0)
{
// check either we are step 1 or that second type matches as well
if (step.Type == 1 || (
step.Type == 2 &&
(Cards[CardIndices[step.MatchP2]].Types[(step.MatchO2 - Cards[CardIndices[step.MatchP2]].Orientation + 4) & 0x3] ^ cio.NextType) == 0x10)
) {
// get new orientation for card
int newOrientation = (orientation2 - cio.TypePosition + 4) & 0x03;
PlaceCard(cio.CardIndex, step.Position, newOrientation);
if (Method1Step(stepIndex + 1))
// found solution and non-exhaustive so return true
return true;
RemoveCard(step.Position);
}
}
}
break;
}
return false; // dead end or exhaustive search
}
Интересное примечание: я написал код для рандомизациикарты, использующие существующую модифицированную колоду с 4 решениями и 9999 других колод, созданных со случайными начальными значениями между 1 и 9999. Я нашел 3465 решений, распределенных по 1555 начальным макетам за 7,2 секунды, так что в среднем он составлял около 0,72 миллисекунды за цикл.В общей сложности было совершено 4,16 миллиона вызовов метода Method1Step ().