Sudoku Solver in Python part 3

Previous post here

I continued my try to solve Sudoku with Python. Actually I have never solve a Sudoku puzzle myself

Here is the updated code

 python | 
  |
?
 
001
# -*- coding: utf-8 -*-
002
"""
003
Created on Wed Aug 11 18:22:44 2011
004
 
005
@author: gkomninos
006
"""
007
from Position import Position
008
 
009
class Puzzle(object):
010
    errors_number = 0
011
    '''A Sudoku puzzle'''
012
    def __init__(self):
013
        w, h = 9, 9
014
        self.Positions = [ [None]*w for i in range(h) ]
015
 
016
    def write_to_file(self, filepath):
017
        '''writes the puzzle to a file'''
018
        puzzlefile = open(filepath,'w')
019
        puzzlefile.write(self.to_string())
020
        puzzlefile.close()
021
 
022
    def load_from_file(self, filepath):
023
        '''Loads a Sudoku puzzle from a file'''
024
        puzzlefile = open(filepath)
025
        lines = puzzlefile.readlines()
026
        puzzlefile.close()
027
        row = 0
028
        column = 0
029
        for line in lines:
030
            line_data = line.split()
031
            column = 0
032
            for data in line_data:
033
                if(data == 'x'):
034
                    tmp = Position(row, column, data, False)
035
                else:
036
                    tmp = Position(row, column, data, True)
037
                self.Positions[row][column] = tmp
038
                column += 1
039
            row += 1
040
 
041
    def to_string(self):
042
        '''returns the puzzle as a string'''
043
        out = ''
044
        for row in range(9):
045
            for column in range(9):
046
                out += self.Positions[row][column].to_string()
047
                if(column != 8):
048
                    out += ' '
049
            out += '\n'
050
        return out
051
 
052
    def random_fill(self):
053
        '''Completes the puzzle with "random" numbers'''
054
        for row in range(9):
055
            fixed = [int(cell.Value) for cell in self.Positions[row]
056
                         if cell.Value != 'x' and cell.Fixed == True ]
057
            candidates = [ i for i in range(1,10) if i not in fixed ]
058
            for column in range(9):
059
                if(self.Positions[row][column].Fixed):
060
                    continue
061
                tmp_cell = Position(row, column, str(candidates.pop()))
062
                if not self.is_valid(tmp_cell):
063
                    tmp_cell.Valid = False
064
                    self.errors_number += 1
065
                self.Positions[row][column] = tmp_cell
066
 
067
    def count_errors(self):
068
        '''counts the errors in the puzzle'''
069
        pass
070
 
071
    def is_valid(self, cell):
072
        '''checks if putting the number_to_insert in cell is valid'''
073
        #out = 'checking ('+str(cell.Row)+','+str(cell.Column)+') => '        
074
        if cell.Value == 'x' or cell.Fixed:
075
            return True
076
        #check if number_to_insert allowed in column
077
        if int(cell.Value) not in self.get_column_allowed_numbers(cell.Column):       
078
            return False
079
        if int(cell.Value) not in self.get_box_allowed_numbers(cell.Box):
080
            return False
081
        if int(cell.Value) not in self.get_row_allowed_numbers(cell.Row):         
082
            return False
083
        return True
084
 
085
    def get_column_allowed_numbers(self, column):
086
        '''returns a list of  the numbers which allowed in column'''
087
        column_list = [ int(self.Positions[i][column].Value) for i in range(9)\
088
                        if str(self.Positions[i][column].Value) != 'x']
089
        return [ i for i in range(1,10) if i not in column_list ]
090
 
091
    def get_row_allowed_numbers(self, row):
092
        '''returns a list of the numbers which allowed in the row'''
093
        row_list = [ int(self.Positions[row][i].Value) for i in range(9)\
094
                    if str(self.Positions[row][i].Value) != 'x']
095
        return [ i for i in range(1,10) if i not in row_list]
096
 
097
    def get_box_allowed_numbers(self, box):
098
        '''returns a list of the numbers which allowed in the box'''
099
        box_list = [ int(self.Positions[i][j].Value) for i in range(9) \
100
                    for j in range(9) \
101
                    if self.Positions[i][j].Box == box and \
102
                       str(self.Positions[i][j].Value) != 'x']
103
        return [ i for i in range(1,10) if i not in box_list]
104
 
105
 
106
    

 python | 
  |
?
 
01
# -*- coding: utf-8 -*-
02
"""
03
Created on Wed Aug 11 18:21:28 2011
04
 
05
@author: gkomninos
06
"""
07
 
08
class Position(object):
09
    '''A Sudoku cell '''
10
    def __init__(self, row, column, value='x', fixed = False):
11
        '''Constructor like'''
12
        self.Row = row
13
        self.Column = column
14
        self.Box = self.__calc_box()
15
        self.Value = value
16
        self.Fixed = fixed
17
        self.Valid = True
18
 
19
    def __calc_box(self):
20
        '''calculates in which "box" the cell belongs'''
21
        if self.Row >= 0 and self.Row <= 2 and \
22
           self.Column >= 0 and self.Column <= 2:
23
            return 0
24
        elif self.Row >= 0 and self.Row <= 2 and \
25
             self.Column >= 3 and self.Column <=5:
26
            return 1
27
        elif self.Row >= 0 and self.Row <= 2 and \
28
             self.Column >= 6 and self.Column <= 8:
29
            return 2
30
        elif self.Row >= 3 and self.Row <= 5 and \
31
             self.Column >= 0 and self.Column <= 2:
32
            return 3
33
        elif self.Row >= 3 and self.Row <= 5 and \
34
             self.Column >= 3 and self.Column <= 5:
35
            return 4
36
        elif self.Row >= 3 and self.Row <= 5 and \
37
             self.Column >= 6 and self.Column <= 8: 
38
            return 5
39
        elif self.Row >= 6 and self.Row <= 8 and \
40
             self.Column >= 0 and self.Column <= 2: 
41
            return 6  
42
        elif self.Row >= 6 and self.Row <= 8 and \
43
             self.Column >= 3 and self.Column <= 5: 
44
            return 7
45
        elif self.Row >= 6 and self.Row <= 8 and \
46
             self.Column >= 6 and self.Column <= 8: 
47
            return 8        
48
        return -1
49
 
50
    def to_string(self):
51
        '''returns the value of a Position object'''
52
        return self.Value
53
 
54
    def swap(self, other_object):
55
        '''Swaps two cells'''
56
 
57
#        print 'swapping : ('+str(self.Row)+','+str(self.Column)+')=>('+\
58
#                str(other_object.Row)+','+str(other_object.Column)+')'
59
        if(self.Fixed == True or other_object.Fixed == True):
60
            return False
61
 
62
        tmp_row = self.Row
63
        tmp_column = self.Column
64
        tmp_box = self.Box
65
        tmp_value = self.Value
66
 
67
        self.Row = other_object.Row
68
        self.Column = other_object.Column
69
        self.Box = other_object.Box
70
        self.Value = other_object.Value
71
 
72
        other_object.Row = tmp_row
73
        other_object.Column = tmp_column
74
        other_object.Box = tmp_box
75
        other_object.Value = tmp_value
76
 
77
        return True
78
 
79
 
80
    if __name__ == "__main__":
81
        print 'Position object'

As you can see I added the function random_fill. This functions fills the empty cells with almost random numbers.
I say almost because in each row I add only the numbers they are allowed. But not in the right order.
Then I check if the Value is valid and I keep track of the errors.

The next step is to try to find a way to eliminate the errors by swapping the numbers.
I will try this now and I will post the results. The possibility to go back to correct a mistake or even change the logic at all are very high. But that is the meaning…learning python by becoming smarter.
To be continued

UPDATE

And yes I am right I have mistakes! But I do not give up…I will start from scratch tomorrow or later at night maybe.
Now it’s time to enjoy the sunset with the company of a souvlaki ( maybe 2 ).