商城网站开发定制,传统企业建设营销型网站,蒙文网站建设,免费网站制作多少钱最近在看Python基础#xff0c;遇到了八皇后问题#xff0c;看得整个人晕晕乎乎#xff0c;甚至开始怀疑人生。问题是在一个8*8的国际象棋棋盘上摆放8个皇后#xff0c;问题一是找出一个解#xff0c;问题二是问有多少个解。这里我把我自己的理解写出来#xff0c;只针对…最近在看Python基础遇到了八皇后问题看得整个人晕晕乎乎甚至开始怀疑人生。问题是在一个8*8的国际象棋棋盘上摆放8个皇后问题一是找出一个解问题二是问有多少个解。这里我把我自己的理解写出来只针对最后一个落子的情况不涉及递归希望能有所帮助。首先定义冲突函数def conflict(state,nextQueenColumnIndex)#state是当前已经放置的皇后在棋盘上面的列索引组成的元组nextQueenColumnIndex是将要放置的下一个皇后(简称A)的列索引这里关键问题在于要将A与之前放置的皇后一一比对找出是否会被吃掉(存在冲突)因此需要做循环之前已经放置的皇后个数当然是len(state),因为索引是从0开始算的所以已经放置的最后一个皇后的行索引为len(state)-1因此A的行索引为len(state)。nextQueenRowIndexlen(state)for everyqueen in range(nextQueenRowIndex):#注意range右边是开区间取出每一行等行索引。if abs(state[everyqueen]-nextQueenColumnIndex) in (0,nextQueenRowIndex-everyqueen):#,这里需要明白的是假如state为(0123)那么代表的是第一行皇后列索引为0第二行皇后列索引为1以此类推。那么state[everyqueen]实际上就是取出了每一行皇后的列索引。return Truereturn False#这里有两个关键点第一、是abs(state[everyqueen]-nextQueenColumn)0检查A是否与其他皇后在同一列abs(state[everyqueen]-nextQueenColumn)nextQueenRowIndex-everyqueen检查A是否与其他皇后在一条斜线上(对角线)其实就是行索引-行索引列索引-列索引就代表在一条斜线上面。第二、注意return False是与for对齐的因为只要存在冲突就会return True当for循环执行完后都没有return的话那么就会执行到return False也即不存在冲突那么A落在这个棋盘点就是对的以上冲突函数就写完了。然后我们来写主函数def MyQueen(state,queencount):#state依然代表当前已经放置的皇后在棋盘上面的列索引组成的元组queencount代表皇后的总数(包括已有的和准备下的)下面讨论的是最简单的一种情况就是已知棋盘的状态需要下最后一颗子。if len(state)queencount-1#len(state)代表已落子的个数如果与总数-1相等的话那么我们要下的必然是最后一颗子。这最后一颗子怎么下当然是要与前面的每一行的皇后做冲突比对好在我们的冲突函数已经写好了可以直接用。for n in range(queencount):取出每一列的列索引其实就是说在当前棋盘状态下落子第一列行不行落子第二列行不行。。。落子最后一列行不行其实这里的range(queencount)只是方便我们按次序取出12345。。。因为要注意这道题的前提是棋盘是真方形是在N*N的棋盘上面放置N个皇后因此我们这里直接用queencount比较方便当然如果你已经知道棋盘大小为8或者16直接用range(8)或者range(16)也行。if not conflict(state,n):#n就是要落子的列索引print(n)#输出的n就是A的列索引了也即最后一个皇后落子的棋盘列索引位置。Over上面就讨论了八皇后问题中落最后一颗子的简单情况当然是用这个函数的前提是要知道棋盘的当前落子状态及皇后的总数我目前刚把这个看懂写出来也为自己加深印象后面的还要继续学习。。。
