Created
July 8, 2014 03:42
-
-
Save sampathweb/2e763ef5a1b01d3e46a6 to your computer and use it in GitHub Desktop.
Sudoku Solver - On the Air
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
import random | |
def print_puzzle(puzzle): | |
print('---' * 18) | |
for row in range(9): | |
for col in range(9): | |
pos = row * 9 + col | |
print(' ', puzzle[pos]['val'], end=' |') | |
print(end='\n') | |
if (row + 1) % 3 == 0: | |
print('---' * 18) | |
def init_puzzle(seed_values): | |
row_axis = [] | |
col_axis = [] | |
box_axis = [] | |
for row in range(9): | |
row_axis.append([1, 2, 3, 4, 5, 6, 7, 8, 9]) | |
col_axis.append([1, 2, 3, 4, 5, 6, 7, 8, 9]) | |
box_axis.append([1, 2, 3, 4, 5, 6, 7, 8, 9]) | |
puzzle = [] | |
for item in range(81): | |
row = item // 9 | |
col = item % 9 | |
if row < 3: | |
box = 0 | |
elif row < 7: | |
box = 3 | |
else: | |
box = 6 | |
if col < 3: | |
box += 0 | |
elif col < 7: | |
box += 1 | |
else: | |
box += 2 | |
cell = {} | |
cell['val'] = 0 | |
cell['col'] = col | |
cell['row'] = row | |
cell['box'] = box | |
puzzle.append(cell) | |
for row, col, seed_num in seed_values: | |
# print(row, col, seed_num) | |
pos = (row * 9) + col | |
cell = puzzle[pos] | |
if seed_num in row_axis[cell['row']] and seed_num in col_axis[cell['col']] and seed_num in box_axis[cell['box']]: | |
row_axis[cell['row']].remove(seed_num) | |
col_axis[cell['col']].remove(seed_num) | |
box_axis[cell['box']].remove(seed_num) | |
cell['val'] = seed_num | |
else: | |
print('invalid seed: ', row, col, seed_num) | |
return puzzle, row_axis, col_axis, box_axis | |
def _get_valid_choices(row_values, col_values, grid_values): | |
valid_choices = [] | |
for val in range(1, 10): | |
if val in row_values and val in col_values and val in grid_values: | |
valid_choices.append(val) | |
return valid_choices | |
def solve_puzzle(init_seed): | |
prob_puzzle, prob_row_axis, prob_col_axis, prob_box_axis = init_puzzle(init_seed) | |
success = False | |
attempts = 0 | |
while not success and attempts < 10000: | |
success = True | |
attempts += 1 | |
puzzle = [] | |
row_axis = [] | |
col_axis = [] | |
box_axis = [] | |
for item in range(81): | |
puzzle.append(prob_puzzle[item].copy()) | |
for idx in range(9): # Deep Copy | |
row_axis.append(prob_row_axis[idx].copy()) | |
col_axis.append(prob_col_axis[idx].copy()) | |
box_axis.append(prob_box_axis[idx].copy()) | |
for row in range(9): | |
for col in range(9): | |
pos = (row * 9) + col | |
cell = puzzle[pos] | |
if cell['val'] == 0: | |
valid_choices = _get_valid_choices(row_axis[cell['row']], col_axis[cell['col']], box_axis[cell['box']]) | |
if valid_choices: | |
val = random.choice(valid_choices) | |
cell['val'] = val | |
row_axis[cell['row']].remove(val) | |
col_axis[cell['col']].remove(val) | |
box_axis[cell['box']].remove(val) | |
if cell['val'] == 0: | |
# print('Failed at: ', row, col) | |
# print_puzzle(puzzle) | |
# print(row_nums) | |
# print(col_nums) | |
success = False | |
break | |
if not success: | |
break | |
return puzzle, success, attempts | |
def main(): | |
init_seed = [(0, 0, 2), (0, 1, 5), (0, 4, 4), (0, 6, 3), \ | |
(1, 0, 9), (1, 3, 2), (1, 6, 4), \ | |
(2, 1, 8), (2, 3, 9), (2, 7, 6), \ | |
(3, 1, 2), (3, 2, 1), (3, 5, 9), (3, 8, 6), \ | |
(4, 4, 3), \ | |
(5, 0, 3), (5, 3, 8), (5, 6, 1), (5, 7, 5), \ | |
(6, 1, 4), (6, 5, 5), (6, 7, 1), \ | |
(7, 2, 5), (7, 5, 2), (7, 8, 4), \ | |
(8, 2, 7), (8, 4, 6), (8, 7, 2), (8, 8, 9)] | |
puzzle, success, attempts = solve_puzzle(init_seed) | |
print('Attempts: ', attempts, ' Found Solution: ', success) | |
print_puzzle(puzzle) | |
print('Attempts: ', attempts) | |
if __name__ == '__main__': | |
main() |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment