問題描述：在n*n的二維表格，把n個皇后在表格上，要求同一行、同一列或同一斜線上不能有2個以上的皇后。

例如八皇后有92種解決方案，五皇后有10種解決方案。

public class TestQueen {

int n; //皇后的個數

int num = 0; // 記錄方案數

int[] queenCol; // 記錄n個皇后所占用的列號

boolean[] col; // 列安全標志

boolean[] diagonal; // 對角線安全標志

boolean[] undiagonal; // 反對角線安全標志

public TestQueen(int n) {

this.n = n;

queenCol = new int[n];

col = new boolean[n];

diagonal = new boolean[2 * n - 1];

undiagonal = new boolean[2 * n - 1];

for (int i = 0; i < n; i++)

// 置所有列為安全

col[i] = true;

for (int t = 0; t < (2 * n - 1); t++)

// 置所有對角線為安全

diagonal[t] = undiagonal[t] = true;

}

public void run() {

solve(0);

if (num == 0) {

System.out.println(n + "皇后無解！");

}

}

// 從i行開始，把之后的皇后放好

private void solve(int i) {

for (int j = 0; j < n; j++) {

if (col[j] && diagonal[i - j + n - 1] && undiagonal[i + j]) {

// 表示第i行第j列是安全的可以放皇后(i,j從0開始)

queenCol[i] = j;

col[j] = false; // 修改安全標志

diagonal[i - j + n - 1] = false;

undiagonal[i + j] = false;

if (i < n - 1) // 判斷是否放完n個皇后

{

solve(i + 1); // 未放完n個皇后則繼續放后面的

} else // 已經放完n個皇后

{

num++;

System.out.println("皇后擺放第" + num + "種方案:");

System.out.print("行分別為");

for (int k = 0; k < n; k++)

System.out.print(k + " ");

System.out.print("\n");

System.out.print("列分別為");

for (int k = 0; k < n; k++)

System.out.print(queenCol[k] + " ");

System.out.print("\n");

}

col[j] = true; // 修改安全標志，回溯

diagonal[i - j + n - 1] = true;

undiagonal[i + j] = true;

}

}

}

public static void main(String[] args) {

TestQueen q = new TestQueen(5);

q.run();

}

}

輸出結果：

皇后擺放第1種方案:

行分別為0 1 2 3 4

列分別為0 2 4 1 3

皇后擺放第2種方案:

行分別為0 1 2 3 4

列分別為0 3 1 4 2

皇后擺放第3種方案:

行分別為0 1 2 3 4

列分別為1 3 0 2 4

皇后擺放第4種方案:

行分別為0 1 2 3 4

列分別為1 4 2 0 3

皇后擺放第5種方案:

行分別為0 1 2 3 4

列分別為2 0 3 1 4

皇后擺放第6種方案:

行分別為0 1 2 3 4

列分別為2 4 1 3 0

皇后擺放第7種方案:

行分別為0 1 2 3 4

列分別為3 0 2 4 1

皇后擺放第8種方案:

行分別為0 1 2 3 4

列分別為3 1 4 2 0

皇后擺放第9種方案:

行分別為0 1 2 3 4

列分別為4 1 3 0 2

皇后擺放第10種方案:

行分別為0 1 2 3 4

列分別為4 2 0 3 1

分享到：

2011-10-19 20:51

瀏覽 1957

評論