还记得八皇后的解法吗 (3)

  

还记得八皇后的解法吗

  继续,更新棋盘状态。

  

还记得八皇后的解法吗

  根据上图,将第2个皇后置于第2行第4列。

  

还记得八皇后的解法吗

  继续,更新棋盘状态。

  

还记得八皇后的解法吗

  看上去不错,接着,将第3个皇后置于第3行第1列。

  

还记得八皇后的解法吗

  继续,更新棋盘状态。

  

还记得八皇后的解法吗

  咦,似乎成了。

  

还记得八皇后的解法吗

  BINGO!4皇后的第一个解,找到了。

 

  现在,回顾上面的整个过程,做点抽象,引入一点计算机的思维,就可以得出解题流程了。

  

还记得八皇后的解法吗

  步骤清楚了,现在需要思考的就是过程中很关键的一步——根据已放置的皇后计算下一行棋格状态的逻辑实现。

 

  这里需要回到国际象棋的规则本身了。

  一个皇后在棋盘上的攻击范围如下图所示:

  

还记得八皇后的解法吗

  对这个图做点数学上的抽象分析:棋盘本身是一个标准的坐标平面,每个棋格都有着很明细的坐标位置。所以,上图可以转换成下面的模型:

  

还记得八皇后的解法吗

  受皇后攻击的点,按照和皇后(Q点)的相对位置,可以分成4类

横向(A1)

纵向(A2)

正斜(A3)

反斜(A4)

  横向攻击其实不用考虑,因为解题的思路本身就是按行来推进的,先天就过滤掉横向攻击点了。

  纵向攻击很容易判断,Q点 和 A2点 的 x坐标 相等,就处于攻击范围内。

  不那么直观的是两条斜线的情况,需要算一下。将正斜线攻击(A3类点)和反斜线攻击(A4类点)的坐标转换一下,表示成基于Q点的偏移——

  Q:( x0, y0 )

  正斜线 A3:( x0 + m, y0 + m )

  反斜线 A4:( x0 - m, y0 + m )

 

  通过观察不难得出规律——

  正斜线上的点: (x0 + m) – x0 = (y0 + m) – y0

  即:A3点的横坐标值 - Q点的横坐标值 = A3点的纵坐标值 – Q点的纵坐标值

  反斜线上的点: x0 + y0 = (x0 – m) + (y0 + m)

  即:Q点横坐标值 + Q点纵坐标值 = A4点横坐标值 + A4点纵坐标值

 

  自此,通过皇后所在的棋格判断棋盘上另一处方格是否处于被攻击状态的逻辑就全部搞清楚了。

  流程和方法都有了,是时候写代码实现具体程序了。

 

  用什么语言来做这事呢?

  QBasic,C,C#,Java,Python,Lua,JavaScript,PHP, ……

  我在脑袋里慢慢遍历着我所精通的20门语言,俗话说艺不压身,但俗话却没说选择困难症,哎……

  (以上这段纯属虚构)

 

  最终,我决定用最近的新欢—— Go 语言来写这个程序。

 

  延续之前的思路,依然将重心放到4皇后的情况,直译上面的分析过程,然后代码差不多长这样: 

内容版权声明:除非注明,否则皆为本站原创文章。

转载注明出处:https://www.heiqu.com/zyydfg.html