编城浪子的博客
游戏开发、图形引擎
八皇后棋局:即在一个8×8的方格棋局中放置8个棋子,其中每两个棋子皆不同行、不同列、不同斜线,求出任意一种放置方法,并打印出来。比如,如下棋局即满足以上条件:
0 0 0 1 0 0 0 0
0 0 0 0 0 1 0 0
1 0 0 0 0 0 0 0
0 0 0 0 1 0 0 0
0 1 0 0 0 0 0 0
0 0 0 0 0 0 0 1
0 0 1 0 0 0 0 0
0 0 0 0 0 0 1 0
以上矩阵中,1代表方格中有棋子,0代表方格中无棋子,可以看出,任意两棋子不同行,不同列,且不同斜线。
求出八皇后棋局有很多种,这里介绍本人自创的一种--随机试探法。故名思义,试探性地在某一行的某一位置放置一个棋子(以下简称放子),判断该棋子是否打破棋局规则,如果未打破,则继续在下一行放子;如果打破规则,则重复试探其他位置。为了方便程序实现,也为了更好理解,不妨依次对第1、2、...、8行,如此顺序,试探性的放子。
可以预测,很可能的一种情况是:还未对第八行进行放子时(比如,程序才进行到第5行),无论对中间的某一行(比如第六行)的任何一个位置放子,都不能满足棋局规则,这种情况称为死局。程序运行结果表明这种预测是合理的,一般要进行十几遍从头试探才能成功获得八皇后棋局。
以下给出整个程序:
#include <iostream>
#include <tchar.h>
// eight_queen.cpp : 定义控制台应用程序的入口点。
//
#include "time.h"

/** 在新行中第pos个位置打印一个*号
*/
void print_star(int pos)
{
char str[] = "|                 |\n";
str[pos*2] = '*';
printf(str);
}

/** get a random num between 0,1,2,...7
*/
int get_rand_num()
{
return rand()%8;
}

/** 打印8×8矩阵
*/
void print_flag(bool flag[8][8])
{
//打印星号矩阵
for(int i=0;i<8;i++){
for(int j=0;j<8;j++){
if(flag[i][j] == true){
print_star(j+1);
break;
}
}
}
//打印0-1矩阵
for(int i=0;i<8;i++){
for(int j=0;j<8;j++){
printf(" %d", flag[i][j]==1?0:1);
}
printf("\n");
}
}

/** result = (i<=num<=j)
*/
bool isBetween(int num, int i, int j)
{
return (num>=i)&&(num<=j);
}

/** test whether flag[i][j] can be true
对于flag[8][8]矩阵,判断可否在第row行,第col列放入一个棋子
*/
bool test_value(bool flag[8][8], int row, int col)
{
//判断横
for(int i=0;i<8;i++){
if(true == flag[i][col]){
return false;
}
}
//判断竖
for(int j=0;j<8;j++){
if(true == flag[row][j]){
return false;
}
}
//判断斜方向
for(int i=1;i<8;i++){
if(isBetween(row-i, 0, 7)&&isBetween(col-i, 0, 7)){
if(true == flag[row-i][col-i]){
return false;
}
}
else{
break;
}
}
//判断斜方向
for(int i=1;i<8;i++){
if(isBetween(row+i, 0, 7)&&isBetween(col+i, 0, 7)){
if(true == flag[row+i][col+i]){
return false;
}
}
else{
break;
}
}
//判断斜方向
for(int i=1;i<8;i++){
if(isBetween(row-i, 0, 7)&&isBetween(col+i, 0, 7)){
if(true == flag[row-i][col+i]){
return false;
}
}
else{
break;
}
}
//判断斜方向
for(int i=1;i<8;i++){
if(isBetween(row+i, 0, 7)&&isBetween(col-i, 0, 7)){
if(true == flag[row+i][col-i]){
return false;
}
}
else{
break;
}
}
flag[row][col] = true;
return true;
}


#define RAND_NUM 20
//递归函数
bool recursive(bool flag[8][8], int i)
{
if(i==8)
return true;
int num = 0;
while(num<RAND_NUM){
int j = get_rand_num();
if(test_value(flag, i, j)){
break;
}
num++;
}
if(num<RAND_NUM)
return recursive(flag, i+1);
else
return false;
}
/** get a queen fig
*/
bool get_queen_fig(bool flag[8][8])
{
//棋局初始化
for(int i=0;i<8;i++){
for(int j=0;j<8;j++){
flag[i][j] = false;
}
}
return recursive(flag, 0);
}

#define LOOP_NUM 30
int _tmain(int argc, _TCHAR* argv[])
{
srand(time(0));
for(int i=1;i<=8;i++)
print_star(i);

bool flag[8][8];
int loops = 0;
do
{
loops++;
if(loops>LOOP_NUM)
{
break;
}
printf("has trying get a queen figure for %d times\n", loops);
}
while(false == get_queen_fig(flag));
if(loops>LOOP_NUM)
printf("failed to get a queen figure!\n");
else{
printf("succeed to get a queen figure!\n");
print_flag(flag);
}


return 0;
}

posted on 2008-10-21 22:49 zengfancy 阅读(2672) 评论(8)  编辑 收藏 引用
Comments
  • # re: 八皇后问题的一种解法-随机试探法
    thermos
    Posted @ 2008-10-21 23:35
    拉斯维加斯算法 嗯   回复  更多评论   
  • # re: 八皇后问题的一种解法-随机试探法[未登录]
    Albert
    Posted @ 2008-10-22 10:31
    你这叫随机试探?我怎么没感觉出来,跟经典的解放有一点不同么?  回复  更多评论   
  • # re: 八皇后问题的一种解法-随机试探法
    zengfancy
    Posted @ 2008-10-22 16:21
    什么是拉斯维加斯算法?我不知道。或许它和我想到一处去了。@thermos
      回复  更多评论   
  • # re: 八皇后问题的一种解法-随机试探法
    zengfancy
    Posted @ 2008-10-22 16:23
    我理解的随机试探法就是填棋的时候位置是随机生成的。@Albert
      回复  更多评论   
  • # re: 八皇后问题的一种解法-随机试探法
    金山毒霸2008
    Posted @ 2008-10-22 21:36
    你的这个解法怎么这么长,我记得上学时设计的很短的。  回复  更多评论   
  • # re: 八皇后问题的一种解法-随机试探法
    merlinfang
    Posted @ 2008-10-28 19:12
    求出任意一种算法,还是使用贪婪法快啊  回复  更多评论   
  • # re: 八皇后问题的一种解法-随机试探法
    zengfancy
    Posted @ 2008-10-31 20:54
    对于贪婪算法,我不是很懂。。  回复  更多评论   
  • # re: 八皇后问题的一种解法-随机试探法
    merlinfang
    Posted @ 2008-11-01 11:48
    贪婪法比较简单,就是一种策略
    我所了解的如下:
    象一般的求解是遍历(你这里是随机遍历), 但贪婪法在遍历之前先进行排序,即对可遍历的子节点进行排序,排序的规则是谁的后续空格少,谁就先遍历.

    我以前测试的速度要快N倍,特别到几十皇后的时候,遍历法根本跑不动

      回复  更多评论   

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理