N皇后問題自不必多說，這道題的先行條件是在放置的時候已經(jīng)指定了一個棋子的位置。

輸入第一行為N，第二行為指定棋子的坐標（x,y）；輸出方案總數(shù)以及按字典序升序的各種方案。

思路：
首先是回溯，其次對待指定棋子有三種方法：

枚舉所有情況，最后判斷

在枚舉到那一行的時候只讓棋子下在指定的那一列

初始化vis數(shù)組時進行標記，同時跳過枚舉x行和y列

第三種我沒寫出來，但很明顯比前兩種要快得多，第二種比第一種快了100多ms

代碼如下：
第一種，耗時327ms：

#include<cstdio> #include<algorithm> #include<string.h> using namespace std; int n, x, y, tot = 0; int vis[3][100], c[20]; int ans[1000000][20];void search(int cur) {if (cur == n) {if (c[x] != y) return;memcpy(ans[tot], c,sizeof(c));tot++;}else for (int i = 0; i < n; i++) {if (!vis[0][i] && !vis[1][cur + i] && !vis[2][cur - i + n]) {c[cur] = i;vis[0][i] = vis[1][cur + i] = vis[2][cur - i + n] = 1;search(cur + 1);vis[0][i] = vis[1][cur + i] = vis[2][cur - i + n] = 0;}} }int main() {scanf("%d", &n);scanf("%d%d", &x, &y);x--; y--;search(0);printf("%d\n", tot);for (int i = 0; i < tot; i++) {for(int j = 0; j < n; j++) {printf("%d ", ans[i][j] + 1);}printf("\n");}return 0; }

第二種，耗時221ms

#include<cstdio> #include<algorithm> #include<string.h> using namespace std; int n, x, y, tot = 0; int vis[3][100], c[20]; int ans[1000000][20];void search(int cur) {//if (cur == x) { c[cur] = y; search(cur + 1); return; }if (cur == n) {//if (c[x] != y) return;memcpy(ans[tot], c, sizeof(c));tot++;}else for (int i = 0; i < n; i++) {if (cur == x&&i != y)continue;if (!vis[0][i] && !vis[1][cur + i] && !vis[2][cur - i + n]) {c[cur] = i;vis[0][i] = vis[1][cur + i] = vis[2][cur - i + n] = 1;search(cur + 1);vis[0][i] = vis[1][cur + i] = vis[2][cur - i + n] = 0;}} }int main() {scanf("%d", &n);scanf("%d%d", &x, &y);x--; y--;search(0);printf("%d\n", tot);for (int i = 0; i < tot; i++) {for (int j = 0; j < n; j++) {printf("%d ", ans[i][j] + 1);}printf("\n");}return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/romaLzhih/p/9489818.html

總結(jié)

以上是生活随笔為你收集整理的回溯经典（指定位置N皇后问题）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。