如何找出八皇后问题的所有合法着色方案？

问题定义 #

设计的着色八皇后棋盘需满足以下规则：

• 每行必须恰好有一个皇后
• 每列必须恰好有一个皇后
• 皇后之间不能互相攻击（包括对角线方向）
• 每个颜色区域必须恰好包含一个皇后
• 同颜色的单元格必须通过边相连
• 必须恰好有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<Point>();
    
    //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[i].X;
        int y = list[i].Y;
        
        cells[x,y].Color = color;
    }
}

解决方案：遍历所有合法着色方案 #

核心逻辑 #

合法着色本质是将所有非皇后单元格分配给8个以皇后为起点的连通区域，每个区域对应唯一颜色，需满足：

1. 区域内所有单元格通过边相连
2. 所有非皇后单元格均被分配
3. 每个区域恰好包含一个皇后

具体实现步骤 #

1. 预处理棋盘

   • 为每个皇后分配唯一颜色（1-8），初始区域仅包含皇后自身
   • 收集所有非皇后的空白单元格，按某种顺序（如从左到右、从上到下）存入待分配列表

2. 回溯+剪枝算法
   通过递归遍历每个待分配单元格的合法颜色选项，逐步构建完整着色方案：

   // 全局或类级变量：保存所有合法方案
   private static List<Cell[,]> _allValidColorings = new List<Cell[,]>();
   
   public static void FindAllValidColorings(Cell[,] initialBoard)
   {
       _allValidColorings.Clear();
       // 复制初始棋盘，避免修改原数据
       Cell[,] board = CloneBoard(initialBoard);
       // 收集所有未着色的非皇后单元格
       List<Point> unassigned = GetUnassignedCells(board);
       
       Backtrack(board, unassigned);
   }
   
   private static void Backtrack(Cell[,] board, List<Point> unassigned)
   {
       if (unassigned.Count == 0)
       {
           // 保存当前棋盘的副本
           _allValidColorings.Add(CloneBoard(board));
           return;
       }
   
       // 优先处理可选颜色最少的单元格（启发式剪枝）
       int minOptionsIndex = FindCellWithMinValidColors(board, unassigned);
       Point current = unassigned[minOptionsIndex];
       unassigned.RemoveAt(minOptionsIndex);
   
       // 获取当前单元格的所有合法颜色（相邻已着色单元格的颜色）
       HashSet<int> validColors = GetValidAdjacentColors(board, current.X, current.Y);
   
       foreach (int color in validColors)
       {
           board[current.X, current.Y].Color = color;
           Backtrack(board, unassigned);
           // 回溯
           board[current.X, current.Y].Color = -1;
       }
   
       // 恢复单元格到待分配列表
       unassigned.Insert(minOptionsIndex, current);
   }
   
   // 辅助方法：获取单元格的合法相邻颜色
   private static HashSet<int> GetValidAdjacentColors(Cell[,] board, int x, int y)
   {
       HashSet<int> colors = new HashSet<int>();
       int[] dx = { -1, 1, 0, 0 };
       int[] dy = { 0, 0, -1, 1 };
   
       for (int i = 0; i < 4; i++)
       {
           int nx = x + dx[i];
           int ny = y + dy[i];
           if (InBoard(nx, ny) && board[nx, ny].Color != -1)
           {
               colors.Add(board[nx, ny].Color);
           }
       }
   
       return colors;
   }
   
   // 辅助方法：找到可选颜色最少的待分配单元格
   private static int FindCellWithMinValidColors(Cell[,] board, List<Point> unassigned)
   {
       int minCount = int.MaxValue;
       int index = 0;
   
       for (int i = 0; i < unassigned.Count; i++)
       {
           Point p = unassigned[i];
           int count = GetValidAdjacentColors(board, p.X, p.Y).Count;
           if (count < minCount)
           {
               minCount = count;
               index = i;
           }
       }
   
       return index;
   }
   
   // 辅助方法：复制整个棋盘
   private static Cell[,] CloneBoard(Cell[,] original)
   {
       int size = original.GetLength(0);
       Cell[,] clone = new Cell[size, size];
       for (int i = 0; i < size; i++)
       {
           for (int j = 0; j < size; j++)
           {
               clone[i, j] = (Cell)original[i, j].Clone();
           }
       }
       return clone;
   }
   
   // 辅助方法：收集未着色的非皇后单元格
   private static List<Point> GetUnassignedCells(Cell[,] board)
   {
       List<Point> list = new List<Point>();
       int size = board.GetLength(0);
       for (int i = 0; i < size; i++)
       {
           for (int j = 0; j < size; j++)
           {
               if (board[i, j].Status != CellStatus.Queen && board[i, j].Color == -1)
               {
                   list.Add(new Point(i, j));
               }
           }
       }
       return list;
   }
   
   // 辅助方法：判断坐标是否在棋盘内
   private static bool InBoard(int x, int y)
   {
       return x >= 0 && x < 8 && y >= 0 && y < 8;
   }
   

3. 优化策略

   • 最少剩余值启发式：优先处理可选颜色最少的单元格，大幅减少递归分支数
   • 对称性剪枝：若八皇后解存在翻转、旋转对称性，可只计算一种对称方案，避免生成重复等价的着色结果
   • 提前终止：若某个待分配单元格无合法颜色可选，直接回溯，无需继续递归

4. 去重处理
   由于颜色编号是人为赋予的（如交换皇后的颜色1和2，本质是同一着色方案），可约定颜色与皇后的绑定规则（比如按皇后所在行的顺序分配颜色1-8），避免生成重复的等价方案。

内容的提问来源于stack exchange，提问作者Ali Tor