N-皇後問題

國際象棋中皇後可攻擊其所在行、列以及對角線上的棋子。N-皇後問題是要在N行N列的棋盤上放置N個皇後，使得皇後必吃之間不受攻擊，即任意兩個皇後不在同一行、同一列和系統的對角線。

為解決這個問題，考慮采用回溯法：第i個皇後放在第i行，然後從第一個皇後開始，對每個皇後，從其對應行(第i個皇後對應第i行)的第一列開始嘗試放置，若可以放置，則确定該位置并考慮下一個皇後；若與之前的皇後沖突，則考慮下一列；若超出最後一列，則重新确定上一個皇後的位置。重複該過程，直到找到所有的放置方案。

下面是算法的C++代碼實作。

常量和變量說明

pos: 一維數組，pos[i]表示第i個皇後放置在第i行的具體位置

count: 統計放置方案數

N: 皇後數

C++代碼：

#include "stdafx.h"

#include <iostream>

int isPlace(int pos[], int k);

int main() {

const int N = 4;

int i, j, count = 1;

int pos[N + 1];

//初始化位置

for (i = 1; i <= N; i++) {

pos[i] = 0;

}

j = 1;

while (j >= 1) {

pos[j] = pos[j] + 1;

//嘗試擺放第i個皇後

while (pos[j] <= N && isPlace(pos, j) == 0) {

//得到一個擺放方案

if (pos[j] <= N && j == N) {

printf("方案%d:", count++);

printf("%d-", pos[i]);

printf("\n");

//考慮下一個皇後

if (pos[j] <= N && j < N) {

j = j + 1;

else {//傳回考慮上一個皇後

pos[j] = 0;

j = j - 1;

system("pause");

return 1;

int isPlace(int pos[], int k) {

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

if (pos[i] == pos[k] || fabs(i - k) == fabs(pos[i] - pos[k])) {

return 0;