Sudoku Puzzle Generating, Pragmatic Way

Couple of days ago I described how you could generate a good random sudoku field, today I'm going to advocate for just opposite thing. There's no controversy in really, just there are different cases, when you should and when you should not do that.

You should or could write your own sudoku puzzles generator if you are particularly interested in the field and ready to spend lots and lots of time, getting deep in all the various rules which actually make a good sudoku. Well at least it will keep your self-esteem up.

But if you are just writing some implementation of the sudoku game, you actually better not to do that. And here is why.

• Sudoku generating is a random process with generally unpredictable duration. There is a good chance that your generator will get unlucky and stuck. And a hanging over application is the last thing you want your user to see.
  
• The process of generating of a really good, hard sudoku usually takes time, sometimes a few seconds
  
• There are lots of rules you need to get into, implement test over, and then if you are not an expert in sudoku you wont be able to check it out if you have done everything properly
  
• You will probably forget and never use again all the knowledge you gain during the implementation. I don't want to call it a waste of time, but I'm pretty sure there are better ways to actually waste your time.
  
• A good sudoku generator might be quite big and complicated piece of software, which will be hard to test and support.
  

Luckily there are better ways to do that. Use other people's work to be precise. There are lots and lots of online sudoku generators, or you could use any desktop applications, most of them cache boards in files. I used the gnome-sudoku application, it lets you generate any number of sudoku and saves them in the files in the gnome configuration directory, or you can grab my archive right here puzzles.zip

What about the number of puzzles ask you? You need some storage to keep them and have big enough collection to keep the user happy.

Actually not, and here is the trick of the article. You actually can keep just a few puzzles for each level and then generate new puzzles out of the originals. You can safely do the following things with your puzzles

• Rotate them
  
• Flip in any way
  
• Randomly shuffle rows and columns inside the 3x3 boxes
  
• Shuffle rows and columns of the 3x3 boxes
  

As the result, if you say have initially a collection out of 16 puzzles, then you can rotate and flip it in 5 ways, then you can shuffle rows and columns in 9 ways in each of the nine 3x3 boxes, and eventually you can have 9 combinations of the 3x3 blocks.

16 * 5 * 9 * 9 * 9 = 58320

That's more than enough for your user never see the same puzzle twice in a row. More of that, all of those puzzles will be really consistent by the difficulty level because initially it is just the same puzzle.

And for the end you can see a possible JavaScript implementation right here boards.js

This is pretty much it. Have a good one!

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]);
        }
      }
    }
  }
....

How Not To Create Rails Plugin

Another day I needed to handle some task which included communication with a SPARQL service. Quick google search gave me a reference to the ActiveRDF project, which claims to be the thing for ruby and rails.

But the thing is that the darn thing ain't work. As the matter of fact, you won't be able even run the example from the official site. I'm not complying, used the python sparql-wrapper to accomplish the task, but this project is a good example how you should not create a Rails plugin.

And here some tips and lessons you can learn out of it.

1. Location and Versioning Control System

The project was started at the https://launchpad.net service, under the bazaar versioning control system. That's probably a progressive thinking, but still a big mistake.

All the Rails crowd currently, more or less lives on git and github. The reason is obvious, all the people in one place, it is easy to participate in the projects using quick forking and merging. No need to register and set up your account. You do it once and have them all.

I had some experience with launchpad, it's a pretty good system, and if I would start some specific project for Ubuntu, I would probably thought about launchpad, but for Rails related project, if you want the people to participate you should go to github.

2. Implementation

The implementation as well a good example how not to write ruby code.

First of all when you creating an actual plugin or gem, global classes is the last thing which you should do. There should be the only one global name and this is the name of your project. All the rest of the things should be under the namespace.

The second is the API and what the users need to write in order to make it working in their application. With such a beautiful and powerful language as Ruby is, it is quite a shame to make people call the factory method directly. None of the actual rails part do that. There so much opportunities for all the meta-programming magic and you end up calling classes creation manually.

They should do it simultaneously to the existing things, like ActiveRecord or ActiveResource. As the matter of fact they probably should not start a standalone project in the first place and create some extension for the ActiveRecource project, they might make it to the rails codebase and that's huge. Much better than having another rails plugin.

But anyway, with a badly structured project, even if someone would like to participate and help it, that would be really hard and usually almost impossible to change anything, because there are already people who use the project as is, and people don't like to update their application code.


3. Support

I don't think I should mention such basic things, that when you have year and a half old bugs in your bug-tracker, even bugs where people already posted solutions and patches and you still didn't fix the problem, that's quite suck. As well as I should not mention such simple thing like keeping your code actually working, at least with the examples you have got on the front page.

The thing is that despite the fact that you are creating an open-source project and by the license you are not responsible for anything, you actually creating a project for people. Yes I know 90% of OOS just show-off projects by rookies just out of the university. But if you want the people to take you seriously you should support your projects.

Even if you don't want to work on the project anymore and there are no one else, you probably should say something, like "sorry guys the thing didn't fly and I have better things to do". Yes that suck, but that's understandable, and responsible.

If you didn't do that, people will still come and kill their time with your buggy code and will be left pretty much alone. You should warn your customers about such things, because everyone has different situations, someone probably would be happy to spend some hours to make a dead thing walking, but someone might be on a deadline and would expect your project actually working and probably would switch to something else if was warned.


The End

So the thing is simple. Bad location, bad implementation and bad support. This is more than enough to kill almost any project in any area. Think about it when you start your own.

RightJS The First Public Version

After months and months of hesitations and struggling against my own perfectionistic habits I've eventually released the first version of my javascript library called RightJS.

Basically it's the fastest and compactest JavaScript framework at the day. And the coolest one too. Sure.

Well... Whatever. I wish the thing a long happy live and lots of ass-kicking experience.

Amen.

http://rightjs.org

Dynamic IFrames As Form Targets

Sometimes you need to submit a form through some hidden iframe, usually when you're trying to monkey an ajax request for a file uploading.

Usually you just render an iframe element along with the form in the html code and assign the target attribute of the form. Something like this

<form target="my-iframe">.....</form>
<iframe name="my-iframe"></iframe>

It works, but in cases when you try do the same thing dynamically with javascript. Say to wire some additional fancy callbacks or something. Say like that.

var iframe = document.createElement('iframe');
document.body.appendChild(iframe);
iframe.id = iframe.name = 'my-iframe';
window['my-iframe'].onload = function() {...};

var form = document.getElementById('my-form');
form.target = iframe.id;
form.submit();

This thing looks generally correct, but unfortunately won't work.

I'm not sure why, but I do know the way how to deal with it.

The trick is simple, dirty and cross-browsing. Just how we like it.

var div = document.createElement('div');
document.body.appendChild(div);
div.innerHTML = '<iframe id="my-iframe" name="my-iframe"></iframe>';
var iframe = document.getElementById('my-iframe');
iframe.addEventListener('load', function() {....}, false);
// or for IE
iframe.attachEvent('onload', function() {....});

var form = document.getElementById('my-form');
form.target = iframe.id;
form.submit();

This thing is perfectly works in all the modern browsers and old IEs.

And for the end, there is even better way. Try the new RightJS framework. Then the same thing will look like this.

$('my-form').send();

This is pretty much it. Have a good one.

Filenames Encoding Conversion Under Linux

If you need to mass-convert filenames from one encoding to another, say you are migrating from one distro to another and need to move the legacy data, you can do that with the convmv util.

# apt-get install convmv
# convmv -f cp1251 -t utf8 -r --notest /dir/name

Integers To Binary Or Hex Conversion In Ruby

There are some tips on how you convert integers to binary or hex numbers forth and backwards.

irb(main):019:0> 30.to_s(2)
=> "11110"
irb(main):020:0> 30.to_s(10)
=> "30"
irb(main):021:0> 30.to_s(16)
=> "1e"

irb(main):027:0> '11110'.to_i(2)
=> 30
irb(main):028:0> '30'.to_i(10)
=> 30
irb(main):029:0> '1e'.to_i(16)
=> 30