Animating a recursive backtracking algorithm in javascript

Question

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.

couldn't you just implement a kind of sleep and update your animation in another animationLoop()? — Regenschein
– Regenschein, Commented Jul 18, 2013 at 10:21
Is that really a viable solution? I was under the impression that sleep implementations in js are bad practice given that javascript is single-threaded/asynchronous. — brainkim
– brainkim, Commented Jul 18, 2013 at 10:36

Bergi · Accepted Answer · 2013-07-18 12:40:23Z

1

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);
    })();
}

answered Jul 18, 2013 at 12:40

Bergi

671k162 gold badges1k silver badges1.5k bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

brainkim Over a year ago

Found a bug! In my implementation of your code, backtracking and reassignment are properly delayed but consecutive assignments are still instantaneous. I'll try to fix it on my own before I accept this answer. Thanks for the lead!

Bergi Over a year ago

Yes, you probably want to put the assignment steps in a setTimeout(function(){ var domain = …; setTimeout(function(){ var i=0,… ; },100); },100); cascade. This is only complicated when you're dealing with control flow (loops etc) which has to be rewritten (and I've shown you how) but now that execution is quite linear (with recursive calls) you can basically insert such delays wherever you want.

user742071 · Accepted Answer · 2013-07-18 11:42:38Z

0

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).

answered Jul 18, 2013 at 11:42

user742071

Collectives™ on Stack Overflow

Animating a recursive backtracking algorithm in javascript

2 Answers 2

2 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

2 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related