# Solving a partially completed 10x10 tournament schedule

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

//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
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

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;

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

• 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. – Pablo Jun 19 '15 at 6:17
• 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 ? – Loufylouf Jun 19 '15 at 8:36

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;


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.