Had a few free hours and spent them on my Sudoku generator, and by now I have a nice little online Sudoku game

It now spits out nice symmetric Sudokus with a fairly mild difficulty level, and it times the solving of each puzzle.

I still have some more features in store (like better response from the check function), and I still need to slap up a little website around it, but its already great fun. Enjoy…

First a message to that one guy who added this blog to his RSS feeds: don’t worry it isn’t dead already, it’s owner was just away on some stressful vacation, had visitors, started on a new job and was celebrating his 30th birthday!

Then a message to whomever might read it: the next statement might seem to blatantly contradict the title of this post.

Ruby is really, really slow. While the benchmarks from the Computer Language Shootout might be misleading or biased or whatever, Ruby is so slow that from time to time you really don’t need a benchmark to notice it.

Solving Sudoku

With me on my vacation I had Donald E. Knuth’s paper about the Dancing Links algorithm. I wanted to use it to create my own little Sudoku generator in Ruby. Perhaps a geeky vacation activity, but if its fun solving a Sudoku, why shouldn’t it be fun solving Sudoku?

Knuth’s algorithm is really extremely beautiful. Implementing it gave me a bit of the same feeling as studying a Bach Fugue at the piano. What an amazing ability of abstract imagination Knuth must be in possession of!

Implementing the algorithm in Ruby didn’t make it any less beautiful, but it did make it seriously slow. The algorithm needs an initial matrix of circularly linked lists to be setup, before it can work its magic. To solve Sudoku this involves setting up a matrix of 3.241 linked Nodes. While 3.341 is generally a really small number for a computer, it’s a pretty big number for Ruby, and on my good, old, trusty iBook G4, setting up this matrix in Ruby takes time. Perhaps not a huge amount of time in the grand perspective of things, but enough time that a web-based Sudoku generator running on Ruby on Rails would feel slow.

Of course I could just try to hide the slow nature of the generator by some Ajax trickery, or I could generate a huge batch of Sudokus overnight and feed them to a database, but the first solution is a shoddy excuse for not just creating something that’s fast enough from the outset, and the other option was just not what I wanted for my own little online Sudoku generator.

More to Ruby than Ruby

So why am I still claiming in the title of this post, that Ruby is more than fast enough?

Because all this led me to discover how insanely easy it is to extend Ruby with C. And while C might lack objects, classes and all the niceties of a dynamic OOP language like Ruby, it sure has speed.

Programming Ruby: The Pragmatic Programmers Guide provides an excellent guide to extending Ruby in C, and with the help of this guide and the README.EXT file in the Ruby source directory, I was able to quickly create a Sudoku extension for Ruby.

I started out by creating a quick implementation of the Dancing Links algorithm in C. Since I had already implemented the algorithm once in Ruby, it was quite easy getting a command-line Sudoku solver up and running in C – this one just as blazingly fast as the Ruby version was slow. Now it was just a matter of including ruby.h, setting up a few interface functions, letting ruby generate a makefile for me and running “make” – and bam! – I had my Sudoku extension.

A Tiny Tutorial

Just to give you an idea how easy this whole process is, here’s a small tutorial on creating an incredibly useful “Hello World” extension to ruby:

First we make our “Hello world” C program in an empty folder:

hello_world.h:

#include <stdio.h>

void say_hello();

hello_world.c:

#include "hello_world.h" 

void say_hello() {
printf("Hello, World!\n");
}

int main() {
say_hello();
}

Compile and run to check that your new fantastic hello world program works.

Time to make it a Ruby extension. Remove the int main() function from hello_world.c and lets start interfacing. Here are the c files:

hw_extension.h:

#include "ruby.h" 
#include "hello_world.h"

hw_extension.c:

#include "hw_extension.h" 

VALUE cHello;

static VALUE h_init(VALUE self) {
return self;
}

static VALUE h_say_hello(VALUE self) {
say_hello();
return Qnil;
}

void Init_HelloWorld() {
cHello = rb_define_class("HelloWorld",rb_cObject);
rb_define_method(cHello, "initialize", h_init, 0);
rb_define_method(cHello, "say_hello", h_say_hello, 0);
}

The Init_HelloWorld() function is needed to define our new Ruby classes and methods. Our class is defined as “HelloWorld”, HelloWorld.initialize is set to the h_init function and HelloWorld.say_hello is set to our h_say_hello method.

Now we need to tell Ruby to create a makefile for us. For that purpose we make a config file:

extconf.rb:

require "mkmf" 

dir_config("HelloWorld")

create_makefile("HelloWorld")

Now run “ruby extconf.rb” and Ruby will search the directory for .c files and add them to the make files instructions. When that’s done all there’s left to do is type “make” at the command line and we’re good to go.

Fire up irb and lets test our new extension:

> require "HelloWorld" 
=> true
> h = HelloWorld.new
=> #<HelloWorld:0x1bafbc>
> h.say_hello
Hello, World!
=> nil

Y-ay! We now have a lighting fast hello world extension and all your worries about your hello world programs running way to slowly in Ruby should be a thing of the past! At least the excellent extendibility of Ruby made my worries about the speed of my Sudoku generator go away.

I put up the current Rails driven version of my Sudoku generator at sudoku.mathias-biilmann.net It currently generates very hardcore Sudokus with few hints and no testing to see if they are solvable without backtracking. But it works, it’s fast and I hope to get time to improve upon it during the months to come.

[Update – The Sudoko game is now far more enjoyable. It generates fairly easy aesthetically pleasing Sudokus, and let you challenge a friend to beat your time at any Sudoku you manage to solve.]