【算法导论】八皇后问题的算法实现(C、MATLAB、Python版)

        八皇后问题是一道经典的回溯问题。问题描述如下:皇后可以在横、竖、斜线上不限步数地吃掉其他棋子。如何将8个皇后放在棋盘上(有8*8个方格),使它们谁也不能被吃掉?
        看到这个问题,最容易想到的就是遍历穷举法,不过仔细一想,思路虽然非常清晰,但是需要遍历次数太多,时间复杂度很高。那么,我们应该怎么办呢?下面给出算法思路:
        算法思想:首先尝试在第一行放置第一个皇后,然后在第二行放置第二个使之与前面的皇后不构成威胁,依此类推。如果发现不能放置下一个皇后,就回溯到上一步,试着将皇后放在其他的位置。最后,或者尝试完所有的可能或者找到解决方案。
        这种算法思想与中国的一句古话“不撞南墙不回头”类似:一路向前走,直到走到死胡同,然后往回走,回到上一个岔路口,重新选择一个方向,继续向前走,直到到达目的地。
        下面给出了该算法的具体实现,用C、MATLAB、PYTHON分别进行了实现,由于程序给出了比较详细的注释,因此就不对具体程序解释说明了。

C语言实现:

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

#define N 8//棋盘大小

int matrix[N][N];//存储皇后的位置,其实也可以用一维数组表示

void PrintQueen();//打印棋盘
void PlaceQueen(int row);//放置皇后
int Conflict(int row,int col);//检查当前皇后是否与之前的冲突

int main()
{
    PlaceQueen(0);
    return 0;
}

void PrintQueen()
{
    static int solutionNum=0;//看总共有多少种情况
    solutionNum+=1;
    int row,col;
    printf("第%d种方法:\n",solutionNum);
    for(row=0;row<N;row+=1)
    {
        for(col=0;col<N;col+=1)
        {
            if(matrix[row][col])
            {
                printf("* ");
            }
            else
            {
                printf("- ");
            }
        }
        printf("\n");
    }
    printf("\n");
}

int Conflict(int row,int col)
{
	for (int m = 0; m <row ; m++) 
	{  
        for (int n = 0; n <N; n++)
		{   
            if (matrix[m][n] == 1) //  每一行只有一个皇后  
			{  
                if ( n == col || abs(row - m) == abs(col - n) )   // 检查是否与之前的皇后冲突
                    return false;  
            }  
        }  
    }  
    return true;
}

void PlaceQueen(int row)
{
	if(row>=N)//已经放置了N个皇后
	{
		PrintQueen();
	}
	else
	{
		for(int col=0;col<N;col++)
		{
			matrix[row][col]=1;
			if(row==0||Conflict(row,col))
					PlaceQueen(row+1);//递归调用		
			matrix[row][col]=0;		
		}
		
	}
	
}

MATLAB实现

脚本文件Queen.m

 clear all
clc
 
global solutionNum;
solutionNum=0;%全局变量记录方法数
N=8;%皇后个数
matrix=zeros(N);%存储皇后位置信息
 
PlaceQueen(1,matrix,N)%调用放置方法


函数文件PlaceQueen.m

function PlaceQueen(row,matrix,N)%回溯法放置皇后
 
    if row>N
        PrintQueen(N,matrix);%打印棋盘
    else
        for col=1:N
            matrix(row,col)=1;
            if row==1||Conflict(row,col,N,matrix)%检测是否冲突
                PlaceQueen(row+1,matrix,N);
            end
            matrix(row,col)=0;
        end
    end
    
    %子函数:检测冲突
    function result=Conflict(row,col,N,matrix)%检测是否冲突
 
    result=1;
    for i=1:row-1
        for j=1:N
            if matrix(i,j)==1
                if ((j==col)||(abs(row-i)==abs(col-j)))%是否产生冲突:在同一直线,斜线上
                    result=0;
                    break;
                end
            end
        end
        if result==0
            break;
        end
    end
     
    %子函数:打印棋盘信息
function PrintQueen(N,matrix)
 
    global solutionNum; %定义全局变量,来累积方法数
    solutionNum=solutionNum+1;
    
    disp(['第',num2str(solutionNum),'种方法:'])
 
disp(matrix)

PYTHON实现:

def conflict(state,nextX):#冲突检测函数
    nextY=len(state)
    for i in range(nextY):
        if abs(state[i]-nextX) in (0,nextY-i):#检测是否在同一直线、斜线
            return True
    return False

def queens(num=8,state=()): #放置皇后,采用元组state来存储皇后的位置
    for pos in range(num):
        if not conflict(state,pos):
            if len(state)==num-1:
                yield (pos)
            else:
                for result in queens(num,state+(pos)):
                    yield (pos,)+result



for solution in queens(8):
    print (solution)
    
print('总共的方法数为:',len(list(queens(8))))

运行结果分别如下:

1、C语言的运行结果:
【算法导论】八皇后问题的算法实现(C、MATLAB、Python版)

2、MATLAB语言的运行结果:
【算法导论】八皇后问题的算法实现(C、MATLAB、Python版)

3、PYTHON语言的运行结果:
 【算法导论】八皇后问题的算法实现(C、MATLAB、Python版)

扩展:

上面的程序中,改变N的值就可以解决N皇后的问题了,但还可以用分治法来解决N皇后的问题,具体参见文献《N皇后问题解的构造和等价性分析》。下面的Matlab程序给出了一个简单的算法过程:
4皇后的一种放置方式:
     0     0     1     0
     1     0     0     0
     0     0     0     1
     0     1     0     0
根据4皇后的放置方式可以推导出16皇后的一种放置方式:
     0     0     0     0     0     0     0     0     0     0     1     0     0     0     0     0
     0     0     0     0     0     0     0     0     1     0     0     0     0     0     0     0
     0     0     0     0     0     0     0     0     0     0     0     1     0     0     0     0
     0     0     0     0     0     0     0     0     0     1     0     0     0     0     0     0
     0     0     1     0     0     0     0     0     0     0     0     0     0     0     0     0
     1     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0
     0     0     0     1     0     0     0     0     0     0     0     0     0     0     0     0
     0     1     0     0     0     0     0     0     0     0     0     0     0     0     0     0
     0     0     0     0     0     0     0     0     0     0     0     0     0     0     1     0
     0     0     0     0     0     0     0     0     0     0     0     0     1     0     0     0
     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     1
     0     0     0     0     0     0     0     0     0     0     0     0     0     1     0     0
     0     0     0     0     0     0     1     0     0     0     0     0     0     0     0     0
     0     0     0     0     1     0     0     0     0     0     0     0     0     0     0     0
     0     0     0     0     0     0     0     1     0     0     0     0     0     0     0     0
     0     0     0     0     0     1     0     0     0     0     0     0     0     0     0     0
依次类推,可以得到4的幂次皇后的一种放置方式,不过值得注意的是2、3、8、9、14、15、26、27、38、39这10个N值不能采用这种分治法。
由4皇后直接推出16皇后的Matlab实现如下:
clear all
clc
 
a4=[  0     0     1     0
     1     0     0     0
     0     0     0     1
     0     1     0     0]
 [asize bsize]=size(a4);
 
 a16=zeros(asize^2,bsize^2);
 [rowIndex,colIndex]=find(a4);
 
 for i=1:length(rowIndex)
     a16((1+asize*(rowIndex(i)-1)):asize*rowIndex(i),(1+asize*(colIndex(i)-1)):asize*colIndex(i))=a4;
 end
 a16


运行结果如下:

【算法导论】八皇后问题的算法实现(C、MATLAB、Python版)


原文:http://blog.csdn.net/tengweitw/article/details/44648249
作者:nineheadedbird










上一篇:算法研究之开灯问题


下一篇:[算法题] 安排会议室——贪心算法的应用