CODEWITHSUNDEEP
javascriptalgorithmrecursion
brainkim
brainkim

Reputation: 981

Animating a recursive backtracking algorithm in javascript

I'm trying to create a live demo of a backtracking algorithm (with simple forward checking) in javascript. I've gotten the algorithm down pat in its recursive form, but now I'm stuck trying to animate it using javascript's setTimeout or setInterval, which I'm assuming would require me to convert the recursive solution to an iterative one. Here's the function (rewritten to be a little more general):

function solve(model) {
    if (model.isSolved()) return true;
    var chosen = chooseVariable(model); //could be random or least constrained
    var domain = model.getDomain(chosen);
    var i, assn;
    for (i = 0; i < domain.length; i++) {
        assn = domain[i];
        model.set(chosen, assn);
        if (solve(model)) return true;
        else model.undo();
    }
    return false;

}

As you can see, I've made it so that the model can undo it's own actions, rather than having a separate action stack or cloning the model at each level of recursion. Is there a way to convert the function above into one that could be used with setTimeout or setInterval? Would I have to significantly change the model/add another stack to keep track of the chosen variable/attempted assignments? Do I need a closure with mutating variables? I'm mostly looking for pseudocode to point me in the right direction.

Upvotes: 1

Views: 897

Answers (2)

Bergi
Bergi

Reputation: 664297

I'm assuming this require me to convert the recursive solution to an iterative one.

No, right the other way round. Yours still is iterative in some parts (the for-loop).

You will have to make the steps asynchronous, so that each step takes a callback which is fired when its animation is done and you can continue. Since you will want to animate every single iteration step, you will have to make them asynchronous with a recursive-like callback - continuation passing style.

Here's how:

function solve(model, callback) {
    if (model.isSolved())
        return callback(true);
    var chosen = chooseVariable(model); // could be random or least constrained
    var domain = model.getDomain(chosen);
    var i = 0, assn;
    (function nextStep() {
        if (i < domain.length) {
            assn = domain[i];
            model.set(chosen, assn);
            solve(model, function(solved) {
                if (solved)
                    callback(true);
                else {
                    model.undo();
                    i++;
                    nextStep();
                }
            });
        } else
            callback(false);
    })();
}

Now you can simply make this recursive variant asynchronous by introducing setTimeout where you need it (usually after displaying the model state):

function solve(model, callback) {
    if (model.isSolved())
        return callback(true);
    var chosen = chooseVariable(model); // could be random or least constrained
    var domain = model.getDomain(chosen);
    var i = 0, assn;
    (function nextStep() {
        if (i < domain.length) {
            assn = domain[i];
            model.set(chosen, assn);
            solve(model, function(solved) {
                if (solved)
                    callback(true);
                else {
                    model.undo();
                    i++;
                    setTimeout(nextStep, 100);
                }
            });
        } else
            setTimeout(callback, 100, false);
    })();
}

Upvotes: 1

user742071
user742071

Reputation:

You could program it asynchronously using for example deferreds. jQuery provides an implementation of deferreds and you could have a look at this example which uses timeouts:

http://api.jquery.com/deferred.promise/#example-0

Of course you need only one timeout which always resolves (succeeds).

Upvotes: 0

Related Questions