simple sudoku solver
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