Nini的python学习笔记

----csc1ass2 eight queens question

This week I finished the assignment 2 of CSC1001. The question 6 (eight queens problem) takes me plenty of time.

偏个题----一个愚蠢的故事：

最初！我居然没有看到对角线要不能重复！（可能是因为一到五题都蠢的一批，我自然以为第六题也很水。。。）（清醒一点，这是压轴题啊hhh）然后我想这不就一行一行打，一共八个位置，随机生成位置，占了位的重新生成一波就ok了嘛。。。然后我就开心地做完提交了。。后来有同学问我这道题，我才惊觉自己连diagonal都木有考虑。。。实在是too naive。。

import random

#随机产生0到7的整数计作Queen的位置

k = random.randint(0,7)

（注意：其中（0，7）并非左闭右开，7也是可以取到的）

慌忙爆肝---

当我意识到对角线的问题时，离ddl只有2天了。。。

我最初的想法是一行一行生成（这样就不用考虑same row的问题了）。

然后def两个判断no same row, diagonal的function

怎么判断不在对角线上呢？（这也是把我整蒙了好久的----

最简洁的做法是应用一下规律：

abs(column[row] - column[i]) == abs(row - i)

（反思：我做题的步骤有问题，应该先多观察、思考一下的）

但是我写完后运行的时候总是不能print完全，卡在一个循环里了。。。在同一列或同一对角线就不停重新生成位置。。于是开始我漫长的debug之旅。。。（可怕的是我那时还木有意识到为啥会这样，也就说没有想到在前几行位置确定的情况下还有可能有无解的情况。。

后来终于发现了。。Google了一下说要“回溯”，还涉及到了什么广度优先深度优先的问题（记得小的时候看吴军的《数学之美》中有提到，但课上自然还没学到）。

但这回溯写起来好不容易。。。好复杂啊啊啊啊

后来！

在我实在生无可恋的时候。。。我ultimately向某大神求助了。。他的方法

巧妙地避开了要回溯的问题。。不逐行生成，直接随机生成每行中Queen的位置存储在一个list里

初始column = [0,1,2,3,4,5,6,7]

然后random.shuffle(column)直到满足条件

妙啊。。。我该换个角度想想的嗐！

于是我以这个思路重写了一波，但print出来不对。。于是检查了挺久才发现

当我给list1的某行某列赋值时，总是整一列全部给赋上值了！！！！（吐了）

上网查一下，才发现这个“python二维数组之巨坑”！！！----

二维list若用 [[0] * 5] * 5 这样的方式初始化，则指定元素赋值也会造成所有行的该列也被赋值，与预期不符合。

我把list1 = [['| '] * 8] * 8改成了list1 = [['| '] * 8 for i in range(8)]才最终可以。

QAQ终于把这么一道八皇后给做好了。。。TAT

我还看到了一些似乎更简洁的方法。。。之后或许会再康康orz

anyway，现在就先这样吧虽然花了很多很多时间、掉进好几个大大小小坑里但还是收获满满呢：）

哎，终于肝完了近两天的ddl。。。无语凝咽去听几首Queen的歌吧，既然终于kill掉了这恶搞eight queen...(

超爱波西米亚狂想曲！

reference：

短短的路走走停停被抢注啦（2018），【算法】用回溯法(backtracking algorithm)求解N皇后问题(N-Queens puzzle)，https://www.jianshu.com/p/bb123944d3e5

NicolasLinJieChuang(2018),python 使用递归回溯解决八皇后问题详细解释，https://blog.csdn.net/weixin_41865447/article/details/80034433?depth_1-utm_source=distribute.pc_relevant.none-task&utm_source=distribute.pc_relevant.none-task

_MCTW(2015),python基础: 遍历与八皇后问题浅析,https://blog.csdn.net/u014386870/article/details/44098151?depth_1-utm_source=distribute.pc_relevant.none-task&utm_source=distribute.pc_relevant.none-task

VeyronC(2019),python二维list之巨坑https://www.cnblogs.com/xrszff/p/11493666.html

python eight queens