I just coded an object-oriented Sudoku solver, but I don't have any possibility to check whether I have written good code, so I thought I would just post it here for review. I have looked for other solutions online but they mostly use different approaches so it's hard for me to compare.
I'm just getting started and trying to learn how to write good and clean code, so any suggestions and criticism are welcome, including variable naming, documentation but also on the algorithm itself. Especially i would like to know if my approach is appropriate for such a problem and if there are Sudoku puzzles which could break my code. So far everything worked.
The idea is basically to solve it like a human would: look at a field, check what values are permitted and fill it in if there is only one possibility. The only difference is that the fields are checked linearly instead of looking for fields which may be easy to fill in. To check for possible values I look at rows, columns, and "blocks" separately. If all fields have been checked the loop restarts and hopefully more fields can be filled in during the next iteration. I keep track of everything by storing it in attributes of two classes: a "field" class with position and value and the "board" which is "composited" of 81 fields which are automatically set up when instantiating a board.
Here is my code:
import itertools
class Field:
"""A sudoku field which consists of
a value (default is 0 = empty),
position information given by row, column and block
a list of permitted values, which is to be filled later by a sudoku board method"""
def __init__(self, row, column):
self.value = 0
self.row = row
self.column = column
self.block = (row // 3) * 3 + column // 3
self.permitted_values = set([])
def __str__(self):
"""When printing print the value"""
return str(self.value)
class Board:
"""Sudoku board consisting of
an ordered list of field objects
dictionaries which link row/column/block number to the associated ordered list of field objects
a filled attributed which tracks how many fields are already filled, later used for breaking the solve loop"""
def __init__(self):
"""Sets up the sudoku board by instantiating 81 fields with default values 0 and creating the dictionaries"""
self.fields = []
self.rows = {i: [] for i in range(9)}
self.columns = {i: [] for i in range(9)}
self.blocks = {i: [] for i in range(9)}
self.filled = 0
for i, pos in enumerate(itertools.product(range(9), range(9))):
self.fields.append(Field(*pos))
self.rows[pos[0]].append(self.fields[i])
self.columns[pos[1]].append(self.fields[i])
self.blocks[self.fields[i].block].append(self.fields[i])
def check_possible(self, field):
"""For a given field checks which values are possible and updates the associated attribute"""
if field.value != 0:
return 0
forbidden_values = set([])
units = [self.rows[field.row], self.columns[field.column], self.blocks[field.block]]
for unit in units:
for unit_element in unit:
forbidden_values.add(unit_element.value)
field.permitted_values = set([i + 1 for i in range(9)]) - forbidden_values
def load_game(self, fields):
"""Loads a game which is given in as a list with 81 elements"""
for i, j in enumerate(fields):
self.fields[i].value = j
if j != 0:
self.filled += 1
def export_game(self):
"""Returns the current board setup as a list with 81 elements"""
return [self.fields[i].value for i in range(81)]
def print_board(self):
for i in range(9):
print(*self.rows[i])
def solve(self):
"""While not everything is filled in, loops over fields linearly an fills in the solution when one is found
If solved print out the solution"""
while self.filled < 81:
for field in self.fields:
self.check_possible(field)
if len(field.permitted_values) == 1:
field.value = list(field.permitted_values)[0]
self.filled += 1
print("Board solved!")
self.print_board()
def test_field(self, field_number):
"""Print out all information about a field by field number in .fields"""
print("Printing field {} information".format(field_number))
self.fields[field_number].info()
