Knight's Tour algorithm - TypeError: Cannot set property of undefined

Question

我正在尝试实现 N. Wirth "Algorithms and Data Structures" 一书中的 Knight's Tour 算法。原始版本是用 Oberon 编写的： https://drive.google.com/file/d/0B7KbTu852Hi3cG5jYUVDX3Z4Yjg/view?usp=sharing

问题是我在第 h[u][v] = i; 行收到错误 "Cannot set property '-1' of undefined" 在第 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);

Knight's Tour algorithm - TypeError: Cannot set property of undefined

Knight's Tour algorithm - TypeError: Cannot set property of undefined

javascript

algorithm

knights-tour