Knight's Tourアルゴリズム - TypeError：未定義のプロパティを設定できません

Question

Night Wirthの書籍「アルゴリズムとデータ構造」からKnightのツアーアルゴリズムを実装しようとしています。オリジナル版はオベロンで書かれている： https://drive.google.com/file/d/0B7KbTu852Hi3cG5jYUVDX3Z4Yjg/view?usp=sharing

問題は、私はステップ36のアルゴリズムでラインh[u][v] = i; でエラー「プロパティを設定することはできません 『-1』未定義の」を受けることであるボードの行き止まりに行きます。リトルヘルプ？

var n = 8; // size of the board 
var nsqr = n * n; 
// board matrix 
var h = []; 
for (var i = 0; i < n; i++) { 
     h[i] = []; 
} 
var dx = [2, 1, -1, -2, -2, -1, 1, 2]; // coordinates difference along X, possible 8 moves 
var dy = [1, 2, 2, 1, -1, -2, -2, -1]; // coordinates difference along Y, possible 8 moves 

// knight's tour 
function knightsTour(xin, yin) { 
    clear(); 
    h[xin][yin] = 1; // initial position and step number 
    var done = false; 
    tryNextMove(xin, yin, 1, done); 
} 
// clear 
function clear() { 
    for (var i = 0; i < n; i++) { 
     for (var j = 0; j < n; j++) { 
      h[i][j] = 0; 
     } 
    } 
} 
// try next move 
function tryNextMove(x, y, i, done) { 
    var eos; // end of steps, bool 
    var u, v; // new step coordinates 
    var k; // new step index 

    function next(eos) { 
     do { 
      k++; 
      if (k < 8) { 
       u = x + dx[k]; 
       v = y + dy[k]; 
      } 
     } while (k < 8 && (u < 0 || u >= n || v < 0 || v >= n || h[u][v] != 0)); 
     eos = (k == 8); 
    } 

    function first(eos) { 
     eos = false; 
     k = -1; 
     next(eos); 
    } 

    if (i < nsqr) { 
     first(eos); 
     while (!eos && !canBeDone(u, v, i+1)) { 
     next(eos); 
    } 
    done = !eos; 
    } else { 
     done = true; 
    } 
} 
// can tour be done 
function canBeDone(u, v, i) { 
    var done = false; // bool 
    h[u][v] = i; // ERROR here 
    tryNextMove(u, v, i, done); 
    if (!done) { h[u][v] = 0; } 
    return done; 
} 

knightsTour(3, 1); 
console.log(h); 

このバージョンでは、n = 4 ... 9のために働く：あなたがuとvスコープいるか

function knightsTour(x0, y0, size = 8) { 
    var done = false; 
    var h = []; // chess board matrix 
    for (var i = 0; i < size; i++) { 
     h[i] = []; 
    } 
    var nsqr = size * size; 

    // initializing the board 
    for (var i = 0; i < size; i++) { 
     for (var j = 0; j < size; j++) { 
      h[i][j] = 0; 
     } 
    } 

    // coordinates difference along X and Y, possible 8 moves 
    var dx = [2, 1, -1, -2, -2, -1, 1, 2]; 
    var dy = [1, 2, 2, 1, -1, -2, -2, -1]; 

    h[x0][y0] = 1; // initial position and step number 

    // check if move can be done 
    function canBeDone(u, v, i) { 
     h[u][v] = i; 
     done = tryNextMove(u, v, i); 
     if (!done) { 
      h[u][v] = 0; 
     } 
     return done; 
    } 

    // try next move 
    function tryNextMove(x, y, i) { 
     var done; 
     // u, v - new step coordinates; k - new step index; eos - end of steps, bool 
     var env = {"done": false, "eos": false, "u": x, "v": y, "k": -1}; 

     function next() { 
      x = env.u; 
      y = env.v; 
      while (env.k < 8) { 
       env.k += 1; 
       if (env.k < 8) { 
        env.u = x + dx[env.k]; 
        env.v = y + dy[env.k]; 
       } 
       if ((env.u >= 0 && env.u < size) && (env.v >= 0 && env.v < size) && h[env.u][env.v] == 0) { 
        break; 
       } 
      } 
      env.eos = (env.k == 8); 
     } 

     if (i < nsqr) { 
      next(); 
      while (!env.eos && !canBeDone(env.u, env.v, i+1)) { 
       next(); 
      } 
      done = !env.eos; 
     } else { 
      done = true; 
     } 
     return done; 
    } 

    tryNextMove(x0, y0, 1); 
    //console.log(h); 
    return h; 
} 

Answer 1

最初に確認することがあります。

このコードを確認してください。

first()とnext()には、uとvがパラメータとして指定されていました。しかし、これは、あなたがcanBeDoneに参照しているものと異なるコピーuとvを持っていることを意味しています。

ここで問題は、アルゴリズムがu=9のときに失敗することです。これはさらなるデバッグの出発点です。

var n = 8; // size of the board 
var nsqr = n * n; 
// board matrix 
var h = []; 
for (var i = 0; i < n; i++) { 
     h[i] = []; 
} 
var dx = [2, 1, -1, -2, -2, -1, 1, 2]; // coordinates difference along X, possible 8 moves 
var dy = [1, 2, 2, 1, -1, -2, -2, -1]; // coordinates difference along Y, possible 8 moves 

// knight's tour 
function knightsTour(xin, yin) { 
    clear(); 
    h[xin][yin] = 1; // initial position and step number 
    var done = false; 
    tryNextMove(xin, yin, 1, done); 
} 
// clear 
function clear() { 
    for (var i = 0; i < n; i++) { 
     for (var j = 0; j < n; j++) { 
      h[i][j] = 0; 
     } 
    } 
} 
// try next move 
function tryNextMove(x, y, i, done) { 
    var eos; // end of steps, bool 
    var u, v; // new step coordinates 
    var k; // new step index 

    function next(eos) { 
     do { 
      k++; 
      if (k < 8) { 
       uNew = x + dx[k]; 
       vNew = y + dy[k]; 
      } 
     } while (k < 8 || (u < 0 && u >= n && v < 0 && v >= n && (h[u][v] != 0))); 
     eos = (k == 8); 
    } 

    function first(eos) { 
     eos = false; 
     k = -1; 
     next(eos, u, v); 
    } 

    if (i < nsqr) { 
     first(eos); 
     while (!eos && !canBeDone(u, v, i+1)) { 
      next(eos); 
     } 
     done = !eos; 
    } else { 
     done = true; 
    } 
} 
// can tour be done 
function canBeDone(u, v, i) { 
    var done = false; // bool 
    h[u][v] = i; // ERROR here 
    tryNextMove(u, v, i, done); 
    if (!done) { h[u][v] = 0; } 
    return done; 
} 

knightsTour(3, 1); 
console.log(h);