Sudoku - Rules

This is the 12th MATLAB Online Programming Contest.

The Problem

A Sudoku is a popular logic problem involving a 9-by-9 grid that is divided into 3-by-3 grids called regions. The goal is to place the numbers 1 through 9 into the 81 resulting boxes subject to this constraint: no number can be repeated on any row, column, or 3-by-3 region. The puzzle is posed with some numbers (the "givens") already filled in (see Figure 1 below). Your job is to fill in the rest of the boxes.

Figure 1.

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.

Example

The following example, for simplicity, is built around an order=2 grid, rather than the typical order=3 grid with 81 squares. The actual contest will use the order=3 grid.

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 2.

Figure 3 shows one solution to the puzzle.

Figure 3.

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.

Scoring

The overall score for your entry is a combination of how well your algorithm does and how fast it runs on a multi-problem test suite. How well your algorithm does (the "result") is determined by how closely the rows, columns, and regions of your grid add up to the correct value.

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).

Developing Your Entry

The files you need to get started on the contest are included in a ZIP-file available on the MATLAB Central File Exchange. If you download and uncompress this ZIP-file, you will have the files described below.

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.

 >> runcontest

Size limitations

Some of you have asked about the limit to code size. The column in our MySQL database that stores the M-code is of type text, which is limited of 65535 characters. Submissions longer than this limit will fail.

Collaboration and Editing Existing Entries

Once an entry has been submitted, it cannot be changed. However, any entry can be viewed, edited, and resubmitted as a new entry. You are free to view and copy any entry in the queue. If your modification of an existing entry improves its score, then you are the "author" for the purpose of determining the winners of this contest. We encourage you to examine and optimize existing entries.

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.

Fine Print

The allowable functions are those contained in the basic MATLAB package available in $MATLAB/toolbox/matlab, where $MATLAB is the root MATLAB directory. Functions from other toolboxes will not be available. Entries will be tested against MATLAB version 7.0.4 (R14sp2).

The following are prohibited:

• MEX-files
• Java commands or object creation
• eval, feval, inline, function handles, etc.
• Shell escape such as !, dos, unix
• Handle Graphics commands
• ActiveX commands
• File I/O commands
• Debugging commands
• Printing commands
• Simulink commands
• Benchmark commands such as tic, toc, flops, clock, pause
• error, clear, persistent

About named visibility periods

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:

• Darkness - You can't see the code or scores for any of the entries.
• Twilight - You can see scores but no code.
• Daylight - You can see scores and code for all entries.
• Finish - Contest end time.


Download Sample Code