liyuxia713

[導(dǎo)入]二維數(shù)組求解八皇后問題

//8queen.cpp
//eight queens problem，總共有92個解.
//八皇后問題：在8*8的方格棋盤上安置8個棋子（皇后）
//要求：任何兩個棋子都不能在棋盤的同一行，同一列或同一對角線上。

#include <iostream>
using namespace std;

const int N = 8;
static int num = 0;

int a[N][N] = {0};

//輸出矩陣
void print(int a[][N],int row); //注意二維數(shù)組如何調(diào)用
//判斷步驟是否有效
bool is_valid(int i, int j);
//探索，遍歷
void traversal(int i);

int main()
{       
    traversal(0);
    cout << "There are " << num << " solutions for eight queens problems" <<endl;
    return 0;
}

//探索，遍歷(核心部分)
void traversal(int i)
{
    if(i >= 8)
    {
        print(a, N);       
    }
    for(int j = 0; j != N; ++j)
    {
        a[i][j] = 1;
        if(is_valid(i,j)) traversal(i+1);
        a[i][j] = 0;
    }
}

//判斷步驟是否有效
bool is_valid(int i, int j)
{
    bool b = true;
    for(int i1 = 0; i1 != i; ++i1)
        for(int j1 = 0; j1 != N; ++j1)
        {
            if(a[i1][j1] == 1)
                if((j1 == j) || ( abs(i1 - i) == abs(j1 - j)) ) b = false;               
        }
    return b;
}

//輸出矩陣
void print(int a[][N],int row)
{
    ++num;
    for(int i = 0; i != row; ++i)
    {
        for(int j = 0; j != N; ++j)
            cout << a[i][j] << " ";
        cout << endl;
    }

    cout << "--------------------" <<endl;
}
文章來源:http://liyuxia-life.spaces.live.com/Blog/cns!DA1B364675ACF35!272.entry

posted on 2009-04-10 11:12 幸運草 閱讀(2068) 評論(2)  編輯 收藏 引用 所屬分類: Algorithms