C#八皇后算法：回溯法 vs 列优先法 vs 行优先法 vs 对角线优先法

目录

1.八皇后算法（Eight Queens Puzzle）

2.常见的八皇后算法解决方案

（1）列优先法（Column-First Method）：

（2）行优先法（Row-First Method）：

（3）对角线优先法（Diagonal-First Method）：

（4）回溯法（Backtracking）：

---

1.八皇后算法（Eight Queens Puzzle）

       皇后问题是一个古老而著名的问题，它实质上就是使棋盘上的8个皇后不能在同一行、同一列或同一条斜线上，共有92种方案。

2.常见的八皇后算法解决方案

        八皇后算法的解决方案有多种，以下是一些常见的解决方案：

（1）列优先法（Column-First Method）：

        八皇后问题是一个经典的回溯算法问题，可以使用列优先法（或称为逐列解决法）来解决。 首先选择一个空的棋盘，然后从第一行开始，尝试将皇后放置在每一列。如果当前列没有被攻击，那么就将皇后放置在该列。否则，尝试下一列。当找到一个有效的列时，将皇后放置在该列的最下方。重复这个过程，直到所有的皇后都被放置在棋盘上。

// 使用列优先法解决八皇后问题
// 列优先算法也叫逐列解决法namespace _144_4
{class Program{private const int Size = 8;private readonly int[] queens = new int[Size];               // 存储每行皇后的列位置private readonly bool[] columns = new bool[Size];            // 列是否已被占用private readonly bool[] diagonals1 = new bool[2 * Size - 1]; // 主对角线是否已被占用private readonly bool[] diagonals2 = new bool[2 * Size - 1]; // 副对角线是否已被占用public void Solve(){PlaceQueen(0);}int solnum = 0;private void PlaceQueen(int row){if (row == Size){solnum += 1;PrintQueens(solnum);  // 所有皇后都已放置，打印结果return;}for (int col = 0; col < Size; col++){if (IsSafe(row, col)){queens[row] = col;columns[col] = true;diagonals1[row - col + Size - 1] = true;diagonals2[row + col] = true;PlaceQueen(row + 1);// 回溯diagonals2[row + col] = false;diagonals1[row - col + Size - 1] = false;columns[col] = false;}}}private bool IsSafe(int row, int col){return !columns[col] && !diagonals1[row - col + Size - 1] && !diagonals2[row + col];}private void PrintQueens(int solnum){Console.WriteLine("Solution{0}: ", solnum);for (int i = 0; i < Size; i++){for (int j = 0; j < Size; j++){if (queens[i] == j){Console.Write("Q ");}else{Console.Write("* ");}}Console.WriteLine();}Console.WriteLine();}public static void Main(string[] args){ArgumentNullException.ThrowIfNull(args);Program solver = new();solver.Solve();}}
}

• 算法流程

        初始化所有数组。

        从第一行开始，尝试在每一列放置皇后。

        使用回溯法，如果在某一行找不到安全的位置，则返回到上一行并尝试下一个位置。

        当所有皇后都成功放置时，打印解决方案。

• 方法分析

        Solve()：启动算法，从第一行开始放置皇后。

        PlaceQueen(int row)：递归方法，尝试在当前行的每一列放置皇后。如果找到一个安全的位置，则递归地尝试放置下一个皇后。如果所有皇后都已成功放置，则打印解决方案。

        IsSafe(int row, int col)：检查在给定位置 (row, col) 放置皇后是否安全。如果列、主对角线和副对角线都没有被占用，则返回 true。

        PrintQueens(int solnum)：打印解决方案。对于每一行，如果当前列有皇后，则打印 "Q"，否则打印 "*"。

（2）行优先法（Row-First Method）：

        与列优先法类似，但不同之处在于，该方法从第一列开始，尝试将皇后放置在每一行。如果当前行没有被攻击，那么就将皇后放置在该行的最右侧。否则，尝试下一行。当找到一个有效的行时，将皇后放置在该行的当前列。重复这个过程，直到所有的皇后都被放置在棋盘上。

// 使用行优先法解决八皇后问题
// 行优先算法也叫回溯法
namespace _144_3
{class Program{static void Main(string[] args){ArgumentNullException.ThrowIfNull(args);List<int[]> solutions = [];int[] solution = new int[8];Solve(0, solution, solutions);foreach (int[] sol in solutions){for (int i = 0; i < 8; i++){for (int j = 0; j < 8; j++){if (j == sol[i]){Console.Write("Q ");}else{Console.Write(". ");}}Console.WriteLine();}Console.WriteLine();}}static void Solve(int row, int[] solution, List<int[]> solutions){if (row == solution.Length){//solutions.Add(solution.ToArray()); // Add a copy of the solutionsolutions.Add([.. solution]);return;}for (int col = 0; col < solution.Length; col++){if (IsSafe(row, col, solution)){solution[row] = col;Solve(row + 1, solution, solutions);}}}static bool IsSafe(int row, int col, int[] solution){for (int i = 0; i < row; i++){if (solution[i] == col ||Math.Abs(solution[i] - col) == Math.Abs(i - row)){return false;}}return true;}}
}

        代码使用了行优先法（也称为回溯法）来解决八皇后问题，这是一个经典的递归回溯问题。 代码分析：

• Main 方法

        Main 方法是程序的入口点。

        它首先检查 args 是否为空，如果为空则抛出异常。

        初始化一个空列表 solutions 来存储所有解决方案。

        调用 Solve 方法来寻找解决方案。

        遍历 solutions 列表，并打印出每一个解决方案。

• Solve 方法

        Solve 方法是递归函数，用于寻找八皇后问题的解决方案。

        如果当前行 row 等于解决方案数组的长度（即8），则找到一个解决方案，并将其添加到 solutions 列表中。

        对于当前行的每一列，检查是否安全（没有冲突），如果安全则在该列放置皇后，并递归调用 Solve 方法处理下一行。

• IsSafe 方法

        IsSafe 方法用于检查在当前位置 (row, col) 放置皇后是否安全。

        它遍历已经放置皇后的行，检查当前列和左上方对角线是否有冲突。

        如果没有冲突，返回 true；否则返回 false。

• 注意事项

        在 Main 方法中，使用了 ArgumentNullException.ThrowIfNull(args)； 来检查 args 是否为空。这通常用于命令行应用程序，但在没有实际命令行参数需求的程序中是不必要的。

        在 Solve 方法中，使用了 solutions.Add([.. solution]); 来添加解决方案的副本到 solutions 列表。这是C# 9.0引入的切片语法，用于创建数组或列表的浅拷贝。用这个简洁的方式来避免直接添加引用到同一个数组。

（3）对角线优先法（Diagonal-First Method）：

        该方法首先选择一个空的棋盘，然后从左上角开始，尝试将皇后放置在对角线上。如果当前对角线没有被攻击，那么就将皇后放置在该对角线的最下方。否则，尝试下一个对角线。当找到一个有效的对角线时，将皇后放置在该对角线的当前列。重复这个过程，直到所有的皇后都被放置在棋盘上。

// 八皇后算法_对角线优先法
namespace _144_2
{class Program{static void Main(string[] args){ArgumentNullException.ThrowIfNull(args);int n = 8;int[] queens = new int[n];List<int[]> solutions = [];SolveQueens(n, queens, 0, solutions);Console.WriteLine("Total solutions: " + solutions.Count);foreach (int[] solution in solutions){for (int i = 0; i < n; i++){for (int j = 0; j < n; j++){if (j == solution[i]){Console.Write("Q ");}else{Console.Write(". ");}}Console.WriteLine();}Console.WriteLine();}}static void SolveQueens(int n, int[] queens, int index, List<int[]> solutions){if (index == n){solutions.Add([.. queens]);return;}for (int i = 0; i < n; i++){if (CanPlaceQueen(queens, index, i)){queens[index] = i;SolveQueens(n, queens, index + 1, solutions);}}}static bool CanPlaceQueen(int[] queens, int index, int col){for (int i = 0; i < index; i++){if (queens[i] == col || Math.Abs(queens[i] - col) == index - i){return false;}}return true;}}
}

        在这个示例中，使用一个整数数组queens来表示棋盘上皇后的位置。queens数组的每个元素表示对应行上皇后的列位置。

        使用递归函数SolveQueens来解决八皇后问题。该函数接受当前皇后的位置、当前行号和已找到的解作为参数。在递归过程中，尝试在每一列上放置皇后，并检查是否满足问题的约束条件。如果满足，则将皇后放置在当前行的对应列上，并继续递归处理下一行。如果当前行的所有列都满足约束条件，则表示找到一个解，并将解添加到已找到的解列表中。

        函数CanPlaceQueen用于检查在给定位置放置皇后是否满足约束条件。它接受棋盘大小、当前皇后的位置、当前行号和当前列号作为参数。在函数中，遍历当前行号之前的行，检查当前列号是否已经放置了皇后，或者当前行和列上的皇后是否在同一条对角线上。如果满足任一条件，则表示不能在当前位置放置皇后。

        在Main函数中，输出找到的解决方案。对于每个解决方案，遍历8行8列，如果当前列是皇后的位置，则输出"Q"，否则输出"."。

（4）回溯法（Backtracking）：

        该方法通过递归的方式尝试所有可能的皇后位置。算法步骤如下：

• 选择一个空的棋盘。
• 选择一个皇后，将其放置在棋盘的第一行的任意一列。
• 选择下一个皇后，将其放置在下一行的任意一列，但不能与第一个皇后位于同一列或同一对角线上。
• 重复步骤3，直到所有的皇后都被放置在棋盘上。

// 八皇后算法_回溯法
namespace _144
{class Program{#region 八皇后算法/// <summary>/// 解决八皇后问题/// </summary>/// <param name="size">皇后数量</param>static void QueenArithmetic(int size){int[] Queen = new int[size];//每行皇后的位置int y, x, i, j, d, t = 0;y = 0;Queen[0] = -1;while (true){for (x = Queen[y] + 1; x < size; x++){for (i = 0; i < y; i++){j = Queen[i];d = y - i;//检查新皇后是否能与以前的皇后相互攻击if ((j == x) || (j == x - d) || (j == x + d))break;}if (i >= y)break;     //不攻击}if (x == size)     //没有合适的位置{if (0 == y){Console.WriteLine("Over");        //回溯到了第一行break;     //结束}Queen[y] = -1; //回溯y--;}else{Queen[y] = x;   //确定皇后的位置y++;            //下一个皇后if (y < size)Queen[y] = -1;else{Console.WriteLine("\n" + ++t + ':');//所有的皇后都排完了，输出for (i = 0; i < size; i++){for (j = 0; j < size; j++)Console.Write(Queen[i] == j ? 'Q' : '*');Console.WriteLine();}y = size - 1;//回溯}}}Console.ReadLine();}#endregionstatic void Main(string[] args){ArgumentNullException.ThrowIfNull(args);int size = 8;           //皇后数QueenArithmetic(size);}}
}