simple sudoku solver
unknown
python
2 years ago
6.1 kB
15
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 #Editor is loading...
Leave a Comment