Sudoku Random Field Generator

The task is simple, to fill up a 9x9 field by the sudoku game rules.

Generally it's not a rocket science and there are lots of simple solutions. For example filling up the field with shifted sequences. Say you have a sequence of numbers from 1 to 9, then you might generate a valid field like that.

1 2 3  4 5 6  7 8 9
4 5 6  7 8 9  1 2 3
7 8 9  1 2 3  4 5 6

2 3 4  5 6 7  8 9 1
5 6 7  8 9 1  2 3 4
8 9 1  2 3 4  5 6 7

3 4 5  6 7 8  9 1 2
6 7 8  9 1 2  3 4 5
9 1 2  3 4 5  6 7 8

As you see, the principle is simple, you start with your basic sequence, and then shift it by 3 positions inside 3x3 box, and by one position between the levels. The principle will still work if you start with any randomly sorted sequence of unique numbers.

3 5 6  2 7 4  1 9 8
2 7 4  1 9 8  3 5 6
1 9 8  3 5 6  2 7 4

5 6 2  7 4 1  9 8 3
7 4 1  9 8 3  5 6 2
9 8 3  5 6 2  7 4 1

6 2 7  4 1 9  8 3 5
4 1 9  8 3 5  6 2 7
8 3 5  6 2 7  4 1 9

After that you might shuffle columns and rows in scope of boxes to make the field more random, you even might shuffle the 3x3 rows and columns as well to have even better results.

But this thing is not really serious and kinda boring. The problem is that all your numbers are grouped by three numbers and those groups in different orders will appear all over the field. And this might be used for cheating. Say you open one of the sequences 4 1 9 and then wherever you open any of those three numbers you immediately know the numbers next to it.

Well for smarty pants like you and me, we need something different, something bigger, better and more bad ass.

After several coups of coffee I've come to the following algorithm.

1. We generate our field row by row
2. For each cell in a row, depends on the other existing numbers in the 3x3 box or the column, we generate a list of options
3. Out of the list of options for each cell we randomly select a value
3.1 When we convert a list of the options into a row we watch for intersections with other options and choose the most optimal collection

For example we have the following thing

1 5 6  9 8 7  4 3 2
9 2 3  4 6 5  8 7 1
8 7 4  3 1 2  6 9 5

4 9 7  6 3 1  5 2 8
5 3 2  7 4 8  1 6 9
? ? ?  ? ? ?  ? ? ?
----------------------
The options will be following

6 1 1  2 2 9  3 4 3
  6 8  5 5    7   4
  8      9        7

----------------------
Out of the options we might create sequences

6 1 8  2 5 9  7 4 3 
6 8 1  5 2 9  4 7 3
......

This way we will have no patterns and truly random valid sudoku field.

The only problem is that it is not exactly working.

As it's a random process, for each valid field there will be about 5-10 cases when there will be no ability to create a correct sequence. But despite the "not exactly" prefix, the algorithm is actually working and creates beautiful truly random fields.

And then you have a choice. Think about the algorithm by yourself and try to make it work every time, or you can make your computer think through the algorithm several times until a fully covered field will pop up.

Yes, I know, for a piece of software it sounds cheesy, but in reality there are not much calculations in the algorithm and make it running 5-10 times is not a big deal, it takes just a few milliseconds in javascript. Besides, if you need a speed, you can always cache the fields and shuffle them later as you shuffle the fields generated by patterns.

And for the grand finale here is a possible solution in JavaScript + RightJS

....
  // generates randomly distributed field
  generateGrid: function() {
    var numbers = '123456789'.split('').map('toInt');
    var matrix  = numbers.map(function() { return []; });
    
    for (var x=0; x < 9; x++) {
      var options = [];
      
      for (var y=0; y < 9; y++) {
        var col_numbers = numbers.map(function(i) { return matrix[i-1][y]; });
        var box_numbers = numbers.map(function(i) {
          var box_x = (x/3).floor() * 3 + ((i-1) % 3);
          var box_y = (y/3).floor() * 3 + ((i-1)/3).floor();
          
          return matrix[box_x][box_y];
        });
        
        options.push(numbers.without.apply(numbers, col_numbers.concat(box_numbers)));
      }
      
      matrix[x] = this.sequenceFromOptions(options);
      
      // drop and start over if there sequence was damaged
      if (matrix[x].compact().length < 9)
        return this.generateGrid();
    }
    
    return matrix;
  },
  
  sequenceFromOptions: function(options) {
    for (var i=0; i < 9; i++) {
      this.cleanOptions(options);
      
      options[i] = [options[i].random()];
      for (var j=i+1; j < 9; j++) {
        options[j] = options[j].without(options[i][0]);
      }
    }
    
    return options.map('first');
  },
  
  cleanOptions: function(options) {
    for (var i=0; i < 9; i++) {
      if (options[i].length == 1) {
        for (var j=0; j < 9; j++) {
          options[j] = options[j].length == 1 ? options[j] : options[j].without(options[i][0]);
        }
      }
    }
  }
....