Sudoku

I'm sort of in between projects right now. I finished my first project last week. The next one won't start till late this week. So to while the time away, I alternated between reading about C++ or Python and played sudoku. Yesterday I thought, "Hey why not try to create sudoku puzzles?" I know, it's been done before. But it's been a while now since I've written anything in Python, so there I go -- no cheat sheets from the Internet!

Okay, for those who don't know what sudoku is, the rule is simple. You have a 9x9 matrix board (similar to a crossword puzzle). Then you have 9 unique characters (normally numbers 1-9). You have to fill each position with a character, with the condition that each character is unique in the row, column, and 3x3 submatrix to which it belongs.

Obviously we'll have create a function that fills the board with the unique characters (we'll use numbers 1-9). Off the top of my head, we'll need a list of lists to represent the rows of the matrix and fill these rows with randomly selected numbers. For each row we provide the list of entries 1-9 that we can reduce according to the which numbers are already present in that row, column and 3x3 submatrix.

import random

def fill_board(board):
   "Fill the sudoku board."
   bsize = 9
   gsize = 3
   # initialize ...

Anticipating that this function will have to be called over several iterations, we'll initialize each row and submatrix according to the current contents of the (incomplete) board, resetting the incomplete rows to contain a character that we don't use in the game (here, -1).

   # initialize
   rows = board
   subs = [ [] for i in range(bsize) ]
   if len(rows) == bsize and len(rows[0]) == bsize:
       # board already has some valid rows
       for irow in range(bsize):
           if -1 in rows[irow]:
               # reset incomplete rows
               rows[irow] = [-1 for j in range(bsize)]
               continue
           # copy existing (incomplete) submatrices
           for icol in range(bsize):
               isub = (irow//gsize) * gsize + (icol//gsize)
               subs[isub].append(rows[irow][icol])
   else:
       # initialize an empty board
       rows = [ [-1 for j in range(bsize)] for i in range(bsize) ]

Now we can complete the of the board:

   # complete the board
   for irow in range(bsize):
       if -1 not in rows[irow]:
           # skip a completed row
           continue
       else:
           # reset an incomplete row
           rows[irow] = [-1 for j in range(bsize)]

       entries = range(1,1+bsize)

       # create a list of possible entries to this row
       for icol in range(bsize):

           # determine to which submatrix the current entry belongs
           isub = (irow//gsize) * gsize + (icol//gsize)
           sub = subs[isub]

           # get the current column
           col = [ r[icol] for r in rows ]

           # get the possible choice of entries
           choices = [ e for e in entries if e not in sub and e not in col ]

           # pick a possible entry
           if len(choices) < 1:
                continue
           pick = random.sample(choices, 1)[0]

           # record the new entry
           rows[irow][icol] = pick
           subs[isub].append(pick)

           # remove it from the list of possible entries
           entries.remove(pick)

   # return the board
   return rows

Thanks to Python's list comprehension feature, we can easily retrieve each column (see col = [...]) and the list of remaining valid characters (see choices = [...]) in just single lines. The new entry is then simply picked randomly afterwards.

As we've said earlier, using fill_board(board) just once could give an incomplete board, that is, some entries are still using the invalid character (-1). We therefore have to call this function several times.

def iterate_fill():
   "A helper method to generate the board within a few attempts."
   board = fill_board( [] )
   counter = 0
   limit = 25
   while not is_board_filled(board):
       if counter > limit:
           break
       board = fill_board( board )
       counter = counter + 1
   else:
       return [True, board]

   return [False, board]

def is_board_filled(board):
   "Check if board is completely filled."
   for row in board:
       if -1 in row:
           return False
   return True

Note that we have to put a limit on the number of iterations as we can end up with incomplete rows that just won't fit with the rest of the board. It'd be better (quicker) in that case to just discard the whole board and start from scratch altogether. So we go back from the beginning until we finally get a complete sudoku matrix. Here's the function to do that and display (rather primitively) the output.

def generate():
   "Call this function to produce the Sudoku board."
   done, board = iterate_fill()

   while not done:
       done,board = iterate_fill()

   for r in board:
       print r

We can then save these functions in a module, say sudoku.py. To use it from within a Python session.

import sudoku
sudoku.generate()

The output will look like this:

[3, 7, 4, 1, 5, 8, 6, 9, 2]
[2, 6, 5, 9, 3, 4, 7, 1, 8]
[9, 8, 1, 6, 2, 7, 4, 3, 5]
[5, 9, 6, 2, 8, 1, 3, 7, 4]
[4, 1, 7, 3, 6, 5, 2, 8, 9]
[8, 3, 2, 7, 4, 9, 5, 6, 1]
[7, 5, 9, 4, 1, 3, 8, 2, 6]
[1, 2, 8, 5, 7, 6, 9, 4, 3]
[6, 4, 3, 8, 9, 2, 1, 5, 7]

The next step is hopefully straightforward. According to the desired level of difficulty, we can hide a certain number of entries in this board from the player. We could then add some fancy user interface, and so on. Maybe I could write more about it in the future. But this is all for now. Salut!

-- Allister (http://cxxpython.blogspot.com)