Sunday 7 February 2010

Sudoku solver in Python (part one)

I enjoy playing around with programming. Python is a good language for ease of use and built in features and readability. I'd like to see more type safety, though - Python won't complain if you try sending a list to something expecting a number. It will just crash, instead. (In contrast, C and C++ will give compiler errors before trying to run).

In any case, solving a sudoku is a fairly interesting task to tackle. Partly because there are many ways to try. I could, for example, use strictly logical methods as I would with a pen and paper. While it would easily be possible to to this, listing every method and working out exactly how to do this is a daunting task.

The other method is brute-force. Try every number in every square and see which one fits.

In this case, the solution lies somewhere between the two. The brute force solution, for a 3 x 3 grid has 60 empty squares, with a possible total of 9 values in each. This gives a total of around 1,797,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000 possibilities. A computer able to check a trillion possibilities every second wouldn't even scratch the surface on trying all of them if it ran from the start of the Universe to now!

So we use logical rules to narrow these down.

Let us start by creating an object that represents a Sudoku grid.


class Sudokugrid:
  def __init__(self,major_boxes):
    self.order = major_boxes
    self.size = self.order*self.order
    self.magnitude = self.order*self.order*self.order
    self.grid = []
    for column in range(self.size):
      row = []
      for box in range(self.size):
        row.append(0)
        self.grid.append(copy.deepcopy(row))
    self.conversion = " 1234567890ABCDEFGHIJKLMNOPQRTUVWXYZabcdefghijklmnopqrtuvwxyz@#"
    self.errorbox = "!"
    self.boxhighlight = "*"
    self.stepthrough = None


There are variants on Sudoku. Normally we see 9 x 9, but 16 x 16 and 4 x 4 variants are also occasionally seen. I tend to refer to this as the "order" of the puzzle. A 16 x 16 puzzle has 4 groups of 4 boxes each, and so is order 4. The standard puzzle is of order 3. This __init__ function creates a grid by making a list of lists. This allows any box to be accessed via self.grid[column][row].

The "conversion" variable is used for displaying on screen. 16 x 16 puzzles use letters to avoid having to use multidigit numbers. As it happens, I want to write using numbers throughout (it's safer that way, I believe, and I can use the number 0 to indicate an empty box), but display using letters and numbers. The conversion has enough characters for an eighth order grid.


Now we have a grid, and we assign values to it. We can start building our solver.

No comments:

Post a Comment