Nクイーン問題(N Queens Problem) - JavaScript

JS

　ビンゴの問題を考えていたとき、もしかして、順列で、Nクイーン問題も解けるかもと思ってやってみたら、案の定、解けました。縦横は順列で条件を満たしているので、後は、斜めをチェックするだけ。
　ただ、ｎを増やすと凄く遅くなりますので、アルゴリズム辞典に載っているような普通のやり方の方がいいようです。(^_^;

●nQueens.html

<html>
<head>
<title>nQueens.html</title>
<script type="text/javascript">
function next_perm(p, n, r)  // 順列生成
{
  var i, j, k, tmp;
  if(r <= 0 || n < r) return(false);
  for(i = r + 1; i <= n-1; i++)
    for(j = i; j >= r + 1 && p[j-1] < p[j]; j--)
      tmp = p[j], p[j] = p[j-1], p[j-1] = tmp;
  for(i = n - 1; i > 0 && p[i-1] >= p[i]; i--);
  if(i == 0) return(false);
  for(j = n - 1; j > i && p[i-1] >= p[j]; j--);
  tmp = p[i-1], p[i-1] = p[j], p[j] = tmp;
  for(k = 0; k <= ((n-1)-i)/2; k++)
    tmp = p[i+k], p[i+k] = p[(n-1)-k], p[(n-1)-k] = tmp;
  return(true);
}

var N=8;  // 変更自由
function Check(p)  // 斜めのチェック
{
  for(var i=0; i< N-1; i++){
    for(var j=1; j< N-i; j++){
      if(p[i+j]==p[i]+j||p[i+j]==p[i]-j) return(true);
    }
  }  
  return(false);
}

function disp(p,n)
{
  document.write(n,"<br>");
  for(var i=0; i< N; i++){
    for(var j=0; j< N; j++){
      var ch="";
      if(j==p[i]) ch="■"; else ch="□";  
      document.write(ch);
    }
    document.write("<br>");
  }
}

</script>
</head>
<body>
<script type="text/javascript">
var cnt=0;
var p=new Array(N);
for(var i=0; i< N; i++) p[i]=i;

var tm=(new Date()).getTime();  // Timer start
do{
  if(Check(p)) continue; 
  // チェックを潜り抜けたものだけを表示
  cnt++;
  disp(p,cnt);
}while( next_perm(p,N,N) );
document.write("Total : ",cnt,"<br>");
tm=(new Date()).getTime()-tm;  // Timer stop
document.write("Runtime : ",tm/1000.0, "[sec]<br>");
</script>
</body>
</html>

●実行結果

1
■□□□□□□□
□□□□■□□□
□□□□□□□■
□□□□□■□□
□□■□□□□□
□□□□□□■□
□■□□□□□□
□□□■□□□□
2
■□□□□□□□
□□□□□■□□
□□□□□□□■
□□■□□□□□
□□□□□□■□
□□□■□□□□
□■□□□□□□
□□□□■□□□

…(省略)…

92
□□□□□□□■
□□□■□□□□
■□□□□□□□
□□■□□□□□
□□□□□■□□
□■□□□□□□
□□□□□□■□
□□□□■□□□
Total : 92
Runtime : 0.033[sec]

※参考URL
●［PDF］Nクイーン問題