天下

记录修行的印记

回溯算法(2):八皇后问题(非递归)

#include "stdafx.h"
using namespace std;

const  int n = 9;
static int matrix[n];

bool place(int row,int col)
{
    
for (int prev = 1; prev < row; prev++)
        
if (matrix[prev] == col || labs(col-matrix[prev]) == labs(row-prev)) return false;
    
return true;
}

void display()  //打印每个皇后的列的位置
{
    
int i;
    cout
<<"[";
    
for (i = 1; i <=7; i++)
        cout
<<matrix[i]<<",";
    cout
<<matrix[i]<<"]"<<endl;
}

void queen(int row)
{
    
int count = 0;
    
bool ret = false;
    
int  col = 0;
    memset(matrix,
0,sizeof(matrix));
    
while (row <= 8)
    {
        ret 
= false;
        
for (col = matrix[row] + 1; col <= 8; col++)
        {
            ret 
= place(row,col);
            
if (ret)     //如果(x,y)位置能否摆放皇后
            {
                matrix[row] 
= col;  //将第i行的皇后摆放在第j列
                break;      //跳出这一层循环,开始摆放下一行的皇后
            }
        }
        
if (!ret)  //如果循环完这一行,每个位置都冲突
        {
            matrix[row] 
= 0//将这一行的皇后位置重置为0;
            row--;       //返回到上一行
            if(row==0)break//如果已经返回到了第0行,说明所有情况都找完了
        }
        
else
        {
            
if (row == 8)  //如果找到了第8行,说明有满足条件的结果
            {
                display();  
//输出结果
                count++;
            }
            
else row++;
        }
    }
    cout
<<count<<endl;
}
int main()
{
    queen(
1);
    system(
"pause");
    
return 0;
}   

posted on 2013-03-20 18:09 天下 阅读(509) 评论(0)  编辑 收藏 引用 所属分类: 算法


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


<2012年10月>
30123456
78910111213
14151617181920
21222324252627
28293031123
45678910

导航

统计

常用链接

留言簿(4)

随笔分类(378)

随笔档案(329)

链接

最新随笔

搜索

最新评论