★ 第三十四讲 八皇后问题 | 【递归版】 ★
本帖最后由 不二如是 于 2017-10-23 14:26 编辑http://xxx.fishc.com/forum/201709/05/221714xccynsdzifbskndw.jpg
{:10_254:}{:10_254:} 索引帖 {:10_254:}{:10_254:}
用一节课的时间，提高生活幸福感
------小甲鱼
欢乐与傻笑并存
智慧与邪恶同在
笔记内涵------
八皇后问题
八皇后问题，是一个古老而著名的问题。
是回溯算法的典型例题，这节课小甲鱼先用递归算法来解。
该问题是十九世纪著名的数学家高斯1850年提出：
在8X8格的国际象棋上摆放八个皇后，使其不能互相攻击。
即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。
高斯先生当年由于没有学好计算机编程，没日没夜地计算呀。。。
得出结论是：
76种硬生生把自己给“搞死”了！
对了，当年还没有计算机......
正确的结果应该是：
92种。
本节课属于大家一起边敲代码边总结思路，所以要仔细看视频！
总结
第1次考虑把皇后放在第1行的某个位置。
第2次放的时候就不用去放在第一行了，因为这样放皇后间是可以互相攻击的。
第2次我就考虑把皇后放在第2行的某个位置，第3次我考虑把皇后放在第3行的某个位置， 这样依次去递归。
每计算1行，递归一次，每次递归里面考虑8列， 即对每一行皇后有8个可能的位置可以放。
找到一个与前面行的皇后都不会互相攻击的位置， 然后再递归进入下一行。
找到一组可行解即可输出，然后程序回溯去找下一组可靠解。
我们用一个一维数组来表示相应行对应的列，比如：
c=j//表示， 第i行的皇后放在第j列
如果当前行是r，皇后放在哪一列呢？
答案是：
**** Hidden Message *****
一共有8列，所以我们要让c依次取第0列，第1列，第2列……
一直到第7列， 每取一次我们就去考虑，皇后放的位置会不会和前面已经放了的皇后有冲突。
怎样是有冲突呢？
答案是：
同行，同列，对角线。
由于已经不会同行了，所以不用考虑这一点。
同列：
c==c;
同对角线有两种可能，即主对角线方向和副对角线方向。
主对角线方向满足，行之差等于列之差：
r-j==c-c;
副对角线方向满足， 行之差等于列之差的相反数：
r-j==c-c；
只有满足了当前皇后和前面所有的皇后都不会互相攻击的时候，才能进入下一级递归。
代码实现：
#include <stdio.h>
int count = 0;
int notDanger( int row, int j, int (*chess) )
{
int i, k, flag1=0, flag2=0, flag3=0, flag4=0, flag5=0;
// 判断列方向
for( i=0; i < 8; i++ )
{
if( *(*(chess+i)+j) != 0 )
{
flag1 = 1;
break;
}
}
// 判断左上方
for( i=row, k=j; i>=0 && k>=0; i--, k-- )
{
if( *(*(chess+i)+k) != 0 )
{
flag2 = 1;
break;
}
}
// 判断右下方
for( i=row, k=j; i<8 && k<8; i++, k++ )
{
if( *(*(chess+i)+k) != 0 )
{
flag3 = 1;
break;
}
}
// 判断右上方
for( i=row, k=j; i>=0 && k<8; i--, k++ )
{
if( *(*(chess+i)+k) != 0 )
{
flag4 = 1;
break;
}
}
// 判断左下方
for( i=row, k=j; i<8 && k>=0; i++, k-- )
{
if( *(*(chess+i)+k) != 0 )
{
flag5 = 1;
break;
}
}
if( flag1 || flag2 || flag3 || flag4 || flag5 )
{
return 0;
}
else
{
return 1;
}
}
// 参数row: 表示起始行
// 参数n: 表示列数
// 参数(*chess): 表示指向棋盘每一行的指针
void EightQueen( int row, int n, int (*chess) )
{
int chess2, i, j;
for( i=0; i < 8; i++ )
{
for( j=0; j < 8; j++ )
{
chess2 = chess;
}
}
if( 8 == row )
{
printf("第 %d 种\n", count+1);
for( i=0; i < 8; i++ )
{
for( j=0; j < 8; j++ )
{
printf("%d ", *(*(chess2+i)+j));
}
printf("\n");
}
printf("\n");
count++;
}
else
{
for( j=0; j < n; j++ )
{
if( notDanger( row, j, chess ) ) // 判断是否危险
{
for( i=0; i < 8; i++ )
{
*(*(chess2+row)+i) = 0;
}
*(*(chess2+row)+j) = 1;
EightQueen( row+1, n, chess2 );
}
}
}
}
int main()
{
int chess, i, j;
for( i=0; i < 8; i++ )
{
for( j=0; j < 8; j++ )
{
chess = 0;
}
}
EightQueen( 0, 8, chess );
printf("总共有 %d 种解决方法!\n\n", count);
return 0;
}
这位鱼油，如果喜欢本系列笔记，请订阅 专辑☞（传送门）（不喜欢更要订阅{:10_278:} ） 我不知道{:10_249:} {:5_92:} c很好，我选择pythondef lie(x):
x.sort()
if x == :
return True
else:
return False
def duijiao(x):
for i in range(8):
for j in range(i+1,8):
if abs(x-x) == abs(x-x):
return False
else:
return True
time = 0
for a1 in range(8):
for a2 in range(8):
for a3 in range(8):
for a4 in range(8):
for a5 in range(8):
for a6 in range(8):
for a7 in range(8):
for a8 in range(8):
list1 =
list2 = list(enumerate(list1))
if lie(list1) and duijiao(list2):
qipan = [ for j in range(8)]
for each in list2:
qipan]]=1
for each in qipan:
print(each)
print('\n')
time += 1
print('共有解 %d 个' % time) 我觉得八皇后这儿应该改为这个。 递归完成或者下一行没找成功，然后此位置为0，继续寻找此行符合条件的下一个 这个一个数组也是可以充分够的。 求助大神
蓝色王魂 发表于 2018-1-14 09:24
c很好，我选择python
看不懂啊
蓝色王魂 发表于 2018-1-14 09:24
c很好，我选择python
..试了下运行..显示“list” is not callable
那句 list2= list（enumerate（list1））
是不是有问题? 来看看，学习学习 whalesea 发表于 2018-1-30 19:39
..试了下运行..显示“list” is not callable
那句 list2= list（enumerate（list1））
是不是有问题 ...
我自己运行是没有问题的啊，你看一下是不是代码复制的时候出了什么问题 本帖最后由 圣狄雅哥 于 2018-2-3 21:41 编辑
1093331524 发表于 2018-1-17 10:49
递归完成或者下一行没找成功，然后此位置为0，继续寻找此行符合条件的下一个
我试了试不行。 圣狄雅哥 发表于 2018-2-3 21:34
我试了试不行。
但是按理说chess2每个元素都被初始化为0了，就算后面不重新赋值为0也不影响啊
for( j=0; j < n; j++ )
{
if( notDanger( row, j, chess ) ) // 判断是否危险
{
for( i=0; i < 8; i++ )
{
*(*(chess2+row)+i) = 0;
}
*(*(chess2+row)+j) = 1;
EightQueen( row+1, n, chess2 );
}
}
//这段循环与递归不是太能看懂 1 mark下 朕想知道 谢谢 本帖最后由 ZMichael 于 2018-9-14 22:02 编辑
这怎么像是回溯方法呢？递归和回溯区别在哪？