Technorati 標(biāo)簽:
八皇后問題//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