最近正在學習回溯法，遇到的第一個問題就是n皇后問題，問題如下：
要求在一個n×n的棋盤上放置n個皇后，使得任意兩個皇后不在同一行或同一列或同一斜線上，
直接上代碼：
#include<iostream>
#include<math.h>
using namespace std;
void NQueen(int, int, int*);
int main()
{
int x[4] = { -1, -1, -1, -1 }; //4 * 4的棋盤測驗
NQueen(0, 4, x);
return 0;
}
bool Place(int k, int i, int* x) //用來判斷皇后是否在同一列或者同一斜線，k表示當前行號，i記錄當前的列號，x記錄了當前棋盤資訊
{
for (int j = 0; j < k; j++)
{
if ((x[j] == i) || abs(x[j] - i) == abs(j - k))
return false;
}
return true;
}
void NQueen(int k, int n, int* x)
{
for (int i = 0; i < n; i++) //遍歷當前遞回到行的所有列號
{
if(Place(k, i, x)) //判斷當前位置是否可行
{
x[k] = i;
if (k == n - 1) //如果到了最后一行，說明是一個可行解，輸出
{
for (int j = 0; j < n; j++)
{
cout << x[j] << " ";
}
cout << endl;
}
else //深度優先進入下一層遞回
{
NQueen(k + 1, n, x);
}
}
}
return;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/467895.html
標籤：C++