simple sudoku solver

 avatar
unknown
python
a year ago
6.1 kB
6
Indexable
def sudoku(puzzle):
    solved = False
    solved_blocks = [[0,0,0],
                     [0,0,0],
                     [0,0,0]]
    
    def check_if_solved():                                          # loops through solved_blocks array to see if full puzzle is solved yet
        for i in range(3):                                          #
            if 0 in solved_blocks[i]:                               #
                return False                                        #
        return True                                                 #
    
    def main_loop():                                                # does a full loop through the whole puzzle, sending 1 block at a time to be solved
        for x in range(3):                                          #
            for y in range(3):                                      #
                if solved_blocks[x][y] == 0:                        #
                    solved_blocks[x][y] = solve_block(x*3, y*3)     # x*3, y*3 sends the top-left coordinates of each block
    
    def populate_col(x):                                            # populates a single full column
        return [puzzle[x][y] for y in range(9)]                     #
        
    def populate_row(y):                                            # populates a single full row
        return [puzzle[x][y] for x in range(9)]                     #
    
    def solve_block(topleft_x,topleft_y):                                                                                       # this is where the fun begins

        def check_num_is_valid(x, y, n):                                                                                        # check if the number we are looking for already exists...
            block_contains = n in block                                                                                         #                                                    ...within its block
            cols_contain = (x % 3 == 0 and n in cols[0]) or (x % 3 == 1 and n in cols[1]) or (x % 3 == 2 and n in cols[2])      #                                                    ...within its column
            rows_contain = (y % 3 == 0 and n in rows[0]) or (y % 3 == 1 and n in rows[1]) or (y % 3 == 2 and n in rows[2])      #                                                    ...within its row
            if block_contains or cols_contain or rows_contain:                                                                  # check block or column or row already contains our number
                return False                                                                                                    # 
            return True                                                                                                         # 
        
        def solve_cell(x, y):                                                                                                   # solve a single cell
            valid_numbers = []                                                                                                  #
            for n in range(1, 10):                                                                                              # loop through numbers 1-9
                if check_num_is_valid(x, y, n):                                                                                 # check number is a valid possibility for the current cell
                    valid_numbers.append(n)                                                                                     # if valid then add to list of valid_numbers
            if len(valid_numbers) == 1:                                                                                         # check there is only 1 valid number for current cell
                puzzle[x][y] = valid_numbers[0]                                                                                 # if only 1 possibility then input into cell

        block = [puzzle[x][y] for x in range(topleft_x, topleft_x+3) for y in range(topleft_y, topleft_y+3)]                    # populate current 3x3 block
        if not 0 in block:                                                                                                      # if no 0s in current block then block is solved
            return True                                                                                                         #

        cols = [populate_col(topleft_x), populate_col(topleft_x+1), populate_col(topleft_x+2)]                                  # populate each of the 3 full columns that intersect with this block
        rows = [populate_row(topleft_y), populate_row(topleft_y+1), populate_row(topleft_y+2)]                                  # populate each of the 3 full rows that intersect with this block

        for x in range(topleft_x, topleft_x+3):                                                                                 # loop through each cell in the current block and solve for each
            for y in range(topleft_y, topleft_y+3):                                                                             #
                if puzzle[x][y] == 0:                                                                                           # check current cell isn't already solved before attempting to solve
                    solve_cell(x, y)                                                                                            #
        return False                                                                                                            # return false at the end 
    
    while solved == False:                                          # continue iterating through puzzle until all blocks are solved
        main_loop()                                                 #
        solved = check_if_solved()                                  # check if all 9 blocks are solved
    return puzzle                                                   #
Leave a Comment