Оказывается, это не должно быть слишком плохо для грубой силы, по крайней мере, если ваша доска не слишком большая.
Вы можете определить свой набор бомб, где каждая ячейка может быть Present,Not Present или Unexplored, где Unexplored означает, что там может быть или не быть бомба.Затем вы можете написать метод, который берет вашу доску и этот набор бомб и определяет, является ли доска недействительной или может быть действительной в зависимости от действительного значения любых Unexplored ячеек.
Затем вы начинаетеходить по доске.Установите в первой ячейке значение Present и посмотрите, не приведет ли это к доске, которая может быть действительной (или, безусловно, недействительной).Если это возможно, установите recurse на следующую ячейку.Затем установите первую ячейку на NotPresent и посмотрите, может ли , что может быть действительным, и если она вернется в следующую ячейку.
Это сокращение досок с небольшой площадью, котораяНедопустимый должен значительно сократить пространство поиска по сравнению с полным перебором.
Когда вы проверяете, может ли доска быть действительной, вы можете оптимизировать ее, проверяя только ячейки в квадрате вокруг ячейки, которую выизменено, так как это единственные, которые могут быть затронуты.
Это не полноценное динамическое программирование, и, вероятно, выиграет от некоторого запоминания: если в правом нижнем углу есть комбинация бомб, которая недопустима(нижний правый угол является последней исследованной областью), он будет продолжать пробовать их снова и снова с различными (действительными) комбинациями бомб в других местах.
Это также сработает, если у вашей доски большая открытая область, так как будет большое количество комбинаций, и это тщательно изучит каждую из них.
Я собрал немного C # дляпроиллюстрировать мою идею.Это не опрятно или не совсем ясно (и за это я прошу прощения - у меня не хватило времени, чтобы привести его в порядок), но он находит 4 решения для вашего второго примера.
Это написано с использованием рекурсии, поэтому будет ударстек с большими досками.Перепишите его, чтобы оно было повторяющимся.
class Program
{
static void Main(string[] args)
{
var board = new Board(new CellState[,]
{
{ CellState.Odd, CellState.None },
{ CellState.Odd, CellState.None },
{ CellState.Odd, CellState.Even }
});
var bombs = new BombState[board.Height, board.Width];
int numSolutions = 0;
Explore(board, bombs, 0, 0, ref numSolutions);
}
private static void Explore(Board board, BombState[,] bombs, int x, int y, ref int numSolutions)
{
int nextX = x + 1;
int nextY = y;
if (nextX >= board.Width)
{
nextX = 0;
nextY++;
}
bombs[y, x] = BombState.Present;
if (board.DetermineValidity(bombs, x, y))
{
if (nextY >= board.Height)
numSolutions++;
else
Explore(board, bombs, nextX, nextY, ref numSolutions);
}
bombs[y, x] = BombState.NotPresent;
if (board.DetermineValidity(bombs, x, y))
{
if (nextY >= board.Height)
numSolutions++;
else
Explore(board, bombs, nextX, nextY, ref numSolutions);
}
bombs[y, x] = BombState.Unexplored;
}
}
public enum CellState
{
Odd,
Even,
None,
}
public enum BombState
{
Unexplored,
Present,
NotPresent,
}
public class Board
{
private readonly CellState[,] cells;
public int Width { get; }
public int Height { get; }
public Board(CellState[,] cells)
{
this.cells = cells;
this.Width = cells.GetLength(1);
this.Height = cells.GetLength(0);
}
// Takes a board of bombs, and the position of a bomb to inspect, and determines
// whether that bomb position is definitely valid, or is unknown/invalid
public bool DetermineValidity(BombState[,] bombs, int changedX, int changedY)
{
// We only need to consider the cells in a square around the cell which was just changed
for (int x = Math.Max(0, changedX - 1); x < Math.Min(this.Width, changedX + 1); x++)
{
for (int y = Math.Max(0, changedY - 1); y < Math.Min(this.Height, changedY + 1); y++)
{
var cellState = this.cells[y, x];
// If this is a "None", there's nothing to check
if (cellState == CellState.None)
continue;
// For each cell, check its neighbours... If they're all specified, get the number of boms
int numBombs = 0;
bool areAllSpecified = true;
if (x > 0)
InspectNeighbour(bombs[y, x - 1], ref numBombs, ref areAllSpecified);
if (areAllSpecified && x < this.Width - 1)
InspectNeighbour(bombs[y, x + 1], ref numBombs, ref areAllSpecified);
if (areAllSpecified && y > 0)
InspectNeighbour(bombs[y - 1, x], ref numBombs, ref areAllSpecified);
if (areAllSpecified && y < this.Height - 1)
InspectNeighbour(bombs[y + 1, x], ref numBombs, ref areAllSpecified);
if (areAllSpecified && ((numBombs % 2) == 0) != (cellState == CellState.Even))
return false;
}
}
return true;
}
private static void InspectNeighbour(BombState state, ref int numBombs, ref bool areAllSpecified)
{
switch (state)
{
case BombState.NotPresent:
break;
case BombState.Present:
numBombs++;
break;
case BombState.Unexplored:
areAllSpecified = false;
break;
}
}
}