回溯法之二---8皇后問題
八皇后問題是一個古老而著名的問題，是回溯算法的典型例題。該問題是十九世紀著名的數學家高斯1850年提出：在8X8格的國際象棋上擺放八個皇后，使其不能互相攻擊，即任意兩個皇后都不能處于同一行、同一列或同一斜線上.
問題分析:
第一步 定義問題的解空間
這個問題解空間就是8個皇后在棋盤中的位置.
第二步 定義解空間的結構
可以使用8*8的數組，但由于任意兩個皇后都不能在同行，我們可以用數組下標表示
行，數組的值來表示皇后放的列，故可以簡化為一個以維數組x[9]。
第三步 以深度優先的方式搜索解空間，并在搜索過程使用剪枝函數來剪枝
根據條件:x[i] == x[k]判斷處于同一列
abs(k-i) == abs(x[k]-x[i]判斷是否處于同一斜線
我們很容易寫出剪枝函數：
然后我們按照回溯框架一，很容易寫出8皇后的回溯代碼：
整個代碼：
問題分析:
第一步 定義問題的解空間
這個問題解空間就是8個皇后在棋盤中的位置.
第二步 定義解空間的結構
可以使用8*8的數組，但由于任意兩個皇后都不能在同行，我們可以用數組下標表示
行，數組的值來表示皇后放的列，故可以簡化為一個以維數組x[9]。
第三步 以深度優先的方式搜索解空間，并在搜索過程使用剪枝函數來剪枝
根據條件:x[i] == x[k]判斷處于同一列
abs(k-i) == abs(x[k]-x[i]判斷是否處于同一斜線
我們很容易寫出剪枝函數：
- bool canPlace( int k){
- for ( int i=1;i<k;i++){
- //判斷處于同一列或同一斜線
- if (x[i]==x[k]||abs(k-i)==abs(x[k]-x[i])) return false ;
- }
- return true ;
- }
然后我們按照回溯框架一，很容易寫出8皇后的回溯代碼：
- void queen( int i){
- if (i>8){
- print();
- return ;
- }
- for ( int j=1;j<=8;j++){
- x[i]=j; //記錄所放的列
- if (canPlace(i))queen(i+1);
- }
- }
整個代碼：
- #include<iostream>
- #include<cmath>
- using namespace std;
- int x[9];
- void print(){
- for ( int i=1;i<=8;i++)
- cout<<x[i]<< "" ;
- cout<<endl;
- }
- bool canPlace( int k){
- for ( int i=1;i<k;i++){
- //判斷處于同一列或同一斜線
- if (x[i]==x[k]||abs(k-i)==abs(x[k]-x[i]))
- return false ;
- }
- return true ;
- }
- void queen( int i){
- if (i>8){
- print();
- return ;
- }
- for ( int j=1;j<=8;j++){
- x[i]=j;
- if (canPlace(i))queen(i+1);
- }
- }
- int main(){
- queen(1);
- return 0;
- }
更多文章、技術交流、商務合作、聯系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號聯系： 360901061
您的支持是博主寫作最大的動力，如果您喜歡我的文章，感覺我的文章對您有幫助，請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點擊下面給點支持吧，站長非常感激您！手機微信長按不能支付解決辦法：請將微信支付二維碼保存到相冊，切換到微信，然后點擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對您有幫助就好】元
