РЕДАКТИРОВАТЬ: я не заметил, что вы не можете использовать монету в качестве основного движения, если она не показывает хвосты. Это действительно делает порядок важным. Я оставлю этот ответ здесь, но также постараюсь написать еще один.
Здесь нет псевдокода, но подумайте об этом: можете ли вы когда-нибудь себе представить, что подбрасываете монету дважды? Какой будет эффект?
Альтернатива, запишите какую-нибудь произвольную доску (буквально, запишите ее). Установите несколько монет реального мира и выберите две произвольные, X и Y. Сделайте «X-flip», затем «Y-flip», затем другой «X-flip». Запишите результат. Теперь сбросьте доску на начальную версию и просто выполните «Y flip». Сравните результаты и подумайте о том, что произошло. Попробуйте несколько раз, иногда с X и Y близко друг к другу, иногда нет. Будьте уверены в своем заключении.
Эта линия мышления должна привести вас к определению конечного набора возможных решений. Вы можете проверить их все довольно легко.
Надеюсь, этот намек не был слишком вопиющим - я буду следить за этим вопросом, чтобы узнать, нужна ли вам дополнительная помощь. Это хорошая головоломка.
Что касается рекурсии: вы могли бы использовать рекурсию. Лично я бы не стал в этом случае.
РЕДАКТИРОВАТЬ: На самом деле, если подумать, я, вероятно, использовал бы рекурсию. Это может сделать жизнь намного проще.
Хорошо, возможно, этого было недостаточно очевидно. Давайте пометим монеты A-P следующим образом:
ABCD
EFGH
IJKL
MNOP
Flipping F всегда будет включать в себя следующие монеты, меняющие состояние: BEFGJ.
При подбрасывании J всегда изменяются следующие состояния монет: FIJKN.
Что произойдет, если вы подбросите монетку дважды? Два сальто отменяют друг друга, независимо от того, какие другие смещения происходят.
Другими словами, переключение F, а затем J - это то же самое, что переключение J, а затем F. Переключение F, а затем J, а затем снова F - это то же самое, что просто переключить J для начала.
Таким образом, любое решение на самом деле не является путем «переверни A, затем F, затем J» - это «переверни <эти монеты>; не переворачивай <эти монеты>». (К сожалению, слово «подбрасывание» используется как для переворачивания основной монеты, так и для вторичных монет, которые меняют состояние для конкретного хода, но не берите в голову - надеюсь, понятно, что я имею в виду.)
Каждая монета будет использоваться в качестве основного хода или нет, 0 или 1. Есть 16 монет, так что 2 ^ 16 возможностей. Таким образом, 0 может представлять «ничего не делать»; 1 может представлять «просто А»; 2 может представлять «просто B»; 3 "А и В" и т. Д.
Проверьте каждую комбинацию. Если (каким-то образом) существует более одного решения, подсчитайте количество бит в каждом решении, чтобы найти наименьшее число.
Подсказка к реализации: «текущее состояние» также может быть представлено в виде 16-битного числа. Использование конкретной монеты в качестве основного хода всегда будет XOR текущего состояния с фиксированным номером (для этой монеты). Это позволяет легко определить эффект от любой конкретной комбинации ходов.
Хорошо, вот решение в C #. Он показывает, сколько ходов потребовалось для каждого решения, которое он находит, но не отслеживает, какие это были ходы или какое наименьшее количество ходов. Это SMOP:)
Входные данные представляют собой список монет, с которых начинаются хвосты, поэтому для примера в вопросе вы должны запустить программу с аргументом "BEFGJLOP". Код:
using System;
public class CoinFlip
{
// All ints could really be ushorts, but ints are easier
// to work with
static readonly int[] MoveTransitions = CalculateMoveTransitions();
static int[] CalculateMoveTransitions()
{
int[] ret = new int[16];
for (int i=0; i < 16; i++)
{
int row = i / 4;
int col = i % 4;
ret[i] = PositionToBit(row, col) +
PositionToBit(row-1, col) +
PositionToBit(row+1, col) +
PositionToBit(row, col-1) +
PositionToBit(row, col+1);
}
return ret;
}
static int PositionToBit(int row, int col)
{
if (row < 0 || row > 3 || col < 0 || col > 3)
{
// Makes edge detection easier
return 0;
}
return 1 << (row * 4 + col);
}
static void Main(string[] args)
{
int initial = 0;
foreach (char c in args[0])
{
initial += 1 << (c-'A');
}
Console.WriteLine("Initial = {0}", initial);
ChangeState(initial, 0, 0);
}
static void ChangeState(int current, int nextCoin, int currentFlips)
{
// Reached the end. Success?
if (nextCoin == 16)
{
if (current == 0)
{
// More work required if we want to display the solution :)
Console.WriteLine("Found solution with {0} flips", currentFlips);
}
}
else
{
// Don't flip this coin
ChangeState(current, nextCoin+1, currentFlips);
// Or do...
ChangeState(current ^ MoveTransitions[nextCoin], nextCoin+1, currentFlips+1);
}
}
}