求教C語言回溯法寫出八皇后問題的92種解

2021-07-30 12:51:40 字數 1344 閱讀 9196

1樓:

(1)全排列

將自然數1~n進行排列,共形成n!中排列方式,叫做全排列。

例如3的全排列是:1/2/3、1/3/2、2/1/3、2/3/1、3/1/2、3/2/1,共3!=6種。

(2)8皇后(或者n皇后)

保證8個皇后不能互相攻擊,即保證每一橫行、每一豎行、每一斜行最多一個皇后。

我們撇開第三個條件,如果每一橫行、每一豎行都只有一個皇后。

將8*8棋盤標上座標。我們討論其中的一種解法:

- - - - - - - q

- - - q - - - -

q - - - - - - -

- - q - - - - -

- - - - - q - -

- q - - - - - -

- - - - - - q -

- - - - q - - -

如果用座標表示就是:(1,8) (2,4) (3,1) (4,3) (5,6) (6,2) (7,7) (8,5)

將橫座標按次序排列,縱座標就是8/4/1/3/6/2/7/5。這就是1~8的一個全排列。

我們將1~8的全排列存入輸入a中(a[0]~a[7]),然後8個皇后的座標就是(i+1,a[i]),其中i為0~7。

這樣就能保證任意兩個不會同一行、同一列了。

置於斜行,你知道的,兩個點之間連線的斜率絕對值為1或者-1即為同一斜行,充要條件是|x1-x2|=|y1-y2|(兩個點的座標為(x1,y1)(x2,y2))。我們在輸出的時候進行判斷,任意兩個點如果滿足上述等式,則判為失敗,不輸出。

下面附上**:新增必要的註釋,其中全排列的實現看看註釋應該可以看懂:

#include

#include

#include

#include

int printed;

//該函式用於畫圖,這裡為了節約空間則略去

//讀者只需要將draw(a,k);去掉註釋即可畫圖

void draw(int* a,int k)

{int i,j;

for(i=0;i

2樓:

#include

#include

#define max 8

int queen[max],sum=0;

void show()

printf(")\n");

++sum;

}int place(int n) //阻止max個皇后在同一列和同一對角線上

}return 1;

}void nqueens(int n)

else}}

}int main(void)

c語言的問題,第八題,求教求教,C語言問題,小白求教

您好,a 望採納,謝謝 include void main else if close open else if low open low close if hign open hign close else len sprintf print len,upper shadow printf pri...

求教c語言高手問題,求教C語言高手一個問題

是氣泡排序呀!按從短到長排序。include include void fun char s,int n 定義函式 main fun ss,5 printf s,s n ss 0 ss 4 輸出最短和最長的字串 先定義了一個字串陣列 char ss 相當於 ss 0 bcc ss 1 bbcc 然後...

C語言指標問題,求教大神C語言指標的問題搞不懂求大神指教

include include include include include static char chongpai char static int pare const void const void static int allocateintegerarr const char size ...