sudoku_solver/sudoku_solver.py

# Sudoku: 9x9 Spielfeld. Auf jedem Feld ist eine Liste mit möglichen Werten.
# Enthält diese Liste nur einen Wert, ist das der gesuchte Wert für das Feld.

import logging
logging.basicConfig(level=logging.INFO) # change to DEBUG if needed

gamefield = [
    [[],[],[],      [5],[],[7],       [],[],[]],
    [[],[4],[],      [2],[6],[3],       [],[],[]],
    [[1],[],[7],      [4],[],[],       [],[],[]],
    
    [[3],[6],[],      [],[],[],       [],[4],[5]],
    [[],[],[2],      [],[5],[],       [7],[],[]],
    [[7],[9],[],      [],[],[],       [],[6],[2]],

    [[],[],[],      [],[],[9],       [4],[],[1]],
    [[],[],[],      [1],[3],[4],       [],[9],[]],
    [[],[],[],      [6],[],[5],       [],[],[]]
];

def fill_empty_fields_with_possible_values():
    logging.debug("fill_empty_fields_with_possible_values")
    y = 0
    for row in gamefield:
        x = 0
        for field in row:
            if(len(field) == 0):
                field = [1,2,3,4,5,6,7,8,9]
                row[x] = field
            x += 1
        gamefield[y] = row
        y += 1

def print_sudoku():
    print('')
    y = 0
    for row in gamefield:
        x = 0
        for field in row:
            if(len(field) == 1):
                print(field, end='')
            else:
                print('[ ]', end='')
            
            x += 1
            if(x > 0 and x < len(row) and x%3 == 0):
                print(" | ", end='')

        y += 1
        if(y > 0 and y < len(gamefield) and y%3 == 0):
            print('\n---------------------------------', end='')
        print('')
    print('')

def solve_sudoku():
    logging.debug("solve_sudoku")
    # always repeat everything from the beginning if something is found
    while True:
        if not solve_by_cell_check():
            continue
        if not solve_by_unit_check():
            continue
        # break when every algorithm runs through without any findings
        break

def solve_by_unit_check():
    '''checks each row/cell/3x3 if 1-9 is the only possible value for this unit'''
    logging.debug("solve_by_unit_check_inner")
    # check for each row. check for 1 to 9 if it is the only possible value for this unit. if yes, set. it and restart
    for row in gamefield:
        field_changed = False
        v = 1
        while True:
            count = 0
            foo_field = []
            for field in row:
                if v in field:
                    count += 1
                    foo_field = field
            if count == 1 and len(foo_field) > 1:
                foo_field.clear
                foo_field.append(v)
                field_changed = True
                break
            v += 1
            if v == 9:
                break
    
    # check for each column. check for 1 to 9 if it is the only possible value for this unit. if yes, set. it and restart
    # TODO
    # check for each 3x3 field. check for 1 to 9 if it is the only possible value for this unit. if yes, set. it and restart
    # TODO
    
    # return True when algorithm runs through without any findings
    # return False when algorithm found something
    return not field_changed

def solve_by_cell_check():
    '''checks each cell to remove possible values'''
    logging.debug("solve_by_cell_check_inner")
    # for each cell
    y = 0
    for row in gamefield:
        x = 0
        logging.debug(f"check at {x}/{y}")
        for field in row:
            # if value is already defined, check next value
            if(len(field) == 1):
                x += 1
                continue
            # for each possible value
            field_changed = False
            for possible_value in field[:]:
                logging.debug(f"check value {possible_value} in {field}")
                # check if the value already exists in row/column/3x3 field
                if(check_row_for_value(y, possible_value) or
                   check_column_for_value(x, possible_value) or 
                   check_3x3_for_value(x, y, possible_value)):
                    # if yes, remove it from possible values
                    remove_from_possible_values(x, y, possible_value)
                    field_changed = True
                    # if possible values for a field reaches 1 -> break
                    if(len(field) == 1):
                        break
            # return False because algorithm found something
            if field_changed:
                logging.debug(f"solve_by_cell_check_inner found something and changed field -> restart")
                return False
            x += 1
        y += 1
    # return True when algorithm runs through without any findings
    logging.debug(f"solve_by_cell_check_inner runs through without any findings")
    return True

def remove_from_possible_values(x, y, value):
    logging.debug(f"remove {value} from possible values at {x}/{y}")
    gamefield[y][x].remove(value)

# i do not explicitely skip the field itself because it is skipped by len check
def check_row_for_value(rowIndex, value):
    logging.debug(f"check row {rowIndex} for {value}")
    for field in gamefield[rowIndex]:
        if len(field) == 1:
            if field[0] == value:
                return True 
    return False

def check_column_for_value(columnIndex, value):
    logging.debug(f"check row {columnIndex} for {value}")
    rowIndex = 0
    while rowIndex < len(gamefield):
        field = get_field_by_coord(columnIndex, rowIndex)
        if len(field) == 1:
            if field[0] == value:
                return True 
        rowIndex += 1
    return False

def check_3x3_for_value(x, y, value):
    logging.debug(f"check 3x3 at {x}/{y} for {value}")
    (block_x, block_y) = get_3x3_start_coords(x, y)
    block_x_end = block_x + 2
    block_y_end = block_y + 2
    while block_y <= block_y_end:
        while block_x <= block_x_end:
            # check for each slot in 3x3 if there is already a fixed number (len == 1)
            field = get_field_by_coord(block_x, block_y)
            if len(field) == 1:
                if field[0] == value:
                    return True 
            block_x += 1
        block_y += 1
        block_x -= 3
    return False

def get_3x3_start_coords(x, y):
    while(x % 3 != 0):
        x -= 1
    while(y % 3 != 0):
        y -= 1
    return (x, y)

def get_field_by_coord(x, y):
    return gamefield[y][x]

def main():
    fill_empty_fields_with_possible_values()
    print_sudoku()
    solve_sudoku()
    print_sudoku()

main()