騎士旅行算法 - 類型錯誤：無法設置的不確定

Question

我試圖實現從書「算法與數據結構」，由N.沃斯騎士旅行算法性能。原文寫的奧伯倫： https://drive.google.com/file/d/0B7KbTu852Hi3cG5jYUVDX3Z4Yjg/view?usp=sharing

的問題是，我收到「未定義無法設置屬性‘-1’，」錯誤的行h[u][v] = i; 在步驟36算法進行到董事會的死衚衕。幫助不大？

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：

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

檢查的第一件事是，你是如何劃定範圍的u和v。

檢查這個代碼。

在first()和next()你給u和v作爲參數。但是，這意味着該函數具有u和v從你在canBeDone引用一個不同的副本。

現在的問題是，該算法時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);