常用算法：C#八皇後問題

八皇後問題是一個古老而著名的問題，是回溯算法的典型應用。八皇後問題就是棋盤上的8個皇後不能在同一行、一列或一條斜線上，在8!=40320種排列中共有92種解決方案。代碼如下：

using System;

using System.Collections.Generic;

using System.Text;
namespace ExQueen

{

class Queen

{

public void QueenArithmetic(int size)
{
    int[] Queen = new int[size];//每行皇後的位置
    int y, x, i, j, d, t = 0;
    y = 0;
    Queen[0] = -1;
    while (true)
    {
        for (x = Queen[y] + 1; x < size; x++)
        {
            for (i = 0; i < y; i++)
            {
                j = Queen[i];
                d = y - i;
                //檢查新皇後是否能與以前的皇後相互攻擊
                if ((j == x) || (j == x - d) || (j == x + d))
                    break;
            }
            if (i >= y)
                break;//不攻擊
        }
        if (x == size) //沒有合適的位置
        {
            if (0 == y)
            {
                //回朔到了第一行
                Console.WriteLine("Over");
                break; //結束
            }
            //回朔
            Queen[y] = -1;
            y--;
        }
        else
        {
            Queen[y] = x;//確定皇後的位置
            y++;//下一個皇後
            if (y < size)
                Queen[y] = -1;
            else
            {
                //所有的皇後都排完了，輸出
                Console.WriteLine("\n" + ++t + ':');
                for (i = 0; i < size; i++)
                {
                    for (j = 0; j < size; j++)
                        Console.Write(Queen[i] == j ? 'Q' : '*');
                    Console.WriteLine();
                }
                y = size - 1;//回朔
            }
        }
    }
}
public static void Main()

{

int size = 8;//皇後數

Queen q = new Queen();

q.QueenArithmetic(size);

}

}

}