sudoku in OO Perl

introduction

In the 1990s I suspected object-oriented programing was a fad or a technique for niches like windowing systems. There were articles (both serious and less so) stating this. [1] I'd seen (and done) successful programs with no OO features written in languages with no OO features; so how important could it really be?

Even the OO section at the end of Programming Perl [2] had an uncanny resemblance to the story about the toaster.

During the next decade it became clear that OO wasn't a mere fad and I thought the time was coming when I should learn about it. Besides it features in the object capability model [3] [4] [5] .

how to get to Carnegie Hall

As a practice problem (larger then a typical textbook example but small enough to focus on the essentials) I picked writing a sudoku [6] puzzle solver in OO Perl.

Features of this solver not found in the many others online are:

It uses similar logic to what I do mentally to minimise the use of guessing. The speed is reasonable for Perl; but slow compared to C++.

the program

See it on github [7] but here I'm writing about how it was done.

There needs to be some representation of the state of the puzzle such as the cells having symbols in them (or being blank) and what is known about cell content but is not ready to commit to writing in the cell. There is unchanging geometry about which cells are sharing a set of symbols with which others. I coined the term "clot" for 9 related cells whether that's a row, a column or a block. The solver's treatment of them doesn't care very much which it is. This led me to classes "board, "clot","cell".

An argument "-a" is read if present. Either a file named on the command line or STDIN is read for the initial puzzle state. The size of the square (9x9 to 36x36) is discovered from that input.

As the OO part starts board->new() is called. Setup of the board includes defining the character set allowed in cells because that depends on the puzzle size. Other parts of the code need to be aware of this. set_cell($dig, "input provided") is used to write the initial state into the relevant cells.

The main program file enters a loop where it calls board methods "infer" (for logic) and "guess" and "unguess" until the termination conditions are met.

board->infer() calls clot->infer() on all clots not yet solved. clot->infer() has 3 logical ways of progressing the puzzle.

notdig() is the way of propagating negative knowledge around the puzzle - for instance if the first cell is 1 then all the other cells in the same 3 clots cannot be 1. clot->notdig() is called every time set_cell() sets a cell value not known before.

Guessing is done by making a whole new copy of the board and adjusting that (while keeping a path back to the earlier board for unguessing). This is where the languange with its attitude to objects and memory management affects what programming styles make sense.

I'd write something about profiling it but it's been written already. [8]

    perl -d:NYTProf ./solve.plx in
    nytprofhtml --open

footnotes

  1. OO parody
  2. Programming Perl (2ed)
  3. wikipedia
  4. erights
  5. Object Capabilites and Isolation of Untrusted Web Applications (PDF)
  6. wikipedia
  7. my sudoku_9_to_36 program at github
  8. NYTProf

Written by Peter M Allan. 2015
linkedin
back to articles