【算法】回溯

回溯，顾名思义就是搜索一个问题的一个解时，当没有可行解救回到根节点再进行遍历，直到所有解都遍历一遍。

回溯法基本思想

在确定了解空间的组织结构后，回溯法从开始结点（根节点）出发，以深度优先的方式搜索整个解空间。这个开始节点就成为了一个活结点，同时也成为当前的扩展结点。在当前的扩展结点处，搜索向纵深方向移至一个新结点。这个新结点就成为了一个新的活结点，并成为当前扩展结点。如果在当前扩展界定啊出不能再向纵深方向移动，则当前的扩展结点就成为死结点。换句话说这个结点不再是一个活结点。此时，应往回移动（回溯）至最近的有一个活结点处，并使这个活结点成为当前的扩展结点。回溯法即以这种工作凡是递归地解空间中搜索，直到找到所要求的解或解空间中已无活结点时为止。

步骤

用回溯算法解决问题的一般步骤为：

一、定义一个解空间，它包含问题的解。
二、利用适于搜索的方法组织解空间。
三、利用深度优先法搜索解空间。
四、利用限界函数避免移动到不可能产生解的子空间。问题的解空间通常是在搜索问题的解的过程中动态产生的，这是回溯算法的一个重要特性。

N皇后问题

这是来源于国际象棋的一个问题。N后问题要求在一个N x N格的棋盘上放置n个皇后，使得他们彼此不受攻击。按照国际象棋的规则，一个皇后可以攻击与之处在同一行或同一列或同一斜线上的其他任何棋子。因此，n后问题等价于要求在一个N x N格的棋盘上放置n个皇后，使得任何两个皇后不能被放在同一行或同一列或同一条斜线上。

    class Class1
    {
        static void Main(string[] args)
        {
            int n = 8;
            Queue(n);
            Console.ReadLine();
        }
 
        public static void Queue(int n)
        {
            int i;
            int index = 1; //第一个皇后
            int[] CNum = new int[n + 1];
            int ANum = 0;
 
            string sss = null;//定义一个空变量
            for (i = 1; i <= n; i++)
            {
                CNum[i] = 0;//初始化从第0列开始
            }
            while (index > 0)
            {
                CNum[index]++;//第index个皇后所在的列数
                while (CNum[index] <= n && !Place(CNum, index))  //寻找皇后的位置
                {
                    CNum[index]++;
                }
                if (CNum[index] <= n)
                {
                    if (index == n)//最后一个皇后放置成功
                    {
                        ANum++;//第几种可行方案 
                        sss = "\t " + "方法" + ANum + ":";                       
                        for (i = 1; i <= n; i++)
                        {
                            sss = sss + "   " + CNum[i];
                        }
                        Console.WriteLine(sss);
 
                        //for (i = 1; i <= n; i++)
 
                        //    CNum[index]++;
 
                    }
                    else //继续寻找下一个皇后的位置
                    {
                        index++; //皇后数+1
                        CNum[index] = 0;
                    }
                }
                else
                {
                    index--; //当前皇后无法放置，回溯至上一个皇后
                }
 
 
            }
        }
 
 
 
 
 
 
        public static bool Place(int[] Column, int index)  //Column--列  
        {
            int i;
            for (i = 1; i < index; i++)//如果index为3，那么就跟前两个皇后进行比较
            {
                int Columndiffer = System.Math.Abs(Column[index] - Column[i]);
                int Rowdiffer = System.Math.Abs(index - i);
                if (Column[i] == Column[index] || Columndiffer == Rowdiffer)//是否有皇后与其在同列或同一斜线上
                {
                    return false;
                }
            }
            return true; //没有皇后与其同行，同列或同对角线
        }
    }

来源

回溯算法（N皇后）–C#版代码
回溯-百度百科