Backtracking（JavaScript）でナイトツアーを解決する

Question

バックトラックを使用してKnight's Tourの問題を解決するためにJavaScriptでアルゴリズムを作成しようとしていますが、動作しません。基本的に、この関数は、という配列を出力し、それぞれの移動の位置を含むという配列を出力することになっています。ただし、配列には場所が追加されず、[[0,0]]のままです。ここに私のコードです。どんな手掛かり？

var unit = 75; 

function m1(position) { position[0] += unit; position[1] += 2*unit; return [position[0],position[1]]} 
function m2(position) { position[0] -= unit; position[1] += 2*unit; return [position[0],position[1]]} 
function m3(position) { position[0] += 2*unit; position[1] += unit; return [position[0],position[1]]} 
function m4(position) { position[0] -= 2*unit; position[1] += unit; return [position[0],position[1]]} 
function m5(position) { position[0] += unit; position[1] -= 2*unit; return [position[0],position[1]]} 
function m6(position) { position[0] -= unit; position[1] -= 2*unit; return [position[0],position[1]]} 
function m7(position) { position[0] += 2*unit; position[1] -= unit; return [position[0],position[1]]} 
function m8(position) { position[0] -= 2*unit; position[1] -= unit; return [position[0],position[1]]} 

var moves = [m1, m2, m3, m4, m5, m6, m7, m8]; 
var currentPosition = [0, 0]; 
var visited = [currentPosition]; 

function knightour(currentPosition) 
{ 

    var j; 

    if (promising(currentPosition)) 
    { 

     if (visited.length == 64) 
     { 
      return visited; 
     } 
     else 
     { 
      for (j=0; j<moves.length; j++) 
      { 
       context.drawImage(knight, currentPosition[0], currentPosition[1]); 
       alert("NEXT"); 
       visited.push(moves[j](currentPosition)); 
       knightour(currentPosition); 
      } 
     } 
    } 
} 

function promising(currentPosition) 
{ 
    if (currentPosition[0] < 600 && currentPosition[0] >= 0 && 
     currentPosition[1] < 600 && currentPosition[1] >= 0 && 
     isVisited(currentPosition, visited)) 
     { 
     return true; 
    } else { 
     return false; 
    } 

} 

function isVisited(position, visited)    // visited is an array of size n of array of size 2 ([x,y]) 
{              // currentPosition is an array of size 2 ([x,y]) 
    for (var i=0; i<visited.length; i++) 
    { 
     if (position[0] == visited[i][0] && position[1] == visited[i][1]) 
     { 
      return true; 
     } 
    } 
    return false; 

} 

ありがとうございます。

Answer 1

あなたはバックトラックアルゴリズムを整理していなくても、アルゴリズムが必要とするボードにすでに表示されているボードと競合しています。最良の方法は、最初からやり直し、アルゴリズムを解き、それをすべて表示することを心配することです。そのような考えから、まず擬似コードでアルゴリズムを解決し、その擬似コードをJavaScriptに変換する必要があります。 （ヒント：あなたのコードでは、現在の位置を変更するように見えることはありません）

私はこのような全体的なプロセス参照：スタックが大きいよう

findAllKnightsTours: 
    for every board position 
    set path = empty 
    set board = all false 
    findKnightsTour(currentPosition, path, board) 

パスを有します。正方形が訪問されたかどうかを調べるたびにそれを検索することは苦痛なので、私は別の "ボード"を使用します。単純化のために、単純な配列を使用していますが、ボードはブール値の行列でなければなりません（false == visited、true = visited）。

findKnightsTour(position, path, board): 
    push position onto path 
    set board[position] to true 

    if path.length == 64 
    print out path 
    else 
    for each of the eight moves 
     next = calculate new position based on move 
     if validPosition(next, board) 
     findKnightsTour(next, path, board) 

    set board[position] to false 
    pop position off path 

位置がボード限界内であり、現在（すなわち、真である）訪問されていないかどうかを確認するためにvalidPositionルーチンをチェックします。

このルーチンを見ると、現在の位置がパスとボードに追加され、物が実行され、パスとボードから削除されます。これは、アルゴリズムのバックトラック部分です。状態を保存して何かを試してから、古い状態を復元します。

Readerの簡単な練習として、JavaScriptの変換はそのままです。