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
- Every team must play every other team
- No two teams should play each other twice
- 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;
};