Extreme Sudoku Solving with Ruby


This is a talk I gave at last night’s Ask Later event (formerly known as Techa Kucha) in London. As per the house rules of the night, the format was 20 slides, 20 seconds per slide; in those six-and-two-thirds minutes, I told the tale of my attempt to wangle free booze from the Rupert Murdoch empire with a bit of help from a worldwide puzzle phenomenon, some home-spun OCR algorithms and a most excellent programming language from Japan.

Extreme Sudoku Solving – slides (328K, PDF)

Unfortunately the slides don’t have an awful lot of text on them, so you’ll have to do a lot of the storytelling yourself until I get chance to do a proper write-up…

7 Responses to “Extreme Sudoku Solving with Ruby”

  1. icabod says:

    Dude, you’re wierd.

    Clever. Extremely clever. Everso extremely clever. Incredibly everso extremely clever.

    But wierd ;)

  2. icabod says:

    Of course I mean that in a nice way.
    I’m actually interested in the OCR technique as I was looking at doing some simple OCR from an image a little while back. The tricky bit for what I was looking at was that the background was semi-random, as the text was essentially shown over a moving image. Makes life tricky.

    I look forware to your write-up.

  3. poke says:

    Hi Mathew.
    Nice article. Try imagine your digit bitmap like a 2D probability function. For OCR you can use high probability central moments (variance, skewness, kurtosis) and not only first moment.
    Calculate this moments for your unknown bitmap and compare with moments of typical digit bitmap. It’s basic example of machine learning and image processing. :-)

    More about moments you can see here: http://en.wikipedia.org/wiki/Moment_%28mathematics%29

    Caio,
    Poke

  4. Dan says:

    Hi Mathew,

    Loving this example. I am a big Ruby user and I would like to utilize your the OCR code from your example. I don’t really understand how your are coming back with the “Error” figure, I can see there is a diff which produces this results but I am not sure which two images should be diffed in this fashion.

    Any help would be greatly appreciated.

    Cheers

    Dan

  5. matt says:

    Hi Dan,
    The idea is that you prepare a set of known ‘specimen’ images in advance of running the program, and apply the same preprocessing steps to those. Then, for each square in the grid, you do the pixel-by-pixel diff against each specimen image in turn, and select the one with the smallest difference. (In my case I also calculated a rough margin of error by comparing that figure with the next best one.)

    I’ve put the complete OCR portion of the code here: http://matt.west.co.tt/files/ocr_example.rb

  6. gee says:

    hi.. can you help me.. how to calculate checksums of ocr code at wafer..
    if you know..mail me pls..

  7. huogang says:

    use imagemagick to convert the image to a pgm file then use `gocr -i file.pgm` to get the ocr text from the command line tool inside of ruby.

Leave a Reply