Introduction:

After reading through newspapers almost everyday on the train, I started trying to solve sudoku puzzles. Numerous weeks later I still have little success at solving them in the limited time I have on the train. If I get really close to the end of a game, I still want to know where I went wrong. So here it is; the beginning of a sudoku solver.....



Basic Knowledge:

  • First of all, I'm using python 2.6 so if you don't have it installed, you may need to install it and learn some basic syntax...
Notes:

  • When i refer to choices throughout the text, I mean the possible choices a square can take. For example, if a line contains 1 through 8... the only choice for the last square is 9
Saved Sudoku Game Structure:

As you would already know, a Sudoku game consists of 81 squares (9x9). The most simplest way to input a sudoku game would be to load it from a text file written by the user (this can be improved with a GUI later so the user can click a square and input a number). The structure of the text file will go character space character space character...... After a row is complete, a new row is started by a new line. An example of the file structure will be downloadable once the script is complete.

The Problem:

What functions do we need to write in order to solve the problem?
  • A function to read a game file (saved on file by user)
  • A function to get all the possible choices of a current square in the game (other functions supporting this function?)
  • A main function (controls and calls all other functions) known as the controller
  • A function to print the game when solved
  • A function that will check if the game is solvable with the current selection
  • A function that will reverse and change the previous input if game is unsolvable

The most basic way to solve this problem would be in a tree like structure. The program will input the first choice in the first possible square. It will work through the game column by column, row by row. If the game is unsolvable it will backtrack up the tree and change the square to another possible choice. If there is no other possible choice, it will keep backtracking until there is. The program will have to do thousands of calculations. However, because of the small size of a soduku game, the average game will be solved in a few seconds. Heres a simple picture I drew up to help you visualize what I want the program to do (don't laugh)....


The Fun Part:

NOTE: You will need to indent the code yourself... I cbb going through the html and manually entering spaces atm.

The basic theory is out of the way so lets start the programing.

First we need a function that will convert a given row into a list of its components:

def convertrow(rstr):
row = []
for i in range(0, 18, 2):
row.append(rstr[i])
return row

Notes: range(0, 18, 2) will skip the spaces in the row string (rstr). So range(0, 18, 2) will return 0,2,4,6,8....

Now for the read game function... we will call it read_game

def read_game(filename):
f = open(filename, 'U')
game = []
for line in f:
game.append(convertrow(line))
f.close()
return game

The function opens the file and puts the contents into the variable 'f'. It then reads each line of 'f' and adds each line as separate elements to the list named 'game'. We then close the file and return the list.

Now we need functions to get a specific block (group of 9 square's, 3x3.... you should know what I'm talking about if you have ever player sudoku), row and column .

The simplest is get row...

def get_row(r, game):
return game[r]

Now get column...

def get_column(c, game):
column = []
for r in game:
column.append(r[c])
return column

Now get block...

def get_block(r, c, game):
block = []
for row in range(3*r, 3*r+3):
block.extend(game[row][3*c:3*c+3])
return block

I think you should all understand the above three functions if you have basic python knowledge.

Now we need a function to get the numbers that are contained within two rows or columns. We also need a function that will return the number(s) contained in a row or column that are not in another row or column.

So...

def list_dif(list1, list2):
difnums = []
for i in list1:
if not i in list2:
difnums.append(i)
return difnums

and....

def list_same(list1, list2):
same = []
for i in list1:
if i in list2:
same.append(i)
return same

Again, these functions are pretty strait forward.

Now for the choices function. Basically the function must return all the possible choices that are possible at (r,c). Each choice should not occur in row r, column c or in the block containing this position. It is a bit confusing at first. Basically its a controlling function for all the above functions...

def choices(r, c, game):
all_choices = ['1', '2', '3', '4', '5', '6', '7', '8', '9']
blockrow = r / 3
blockcol = c / 3

row_choices = list_dif(all_choices, get_row(r, game))
col_choices = list_dif(all_choices, get_column(c, game))

block_choices = list_dif(all_choices, get_block(blockrow, blockcol, game))

fchoices = list_same(row_choices, col_choices)
fchoices = list_same(choices, block_choices)

return fchoices

In my opinion, the hardest part is over, the basic structure is complete. I will post the rest of the script tomorrow. Stay Subscribed.