using System;
using System.Collections.Generic;
using System.Text;

namespace AlgorithmEightQueen
{
    /// <summary>
    /// 八个皇后问题是典型的递归回溯求解的问题
    /// 在一个棋盘上放置8个皇后让他们的互相不“冲突”
    /// </summary>
    class Program
    {
        private const int N = 8;
        private static int[,] chess = new int[N + 1,N + 1];
        private static int AlreadyHode = 0;

        static void Main(string[] args)
        {
            //放置
            Lay(1);
        }

        /// <summary>
        /// 尝试放置第num个皇后
        /// </summary>
        /// <param name="num"></param>
        static void Lay(int num)
        {
            //是否已经全部占领完毕
            if(AlreadyHode >= N)
            {
                Console.WriteLine("占领的点如下:");
                for (int i = 1; i <= N; i++)
                {
                    for (int j = 1; j <= N; j++)
                    {
                        if (chess[i, j] == 1)
                            Console.Write("*");
                        else
                            Console.Write("-");
                    }
                    Console.WriteLine();
                }

                Console.ReadLine();
                return;
            }

            //访问棋盘的点 不冲突占领该点
            for (int i = 1; i <= N; i++)
            {
                for (int j = 1; j <= N; j++)
                {
                    if(Try(i, j))
                    {
                        //占领
                        chess[i, j] = 1;
                        AlreadyHode++;

                        //放置下一个皇后
                        Lay(num + 1);

                        //撤出
                        chess[i, j] = 0;
                        AlreadyHode--;
                    }
                }
            }
        }

        /// <summary>
        /// 判断点posX,posY是否能够占领
        /// </summary>
        /// <param name="posX"></param>
        /// <param name="posY"></param>
        /// <returns></returns>
        static bool Try(int posX,int posY)
        {
            //判断是否冲突
            //判断是否横向冲突
            for (int i = 1; i <= N; i++)
                if (chess[posX, i] == 1)
                    return false;
            //判断是否纵向冲突
            for (int i = 1; i <= N; i++)
                if (chess[i, posY] == 1)
                    return false;
            //判断是否斜向冲突
            for (int i = -(N - 1); i <= (N - 1); i++)
            {
                if (posX + i >= 1 && posX + i <= N && posY + i >= 1 && posY + i <= N && chess[posX + i, posY + i] == 1)
                    return false;
                if (posX + i >= 1 && posX + i <= N && posY - i >= 1 && posY - i <= N && chess[posX + i, posY - i] == 1)
                    return false;
            }

            return true;
        }
    }
}