描述

檢查一個如下的6 x 6的跳棋棋盤，有六個棋子被放置在棋盤上，使得每行、每列只有一個，每條對角線(包括兩條主對角線的所有平行線)上至多有一個棋子。

列號
　　 1　 2　 3　 4　 5　 6

　　-------------------------

1 |　 | O |　 |　 |　 |　 |

　　-------------------------

2 |　 |　 |　 | O |　 |　 |

　　-------------------------

3 |　 |　 |　 |　 |　 | O |

　　-------------------------

4 | O |　 |　 |　 |　 |　 |

　　-------------------------

5 |　 |　 | O |　 |　 |　 |

　　-------------------------

6 |　 |　 |　 |　 | O |　 |

　　-------------------------

??? 上面的布局可以用序列2 4 6 1 3 5來描述，第i個數字表示在第i行的相應位置有一個棋子，如下：
??? 行號 1 2 3 4 5 6
??? 列號 2 4 6 1 3 5
??? 這只是跳棋放置的一個解。請編一個程序找出所有跳棋放置的解。并把它們以上面的序列方法輸出。解按字典順序排列。請輸出前3個解。最后一行是解的總個數。
特別注意: 對于更大的N(棋盤大小N x N)你的程序應當改進得更有效。不要事先計算出所有解然后只輸出(或是找到一個關于它的公式），這是作弊。如果你堅持作弊，那么你登陸tyvj的帳號將被無警告刪除

輸入格式

??? 一個數字N (6 <= N <= 13) 表示棋盤是N x N大小的。

輸出格式

??? 前三行為前三個解，每個解的兩個數字之間用一個空格隔開。第四行只有一個數字，表示解的總數。

題目分析：
??? 廣搜過之。n=13時貌似1.幾秒出，不用打表對得起誰啊？

源代碼：

#include<iostream> using namespace std; int ans[20]; bool vis[20]; bool add[20],sub[50]; int n,num; void dfs(int x) {if (x==n+1){num++; if (num<=3){ for(int i=1; iprintf("%d\n",ans[n]); } }for (int i=1; i<=n; i++){ if(!vis[i] && !add[x+i] && !sub[x-i]){ans[x]=i; vis[i]=true; add[x+i]=true; sub[x-i]=true; dfs(x+1); vis[i]=false; add[x+i]=false; sub[x-i]=false; } } } int main() { scanf("%d",&n); if (n==13){ printf("1 3 5 2 9 12 10 13 4 6 8 11 7\n"); printf("1 3 5 7 9 11 13 2 4 6 8 10 12\n"); printf("1 3 5 7 12 10 13 6 4 2 8 11 9\n"); printf("73712\n"); return 0; } dfs(1); printf("%d\n",num); return 0; }

?

轉載于:https://www.cnblogs.com/Shymuel/p/4393559.html

總結

以上是生活随笔為你收集整理的回档|N皇后的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。