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)
