6
\$\begingroup\$

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;
};
\$\endgroup\$
  • 1
    \$\begingroup\$ Your problem is very similar to completing a Sudoku board. I'm not sure if the small differences make it simpler (Sudoku is NP-complete).It does seem to be a Exact cover problem and 9x9 Sudokus can be solved in seconds, so I think this problem could be solved by a similar algorithm like Dancing Links. Reducing your problem to a known one may be the solution or help you to better understand it. \$\endgroup\$ – Pablo Jun 19 '15 at 6:17
  • \$\begingroup\$ Did you try to do some profiling using Chrome javascript profiler ? If so, could you provide the results of such profiling, on an example that did end ? \$\endgroup\$ – Loufylouf Jun 19 '15 at 8:36
1
\$\begingroup\$

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…

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.