查看完整版本: 皇后问题之C#版（非递归）

皇后问题之C#版（非递归）

using System;
    namespace sunjoy
    {
        public class Queen
        {
            public static int Main()
            {
                int board_size = 0,x=0,y=0;//棋盘大小,当前行,当前列
                uint solution_count = 0;   //皇后摆放方案的个数
                int[] rows, cols, slot1, slot2, x2y;//行占用情况，列占用情况，“/”状斜线占用情况，“\”状斜线占用情况，皇后坐标
                DateTime t_start, t_end;
               
                Console.WriteLine("请输入棋盘的大小");
                try
                {
                    board_size = Convert.ToInt32(Console.ReadLine());
                    if (board_size <= 0)
                    {
                        Console.WriteLine("非法数据");
                        return -1;
                    }
                }
                catch (Exception e) { Console.WriteLine("发生异常" + e.Message); };

                rows = new int[board_size];
                cols = new int[board_size];
                slot1 = new int[board_size * 2 - 1];
                slot2 = new int[board_size * 2 - 1];
                x2y = new int[board_size];

                for (int i = 0; i < board_size; i++)
                    x2y = -1;   //坐标初始化都为-1
                t_start = DateTime.Now;
                while (true)
                {
                    for (y = x2y[x]+1; y < board_size; y++)
                        if (rows[x] == 0 && cols[y] == 0 && slot1[x + y] == 0 && slot2[x - y + board_size - 1] == 0)
                            break;

                    if (y < board_size)
                    {
                        //第X行的棋子落下
                        rows[x] = 1; cols[y] = 1; slot1[x + y] = 1; slot2[x - y + board_size - 1] = 1; x2y[x] = y;
                    }  
                    else
                    {
                        //回溯，拿起棋子
                        if (x > 0)
                        {
                            x2y[x] = -1;
                            x--;
                            rows[x] = 0; cols[x2y[x]] = 0; slot1[x + x2y[x]] = 0; slot2[x - x2y[x] + board_size - 1] = 0;
                            continue;
                        }
                        else break;
                    }
                    if (x == board_size - 1)   //如果已经得到了一组解，即当最后一行棋子落定之时
                    {
                        for (int i = 0; i < board_size; i++)
                        {
                            for (int j = 0; j < board_size; j++)
                            {
                                if (x2y == j) Console.Write("Ｑ");
                                else Console.Write("■");
                            }
                            Console.Write("\n");
                           
                        }
                        Console.Write("\n");
                        solution_count++;   //总方案数加一
                        rows[x] = 0; cols[x2y[x]] = 0; slot1[x + x2y[x]] = 0; slot2[x - x2y[x] + board_size - 1] = 0;//放弃这一列

                    }
                    else
                    {
                        x++;   //继续处理下一行
                    }
                }
                t_end = DateTime.Now;
                Console.WriteLine("总共{0}组解",solution_count);
                Console.WriteLine("计算及打印共用时间{0}秒",t_end-t_start);
                return 0;
            }
        }
    }

    ___________________________________________________________

    测试结果:
    请输入棋盘的大小
    4
    ■Ｑ■■
    ■■■Ｑ
    Ｑ■■■
    ■■Ｑ■

    ■■Ｑ■
    Ｑ■■■
    ■■■Ｑ
    ■Ｑ■■

    总共2组解
    计算及打印共用时间00:00:00秒

    _______________________________________________
    请输入棋盘的大小
    6
    ■Ｑ■■■■
    ■■■Ｑ■■
    ■■■■■Ｑ
    Ｑ■■■■■
    ■■Ｑ■■■
    ■■■■Ｑ■

    ■■Ｑ■■■
    ■■■■■Ｑ
    ■Ｑ■■■■
    ■■■■Ｑ■
    Ｑ■■■■■
    ■■■Ｑ■■

    ■■■Ｑ■■
    Ｑ■■■■■
    ■■■■Ｑ■
    ■Ｑ■■■■
    ■■■■■Ｑ
    ■■Ｑ■■■

    ■■■■Ｑ■
    ■■Ｑ■■■
    Ｑ■■■■■
    ■■■■■Ｑ
    ■■■Ｑ■■
    ■Ｑ■■■■

    总共4组解
    计算及打印共用时间00:00:00.0156250秒

__a15 算法很差的人路过~~