前一篇： 升级到Wordpress 2.7
后一篇：部分译作回顾

N王后问题（续）

2009年01月22日 编程技术

N王后问题，是一个科学谜题，指的是在把N个王后放到N*N的棋盘上，结果是任何王后之间都不会彼此威胁。换句话说，每个后继的王后既不能与前面的王后在同一行、同一列，也不能位于同一对角线上。N王后问题给出了Python代码。下面是JavaScript代码，但结果有些误差，不知何故。

  1. function conflict(state,posX)    {
  2.     var posY = state.length;
  3.     for (var i=0;i<posY ;i++ )
  4.     {
  5.         var differ = Math.abs(state[i]-posX);
  6.         if (differ == 0 || differ == (posY - i))
  7.         {
  8.             return true;
  9.         }
  10.     }
  11.     return false;
  12. }
  13.  
  14. function queens(num,state,solutions){
  15.     for (var x=0;x<num ;x++ )
  16.     {
  17.         if (!conflict(state,x))
  18.         {
  19.             if (state.length == (num-1))
  20.             {
  21.                 solutions.unshift(x);
  22.                 return true;
  23.             }
  24.             var result = queens(num,state.concat(x),solutions);
  25.             if (result)
  26.             {
  27.                 if (state.length==0)
  28.                 {
  29.                     solutions.unshift(x);
  30.                     continue;
  31.                 }
  32.                 solutions.unshift(x);
  33.                 return true;
  34.             }
  35.        
  36.         }
  37.  
  38.     }
  39. }

用法如下：

  1. var result = [];
  2. queens(4,[],result);
  3. console.log(result);// [3, 1, 0, 2, 2, 0, 3, 1, 1, 3, 0, 2, 0, 3, 1, 2]


有话要说？ 评论RSS

前一篇： 升级到Wordpress 2.7
后一篇：部分译作回顾

朋友们的留言

  1. 为之漫笔 » N王后问题 | 一月 24th, 2009 at 11:48

    [...] 关于N王后问题 模块代码： #nqueens.py [...]

我来说两句儿


麻烦输入验证码 If you cannot see the CheckCode image,please refresh the page again!