皇后問題

八皇后問題是一個以國際象棋為背景的問題：如何能夠在 8×8 的國際象棋棋盤上放置八個皇后，使得任何一個皇后都無法直接吃掉其他的皇后？為了達(dá)到此目的，任兩個皇后都不能處于同一條橫行、縱行或斜線上。八皇后問題可以推廣為更一般的n皇后擺放問題：這時棋盤的大小變?yōu)閚1×n1，而皇后個數(shù)也變成n2。而且僅當(dāng) n2 ≥ 1 或 n1 ≥ 4 時問題有解。

皇后問題是非常著名的問題，作為一個棋盤類問題，毫無疑問，用暴力搜索的方法來做是一定可以得到正確答案的，但在有限的運(yùn)行時間內(nèi)，我們很難寫出速度可以忍受的搜索，部分棋盤問題的最優(yōu)解不是搜索，而是動態(tài)規(guī)劃，某些棋盤問題也很適合作為狀態(tài)壓縮思想的解釋例題。

進(jìn)一步說，皇后問題可以用人工智能相關(guān)算法和遺傳算法求解，可以用多線程技術(shù)縮短運(yùn)行時間。本文不做討論。

（本文不展開講狀態(tài)壓縮，以后再說）

一般思路：

N*N的二維數(shù)組，在每一個位置進(jìn)行嘗試，在當(dāng)前位置上判斷是否滿足放置皇后的條件（這一點(diǎn)的行、列、對角線上，沒有皇后）。

優(yōu)化1：

既然知道多個皇后不能在同一行，我們何必要在同一行的不同位置放多個來嘗試呢？

我們生成一維數(shù)組record，record[i]表示第i行的皇后放在了第幾列。對于每一行，確定當(dāng)前record值即可，因?yàn)槊啃兄荒芮冶仨毞乓粋€皇后，放了一個就無需繼續(xù)嘗試。那么對于當(dāng)前的record[i]，查看record[0...i-1]的值，是否有j = record[k]（同列）、|record[k] - j| = | k-i |（同一斜線）的情況。由于我們的策略，無需檢查行（每行只放一個）。

public class NQueens {

public static int num1(int n) {

if (n < 1) {

return 0;

}

int[] record = new int[n];

return process1(0, record, n);

}

public static int process1(int i, int[] record, int n) {

if (i == n) {

return 1;

}

int res = 0;

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

if (isValid(record, i, j)) {

record[i] = j;

res += process1(i + 1, record, n);

}

}//對于當(dāng)前行，依次嘗試每列

return res;

}

//判斷當(dāng)前位置是否可以放置

public static boolean isValid(int[] record, int i, int j) {

for (int k = 0; k < i; k++) {

if (j == record[k] || Math.abs(record[k] - j) == Math.abs(i - k)) {

return false;

}

}

return true;

}

public static void main(String[] args) {

int n = 8;

System.out.println(num1(n));

}

}

優(yōu)化2：

分析：棋子對后續(xù)過程的影響范圍：本行、本列、左右斜線。

黑色棋子影響區(qū)域?yàn)榧t色

本行影響不提，根據(jù)優(yōu)化一已經(jīng)避免

本列影響，一直影響D列，直到第一行在D放棋子的所有情況結(jié)束。

左斜線：每向下一行，實(shí)際上對當(dāng)前行的影響區(qū)域就向左移動

比如：

嘗試第二行時，黑色棋子影響的是我們的第三列；

嘗試第三行時，黑色棋子影響的是我們的第二列；

嘗試第四行時，黑色棋子影響的是我們的第一列；

嘗試第五行及以后幾行，黑色棋子對我們并無影響。

右斜線則相反：

隨著行序號增加，影響的列序號也增加，直到影響的列序號大于8就不再影響。

我們對于之前棋子影響的區(qū)域，可以用二進(jìn)制數(shù)字來表示，比如:

每一位，用01代表是否影響。

比如上圖，對于第一行，就是00010000

嘗試第二行時，數(shù)字變?yōu)?0100000

第三行：01000000

第四行：10000000

對于右斜線的數(shù)字，同理：

第一行00010000，之后向右移：00001000，00000100，00000010，00000001，直到全0不影響。

同理，我們對于多行數(shù)據(jù)，也同樣可以記錄了

比如在第一行我們放在了第四列：

第二行放在了G列，這時左斜線記錄為00100000（第一個棋子的影響）+00000010（當(dāng)前棋子的影響）=00100010。

到第三行數(shù)字繼續(xù)左移：01000100，然后繼續(xù)加上我們的選擇，如此反復(fù)。

這樣，我們對于當(dāng)前位置的判斷，其實(shí)可以通過左斜線變量、右斜線變量、列變量，按位或運(yùn)算求出（每一位中，三個數(shù)有一個是1就不能再放）。

具體看代碼：

注：怎么排版就炸了呢。。。貼一張圖吧

public class NQueens {

public static int num2(int n) {

// 因?yàn)楸痉椒ㄖ形贿\(yùn)算的載體是int型變量，所以該方法只能算1~32皇后問題

// 如果想計(jì)算更多的皇后問題，需使用包含更多位的變量

if (n < 1 || n > 32) {

return 0;

}

int upperLim = n == 32 ? -1 : (1 << n) - 1;

//upperLim的作用為棋盤大小，比如8皇后為00000000 00000000 00000000 11111111

//32皇后為11111111 11111111 11111111 11111111

return process2(upperLim, 0, 0, 0);

}

public static int process2(int upperLim, int colLim, int leftDiaLim,

int rightDiaLim) {

if (colLim == upperLim) {

return 1;

}

int pos = 0; //pos：所有的合法位置

int mostRightOne = 0; //所有合法位置的最右位置

//所有記錄按位或之后取反，并與全1按位與，得出所有合法位置

pos = upperLim & (~(colLim | leftDiaLim | rightDiaLim));

int res = 0;//計(jì)數(shù)

while (pos != 0) {

mostRightOne = pos & (~pos + 1);//取最右的合法位置

pos = pos - mostRightOne; //去掉本位置并嘗試

res += process2(

upperLim, //全局

colLim | mostRightOne, //列記錄

//之前列+本位置

(leftDiaLim | mostRightOne) << 1, //左斜線記錄

//（左斜線變量+本位置）左移

(rightDiaLim | mostRightOne) >>> 1); //右斜線記錄

//（右斜線變量+本位置）右移（高位補(bǔ)零）

}

return res;

}

public static void main(String[] args) {

int n = 8;

System.out.println(num2(n));

}

}

完整測試代碼：

32皇后：結(jié)果/時間

暴力搜：時間就太長了，懶得測。。。

public class NQueens {

public static int num1(int n) {

if (n < 1) {

return 0;

}

int[] record = new int[n];

return process1(0, record, n);

}

public static int process1(int i, int[] record, int n) {

if (i == n) {

return 1;

}

int res = 0;

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

if (isValid(record, i, j)) {

record[i] = j;

res += process1(i + 1, record, n);

}

}

return res;

}

public static boolean isValid(int[] record, int i, int j) {

for (int k = 0; k < i; k++) {

if (j == record[k] || Math.abs(record[k] - j) == Math.abs(i - k)) {

return false;

}

}

return true;

}

public static int num2(int n) {

if (n < 1 || n > 32) {

return 0;

}

int upperLim = n == 32 ? -1 : (1 << n) - 1;

return process2(upperLim, 0, 0, 0);

}

public static int process2(int upperLim, int colLim, int leftDiaLim,

int rightDiaLim) {

if (colLim == upperLim) {

return 1;

}

int pos = 0;

int mostRightOne = 0;

pos = upperLim & (~(colLim | leftDiaLim | rightDiaLim));

int res = 0;

while (pos != 0) {

mostRightOne = pos & (~pos + 1);

pos = pos - mostRightOne;

res += process2(upperLim, colLim | mostRightOne,

(leftDiaLim | mostRightOne) << 1,

(rightDiaLim | mostRightOne) >>> 1);

}

return res;

}

public static void main(String[] args) {

int n = 32;

long start = System.currentTimeMillis();

System.out.println(num2(n));

long end = System.currentTimeMillis();

System.out.println("cost time: " + (end - start) + "ms");

start = System.currentTimeMillis();

System.out.println(num1(n));

end = System.currentTimeMillis();

System.out.println("cost time: " + (end - start) + "ms");

}

}

數(shù)據(jù)結(jié)構(gòu)

版權(quán)聲明：本文內(nèi)容由網(wǎng)絡(luò)用戶投稿，版權(quán)歸原作者所有，本站不擁有其著作權(quán)，亦不承擔(dān)相應(yīng)法律責(zé)任。如果您發(fā)現(xiàn)本站中有涉嫌抄襲或描述失實(shí)的內(nèi)容，請聯(lián)系我們jiasou666@gmail.com 處理，核實(shí)后本網(wǎng)站將在24小時內(nèi)刪除侵權(quán)內(nèi)容。

版權(quán)聲明：本文內(nèi)容由網(wǎng)絡(luò)用戶投稿，版權(quán)歸原作者所有，本站不擁有其著作權(quán)，亦不承擔(dān)相應(yīng)法律責(zé)任。如果您發(fā)現(xiàn)本站中有涉嫌抄襲或描述失實(shí)的內(nèi)容，請聯(lián)系我們jiasou666@gmail.com 處理，核實(shí)后本網(wǎng)站將在24小時內(nèi)刪除侵權(quán)內(nèi)容。