This is the 12th MATLAB Online Programming Contest.
The classic Sudoku puzzle is straightforward to solve algorithmically. For this contest, we have generalized the problem somewhat. You are given a partially filled grid and a list of numbers to put into the grid. These numbers are not limited to integers, and there may be more of them than the grid requires. In other words, you may have some left-over numbers that cannot be used. These unused numbers do not affect your score. Using the provided numbers, fill in the rest of the grid so as to minimize the resulting error (defined below).
Rather than enforcing the uniqueness of all rows, columns, and regions, your job is to make each of these add up to the same target sum (to the extent possible). That target number is the sum of all the numbers in the grid divided by 9.
Suppose you are given the vector x and the matrix aInit.
x = [ 4 3 3 1.2 ... 1 3 2 4 ... 1 4 2 7 ... 5 0.5 4.3 ] ; aInit = [ 0 0 2 0 ; 1.7 0 0 4.1 ; 0 0 0 0 ; 1 0 2.8 0 ]Figure 2 shows the problem as it might appear in the newspaper (i.e. the zeros have been removed from the matrix aInit).
Figure 3 shows one solution to the puzzle.
Given the numbers chosen to fill the grid, we can calculate that each column, row, and region should total exactly sum(a(:))/4, or 9.95. We have left out the numbers [0.5 4.3 5 7]. Note that if we had chosen different numbers, the target sum would also change.
To calculate how well we did, consider the sum across rows, columns, and regions of the absolute value of the deviation from the ideal.
>> a = [ 4 1.2 2 3 ; 1.7 3 1 4.1 ; 3 2 4 1 ; 1 4 2.8 2 ] >> target = sum(a(:))/4 >> colSums = sum(a); >> rowSums = sum(a'); >> index = [1 2 5 6; 3 4 7 8; 9 10 13 14; 11 12 15 16]'; >> regSums = sum(a(index)); >> result = ... sum(abs(colSums - target)) + ... sum(abs(rowSums - target)) + ... sum(abs(regSums - target))For a perfect solution, this result is zero. In this case the result is 1.8.
The average result for the entire test suite, along with the associated runtime of your entry, gets passed to our scoring algorithm before returning a final score, according to the equation
We don't publish the values k1, k2, and k3, but they aren't hard to figure out. Your entry will time out and be disqualified if it takes more than 180 seconds (three minutes).
The sudoku solving routine is solver.m.
solution = solver(puzzle,list)where puzzle is the partially filled n^2-by-n^2 solution matrix aInit, list is the vector x of additional numbers available to place in the grid (and which may be longer than the empty spaces in puzzle), and solution is the completed solution a.
Keep in mind that this function must have the right signature: two input arguments, one output argument. Variable names are unimportant. To test this function with the test suite in the ZIP-file, run runcontest.m.
We also encourage you to discuss your solutions and strategies with others. You can do this by posting to the newsgroup thread that we've started.
The following are prohibited:
Contests are divided into segments where some or all of the scores and code may be hidden for some users. Here are the segments for this contest: