Solving a partially completed 10x10 tournament schedule

Question

My buddy schedules a dart tournament, and got into trouble when there were some scheduling conflicts. He has the first 3 weeks in the books, and needs to finish out the rest of the schedule. Turns out it is a pretty difficult puzzle.

So I figured I could quickly solve it with a constraint satisfaction problem. Unfortunately, the solution I came up with does not complete in any reasonable amount of time when pre-filling the first 3 weeks (I haven't waited it out for a solution.) Although, it finishes very quickly if I do not pre-fill any weeks.

Is there any optimization I can make to my solution to let it finish quickly?

Constraints

1. Every team must play every other team
2. No two teams should play each other twice
3. A team must only play once a week

10x10 Matrix Schedule

Here is the schedule with the first 3 weeks already entered. Each row represents a team; each column represents a week.

For example, team 1 plays team 10 in week 1, team 9 in week 2, and team 4 in week 3. (10, 9, 4)

Solve for weeks 4-9:

list = [
    [10, 9, 4, null, null, null, null, null, null],
    [9, 4, 5, null, null, null, null, null, null],
    [8, 6, 7, null, null, null, null, null, null],
    [7, 2, 1, null, null, null, null, null, null],
    [6, 7, 2, null, null, null, null, null, null],
    [5, 3, 8, null, null, null, null, null, null],
    [4, 5, 3, null, null, null, null, null, null],
    [3, 10, 6, null, null, null, null, null, null],
    [2, 1, 10, null, null, null, null, null, null],
    [1, 8, 9, null, null, null, null, null, null]
];

Solution

//start here
add(0, 0);

//recursive function to add the next value to the schedule
// row - table row to solve for
// col - table column starting position
// callback - called on success or failure
function add(row, col, callback) {
    callback = callback || function () {};

    //check if done
    if (row == list.length) {
        return callback(true);
    }

    //find the next number to place
    var nextNum = 1;
    for (i = 0; i < 9; i++) {
        if (row + 1 == nextNum || list[row][i] == nextNum) {
            nextNum++;
            i = -1;
        }
    }

    //check if done
    if (nextNum > 10) {
        return callback(true);
    }

    //find next empty slot with empty matching pair
    while (list[row][col] !== null || list[nextNum - 1][col] !== null) {

        //no match found, fail
        if (col == 9) {
            return callback(false);
        }
        col++;
    }

    //success, set values
    list[row][col] = nextNum;
    list[nextNum - 1][col] = row + 1;

    //continue, solve next value (using timeout to let UI update)
    setTimeout(function () {
        nextJob(row, col, nextNum, callback);
    }, 0);
};

function nextJob(row, col, nextNum, callback) {
    //continue solving the current row
    add(row, 0, function (success) {

        if (success) {
            //solve for next row
            add(row + 1, 0, function (success) {
                //fail, undo last value and try the next column
                if (!success && col < 8) {
                    list[row][col] = null;
                    list[nextNum - 1][col] = null;

                    return add(row, col + 1, callback);
                }
                callback(success);

            });
        } else if (col < 8) {
            //fail, undo last value and try the next column
            list[row][col] = null;
            list[nextNum - 1][col] = null;

            add(row, col + 1, callback);
        } else {
            callback(success);
        }
    });
};

Demos

Click the "Start" button to run the demos. You can click "slow" to slow it down, and "fast" to run full speed again.

Pre-filled

Here is a jsFiddle running this solution against the pre-filled weeks. I've lever let it finish, takes too long.

Blank Schedule

Another jsFiddle running this solution against a blank schedule. It finishes very quickly.

** UPDATE **

@Pablo led me down researching the sudoku solutions, and I used this code (video) as reference to find my own solution. I am still interested in researching dancing links.

Any other insight as to why this works over my original solution would be appreciated. They both appear to be using a breadth first search.

Demo

jsFiddle of the working solution

list = [
    [10, 9, 4, null, null, null, null, null, null],
    [9, 4, 5, null, null, null, null, null, null],
    [8, 6, 7, null, null, null, null, null, null],
    [7, 2, 1, null, null, null, null, null, null],
    [6, 7, 2, null, null, null, null, null, null],
    [5, 3, 8, null, null, null, null, null, null],
    [4, 5, 3, null, null, null, null, null, null],
    [3, 10, 6, null, null, null, null, null, null],
    [2, 1, 10, null, null, null, null, null, null],
    [1, 8, 9, null, null, null, null, null, null]
];

window.solve = function () {
    var i = null;
    var j = null;

    var possiblities = {};

    if (isFull()) {
        return true;
    } else {
        for (var x = 0; x < 10 && i === null; x++) {
            for (var y = 0; y < 10 && j === null; y++) {
                if (list[x][y] === null) {
                    i = x;
                    j = y;
                }
            }
        }

        possiblities = possibleEntries(i, j);

        for (var k = 0; k < 10; k++) {
            if (possiblities[k] === 0) {
                list[i][j] = k + 1;
                list[k][j] = i + 1;
                console.log(JSON.stringify(list));
                var success = solve();
                if (success) {
                    return true;
                }
                list[list[i][j] - 1][j] = null;
                list[i][j] = null;
                console.log(JSON.stringify(list));
            }
        }
        return false;
    }
};

window.isFull = function () {
    for (var x = 0; x < 10; x++) {
        for (var y = 0; y < 10; y++) {
            if (list[x][y] === null) {
                return false;
            }
        }
    }
    return true;
};

window.possibleEntries = function (x, y) {
    var vals = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0];
    for (var i = 0; i < 10; i++) {
        if (i == x) {
            vals[i] = 1;
        }
        if (list[x][i] !== null) {
            vals[list[x][i] - 1] = 1;
        }
        if (list[i][y] !== null) {
            vals[list[i][y] - 1] = 1;
        }
    }
    return vals;
};

Answer 1

This is not really an answer to improve your algorithm, but it did not fit in a comment. Nevertheless it should speed up your application by factor 4 (on my machine):

In short: Try not to update the GUI on each iteration. Doing output in a (tight) loop is bad for performance in almost every language (at least in all that I know).

I expanded your logMsg function a bit to measure and display the speed of execution:

starttime = 0; // initialized in start function with Date.now()
cnt = 0;
perSec = 0;

window.logMsg = function (op, row, nextNum) {
    cnt++;
    if (cnt % 100 == 0) {
        perSec = Math.floor(cnt / ((Date.now() - starttime) / 1000));
        var element = document.getElementById("speed");
        element.innerHTML = cnt + "<br/>" + perSec + "/sec";
    }
    // return;

    [your code here]
};

Fiddle: https://jsfiddle.net/8me8adhn/4/

If I run it like this, I get about 50 operations per second. If I uncomment the return above (to disable the remaining log output), I get about 200.

You could try to update the GUI each 100/200/1000 iterations only to still have the log output but don't impact the performance of the application…