C#中八皇后问题的递归解法——N皇后

百度测试部2015年10月份的面试题之——八皇后。

八皇后问题的介绍在此。以下是用递归思想实现八皇后-N皇后。

代码如下:

using System;using System.Collections.Generic;

namespace QueensSolution
{
    class Program
    {
        static int count = 0;
        static void Main(string[] args)
        {
            int n = Int32.Parse(Console.ReadLine());
            List<int> queen = new List<int>(n);
            for (int i = 1; i <= n; i++)
            {
                queen.Add(0);
            }
            PutQueen(n, queen, 0);
            Console.WriteLine(count);
            Console.ReadKey();
        }

        private static void PutQueen(int n, List<int> queen, int row)
        {
            for (queen[row] = 1; queen[row] <= n; queen[row]++)
            {
                if (CheckQueens(queen, row))
                {
                    row++;
                    if (row < n)
                    {
                        PutQueen(n, queen, row);
                    }
                    else
                    {
                        count++;
                        for (int i = 0; i < n; i++)
                        {
                            Console.Write(queen[i].ToString() + " ");
                        }
                        Console.WriteLine();
                    }
                    row--;
                }
            }
        }

        private static bool CheckQueens(List<int> queen, int row)
        {
            for (int i = 0; i < row; i++)
            {
                if (Math.Abs(queen[i] - queen[row]) == Math.Abs(i - row) || queen[i] == queen[row])
                {
                    return false;
                }
            }
            return true;
        }
    }
}

解释:

1.要想解出在n*n的棋盘上到底有多少种放置皇后的方法,主要用到两个方法,放皇后的PutQueen方法,检查皇后的CheckQueens方法。

2.在Main函数里对动态数组进行初始化,这个动态数组用来记录N皇后中每一行所放置的皇后的位置(1就代表放置在该行第一列,n就代表放置在该行的第n列)。

3.row代表的是八皇后棋盘的每一行。

4.在Main函数中对动态数组进行了一下初始化,这一步是必须的,否则运行结果报错。

5.变量count(解的个数)声明在Main函数外,是静态的。

6.PutQueen方法采用递归思想——放皇后(该行中每一列都要放置),检查放皇后的位置是否合理,如果合理则到下一行,判断下一行是否存在,如果存在——放皇后(该行中每一列都要放置),检查放皇后的位置是否合理,如果合理则……直到不存在下一行为止每一行都已经放置好了皇后,这时我们将解的个数记录一下(count++),然后打印该种解法。

7.在递归结束后,一定要记得返回到上一行(row--),这样才能让“for (queen[row] = 1; queen[row] <= n; queen[row]++)”生效,实现每一行中的每一列都放置过皇后。一定要注意row--的位置要放在整个if-else语句块的后面!因为整个if-else语句块形成了对递归过程中状态的判断,有两种状态,第一种状态是皇后当前在第2到n-1行,这时候如果想返回上一行,“row--”的位置其实可以写在if语句块中"PutQueen(n, queen, row);"这一句的后面;第二种状态是皇后当前在最后一行(也就是第n行),这时候如果想返回上一行,“row--”的位置其实可以写在else语句块中。因此,我们才将“row--”的位置移到了整个if-else语句块的后面。

 

上一篇:Virtual PC 2007下虚拟机与本机双XP系统实现互联与上网详解


下一篇:编程珠玑--旋转算法