Project Euler 393

gistfile1.js

var count   // number of final positions
var N       // total cells in the board
var n       // grid partition

function dfs(now, next) {
    for (var k = 0; k < N; k += 1) {
        // Find an ant to move.
        if (now[k] > 0) {
            // Try to move it to the right.
            if ((k % n < n - 1) && (next[k + 1] == 0) 
                    && ((next[k] == 0) || (next[k] != now[k] + 1))) {
                next[k + 1] = now[k]
                now[k] = 0
                dfs(now, next)
                now[k] = next[k + 1]
                next[k + 1] = 0
            }
            // Try to move it to the left.
            if ((k % n > 0) && (next[k - 1] == 0) 
                    && ((next[k] == 0) || (next[k] != now[k] - 1))) {
                next[k - 1] = now[k]
                now[k] = 0
                dfs(now, next)
                now[k] = next[k - 1]
                next[k - 1] = 0
            }
            // Try to move it up.
            if ((k >= n) && (next[k - n] == 0) 
                    && ((next[k] == 0) || (next[k] != now[k] - n))) {
                next[k - n] = now[k]
                now[k] = 0
                dfs(now, next)
                now[k] = next[k - n]
                next[k - n] = 0
            }
            // Try to move it down.
            if ((k < N - n) && (next[k + n] == 0) 
                    && ((next[k] == 0) || (next[k] != now[k] + n))) {
                next[k + n] = now[k]
                now[k] = 0
                dfs(now, next)
                now[k] = next[k + n]
                next[k + n] = 0
            }
            // We don't need to consider the other ants. The above exploration 
            // has already found all the other possibilities.
            break
        }
    }
    // Check if the position is valid.
    for (var i = 0; i < N; i += 1) {
        if (next[i] == 0) {
            return
        }
    }
    // We implemented the DFS exploration in such a way that if we got here
    // we must have a valid final position. So we increase the counter.
    count += 1
}

function euler_393(size) {
    count = 0
    n = size
    N = n * n
    // This array holds the ants that need to be moved. 
    var now = []   
    // This array holds the ants that have already been moved.
    var next = []  
    // Initialize positions, 0 is empty.
    for (var k = 0; k < N; k += 1) {
        now[k] = k + 1
        next[k] = 0
    }
    // Use Depth First Search to compute the number of possible ways. 
    dfs(now, next)
    return count
}

// Warning: this is very slow for n > 4
print(euler_393(4))