#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;
}
}
}clear all clc global solutionNum; solutionNum=0;%全局变量记录方法数 N=8;%皇后个数 matrix=zeros(N);%存储皇后位置信息 PlaceQueen(1,matrix,N)%调用放置方法
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)
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))))
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
运行结果如下：
原文：http://blog.csdn.net/tengweitw/article/details/44648249
作者：nineheadedbird
【算法导论】八皇后问题的算法实现（C、MATLAB、Python版）
原文：http://blog.csdn.net/tengweitw/article/details/44648249
