Как найти все возможные раскраски в восьми проблем с королевой? ⇐ C#

[Anonymous]

Я сделал доску для раскрашенной задачи на восемь ферзей, которая соответствует приведенным ниже правилам.

• В каждом ряду должен быть ровно один ферзь
• В каждом столбце должен быть ровно один ферзь.
• Ферзи не могут касаться друг друга даже по диагонали.
• В каждой цветовой области должен быть ровно один ферзь< /li>
  Клетки одного цвета должны быть соединены друг с другом одним краем
• Областей должно быть ровно 8
• Каждый цвет должен располагать хотя бы одну ячейку (маточку)

Пример:


У меня есть код, на который можно поставить ферзей неокрашенная доска. Но я изо всех сил пытаюсь найти все возможные раскрашенные доски.
У меня есть метод, позволяющий случайным образом установить цвета в соответствии с правилами игры. Но как найти все возможные раскраски решения?
public class Cell : ICloneable
{
public object Clone()
{
return new Cell(this.Status, this.Color);
}

public Cell(CellStatus status, int color)
{
this.Status = status;
this.Color = color;
}

public Cell()
{

}

public CellStatus Status { get; set; }
public int Color { get; set; }
}

public enum CellStatus
{
Empty,
Queen, //Q
NotAvailable //X
}

public static void SetAllColors(Cell[,] cells)
{
int color = 0;
//set initial different colors every queen cell
for (int i = 0; i < 8; i++)
{
for (int j = 0; j < 8; j++)
{
if (cells[i, j].Status == CellStatus.Queen)
{
color += 1;
cells[i, j].Color = color;
}
}
}

//fill remaining cells following the rules 4,5,6,7
while (EmptyCellExists(cells))
for (int i = 0; i < 8; i++)
{
for (int j = 0; j < 8; j++)
{
if (cells[i, j].Color != -1)
{
SetColorToNeighbourCell(cells, i, j, cells[i, j].Color);
}
}
}
}

public static void SetColorToNeighbourCell(Cell[,] cells, int a, int b, int color)
{

//find vertical and horizontal neighbour cells
int x1 = a - 1;
int x2 = a + 1;
int y1 = b - 1;
int y2 = b + 1;
var list = new List();

//check the neighbour cells if it is on the board and if it is available to set color
if(InBoard(x1,b) && cells[x1,b].Status != CellStatus.Queen && cells[x1,b].Color == -1)
list.Add(new Point(x1,b));
if(InBoard(x2,b) && cells[x2,b].Status != CellStatus.Queen && cells[x2,b].Color == -1)
list.Add(new Point(x2,b));
if(InBoard(a,y1) && cells[a,y1].Status != CellStatus.Queen && cells[a,y1].Color == -1)
list.Add(new Point(a,y1));
if(InBoard(a,y2) && cells[a,y2].Status != CellStatus.Queen && cells[a, y2].Color == -1)
list.Add(new Point(a,y2));

//if there is no suitable neighbour
if(list.Count < 1)
return;

//randomly select a neighbour
int i = rnd.Next(0, list.Count);

//randomly choose if we place a color to the selected cell or not, %50
int j = rnd.Next(0, 2);

if(j == 0)
{
int x = list.X;
int y = list.Y;

cells[x,y].Color = color;
}
}


Подробнее здесь: https://stackoverflow.com/questions/793 ... en-problem