八皇后问题.ppt

八皇后问题
纪林志
演讲者:
问题的简介
思考探讨
解决流程
编码解决问题
八皇后
八皇后问题: 是一个古老而著名的问题,是回溯算法的典型例题。该问题是十九世纪著名的数学家高斯1850年提出:在8X8的国际象棋上摆放八个皇后,使其不能互相攻击,即任意两个皇后都不能处于同一行、同一列或同一斜线上,问有多少种摆法。
高斯认为有76种方案!!!
问题简介
1854年在柏林的象棋杂志上不同的作者发表了40种不同的解,后来有人用图论的方法解出92种结果。计算机发明后,有多种方法可以解决此问题。
思考讨论
你会吗???
思考讨论
so easy!!!
杨老师再也不用担心我的算法了
解决流程
编码来喽
#include <>
#define N 8 // 定义棋盘的格数, 通过改变,也可以是4皇后, 16皇后, 9皇后什么的.
int chess[N][N] = {0}; // 棋盘
int count = 0; // 有多少种放法
int canput(int row, int col) // 确定某一格能不能放
编码来喽
{
int i,j;
for(i = 0; i < N; i ++)
{
if(chess[i][col] == 1) //有同列的
{
return 0;
}
for(j = 0; j < N; j++)
{
if(chess[row][j]==1) //有同行的
{
return 0;
}
if(((i-row)==(j-col)||(i-row)==(col-j))&&chess[i][j]==1) // 对角线上有的
{
return 0;
}
}
}
return 1;
}
编码来喽
void print_chess() // 打印放置的方案
{
int i, j;
for(i = 0; i < N; i++)
{
for(j = 0; j < N; j++)
{
printf("%d ", chess[i][j]);
}
printf("\n");
}
printf("\n");
}
int put(int row) // 放置棋子, row是从哪一行开始, 通常是0
{
int j, s;
for(j = 0; j < N; j++) // 此一行的每一个格子都要试试能不能放
{
if(canput(row, j)) // 假如这格能放的话
{
chess[row][j] = 1; // 放置
if(row == N-1) // 已经到了最后一行, 那么肯定成功