描述

在8*8的棋盘上摆放8个皇后，使其不能互相攻击，即：任意两个皇后，不能处于同一行，同一列或同一斜线上，问有多少种摆法

思路

1. 第一个皇后先放在第一行第一列
2. 第二个皇后放在，第二行第一列，然后判断这个位置会不会和其他的皇后互相攻击，OK就是这里 ，不OK就放第二列，第三列…….直到找到一个OK的位置
3. 继续第三个皇后……….如上第二步的操作
4. 如果后面步骤的皇后发现放位置都不行了，就回溯回去修改之前的步骤，移动之前皇后的位置后，进行下一个皇后的摆放
5. 当第八个皇后也放在正确的位置上了，就出现了一种解法。第八行继续移动列，找到合适的点，找不到了，然后开始回溯，之前的皇后不断的移动列的位置，直到回溯到了第一个皇后的位置，找到第一个皇后放在第一列的所有解
6. 然后第一个皇后放在第二列，又开始2，3，4，5的步骤，直到第一个皇后放到第八列，这时候就得到了所有解

   理论上应该创建一个二维数组表示棋盘，但实际上可以通过算法，用一个一维数组即可以解决问题 arr[8]={0,4,7,5,2,6,1,3}//arr索引表示第几行，即第几个皇后 arr[i]=val//val表示第i+1个皇后，放在第i+1行val+1列

代码

using System;
using System.Collections.Generic;
namespace ConsoleApp1
{
    class Program
    {
        //定义一个数用来表示共有多少个皇后
        static int max = 8;
        //定义一个数组，保存皇后放置位置的一个结果，比如arr = {0,4,7,5,2,1,3}
        static int[] array = new int[max];
        //解法统计
        static int count = 0;
        static void Main(string[] args)
        {
            check(0);
            Console.WriteLine($"一共有{count}种解法");
        }
        //编写一个方法,放置第n个皇后
        private static void check(int n)
        {
            if (n == max)//当n=8时,就表示全部皇后都放好了
            {
                print();
                return;
            }
            //依次放入皇后,并判断是否冲突
            for(int i = 0; i < max; i++)
            {
                //先把当前皇后n放在该行的第1列
                array[n] = i;
                //判断当当前皇后与其他皇后是否冲突
                if (judeg(n))//不冲突
                {
                    //不冲突就接着放下一行的皇后,就是n+1,即开始递归
                    check(n + 1);
                }
                //如果当前位置冲突了,不做其他的操作,他又回到了array[n]=i这一步,i进行了迭代
                //就是说,第n行第i列之后的摆法行不通,那就列往后移,试试第n行第i+1列的摆法,看后面的棋子行不行得通
            }
        }
        //查看当我们放置第n个皇后,就去检测该皇后是否和前面已经摆放的皇后冲突
        private static bool judeg(int n)
        {
            for(int i = 0; i < n; i++)
            {
                //1.array[i]==array[n],表示判断第n个皇后和第i个皇后是不是同一列
                //2.(array[n]-array[i])/(n-i)==1两点之间,直线的斜率,如果等于1,就说明这两个点是对角线
                //3.判断同一行?没有必要,n和i就是行,i<n
                if (array[i]==array[n]||Math.Abs(array[n]-array[i])==Math.Abs(n-i))
                {
                    return false;
                }
            }
            return true;
        }
        //写一个方法，可以将皇后摆放的位置输出
        private static void print()
        {
            count++;
            for(int i = 0; i < array.Length; i++)
            {
                Console.Write(array[i]+" ");
            }
            Console.WriteLine();
        }
    }
}