八皇后问题与回溯算法

7-11 2,615 views

八皇后问题是在8*8的棋盘上放置8枚皇后，使得棋盘中每个纵向、横向、左上至右下斜向、右上至左下斜向均只有一枚皇后。八皇后的一个可行解如图所示：

思路

对于八皇后的求解可采用回溯算法，从上至下依次在每一行放置皇后，进行搜索，若在某一行的任意一列放置皇后均不能满足要求，则不再向下搜索，而进行回溯，回溯至有其他列可放置皇后的一行，再向下搜索，直到搜索至最后一行，找到可行解，输出。
可以使用递归函数实现上述回溯算法，递归函数用于求解在某一行放置皇后，具体代码如下所示。

代码

#include <stdlib.h>
#include <stdio.h> 

int m[8][8] = {0};//表示棋盘，初始为0，表示未放置皇后
int num = 0;//解数目 

//对于棋盘前row-1行已放置好皇后
//检查在第row行、第column列放置一枚皇后是否可行
bool check(int row,int column)
{
    if(row==1) return true;
    int i,j;
    //纵向只能有一枚皇后
    for(i=0;i<=row-2;i++) 
    {          
        if(m[i][column-1]==1) return false;      
    }      
    //左上至右下只能有一枚皇后      
    i = row-2;      
    j = i-(row-column);      
    while(i>=0&&j>=0)
    {
        if(m[i][j]==1) return false;
        i--;
        j--;
    }
    //右上至左下只能有一枚皇后
    i = row-2;
    j = row+column-i-2;
    while(i>=0&&j<=7)
    {
        if(m[i][j]==1) return false;
        i--;
        j++;
    }
    return true;
} 

//当已放置8枚皇后，为可行解时，输出棋盘
void output()
{
    int i,j;
    num++;
    printf("answer %d:\n",num);
    for(i=0;i<8;i++)
    {
        for(j=0;j<8;j++) printf("%d ",m[i][j]);
        printf("\n");
    }
} 

//采用递归函数实现八皇后回溯算法
//该函数求解当棋盘前row-1行已放置好皇后，在第row行放置皇后
void solve(int row)
{
    int j;
    //考虑在第row行的各列放置皇后
    for (j=0;j<8;j++)
    {
        //在其中一列放置皇后
        m[row-1][j] = 1;
        //检查在该列放置皇后是否可行
        if (check(row,j+1)==true)
        {
            //若该列可放置皇后，且该列为最后一列，则找到一可行解，输出
            if(row==8) output();
            //若该列可放置皇后，则向下一行，继续搜索、求解
            else solve(row+1);
        }
        //取出该列的皇后，进行回溯，在其他列放置皇后
        m[row-1][j] = 0;
    }
} 

//主函数
int main()
{
    //求解八皇后问题
    solve(1);
    return 0;
}

#include <stdlib.h>

#include <stdio.h>

int m[8][8] = {0};//表示棋盘，初始为0，表示未放置皇后

int num = 0;//解数目

//对于棋盘前row-1行已放置好皇后

//检查在第row行、第column列放置一枚皇后是否可行

bool check(int row,int column)

{

if(row==1) return true;

int i,j;

//纵向只能有一枚皇后

for(i=0;i<=row-2;i++)

{

if(m[i][column-1]==1) return false;

}

//左上至右下只能有一枚皇后

i = row-2;

j = i-(row-column);

while(i>=0&&j>=0)

{

if(m[i][j]==1) return false;

i--;

j--;

}

//右上至左下只能有一枚皇后

i = row-2;

j = row+column-i-2;

while(i>=0&&j<=7)

{

if(m[i][j]==1) return false;

i--;

j++;

}

return true;

}

//当已放置8枚皇后，为可行解时，输出棋盘

void output()

{

int i,j;

num++;

printf("answer %d:\n",num);

for(i=0;i<8;i++)

{

for(j=0;j<8;j++) printf("%d ",m[i][j]);

printf("\n");

}

//采用递归函数实现八皇后回溯算法

//该函数求解当棋盘前row-1行已放置好皇后，在第row行放置皇后

void solve(int row)

{

int j;

//考虑在第row行的各列放置皇后

for (j=0;j<8;j++)

{

//在其中一列放置皇后

m[row-1][j] = 1;

//检查在该列放置皇后是否可行

if (check(row,j+1)==true)

{

//若该列可放置皇后，且该列为最后一列，则找到一可行解，输出

if(row==8) output();

//若该列可放置皇后，则向下一行，继续搜索、求解

else solve(row+1);

}

//取出该列的皇后，进行回溯，在其他列放置皇后

m[row-1][j] = 0;

}

//主函数

int main()

{

//求解八皇后问题

solve(1);

return 0;

}

版权属于: 我爱我家

原文地址: http://magicwt.com/2012/07/11/%e5%85%ab%e7%9a%87%e5%90%8e%e9%97%ae%e9%a2%98%e4%b8%8e%e5%9b%9e%e6%ba%af%e7%ae%97%e6%b3%95/

转载时必须以链接形式注明原始出处及本声明。