-
Notifications
You must be signed in to change notification settings - Fork 0
/
sudoku.py
executable file
·134 lines (119 loc) · 5.45 KB
/
sudoku.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
#!/usr/bin/env python
# -*- coding: utf-8 -*-
import sys, random, argparse
if sys.version[0] == '2': input = raw_input
BOARD_SIZE = 81
BOARD_WIDTH = 9
BOX_WIDTH = 3
DEFAULT_RANDOM_INTERVAL = (32, 64)
def is_valid(num, pos, board):
x, y = pos
# Check horizontally and vertically
for i in range(BOARD_WIDTH):
if board[x][i] == num: return False
if board[i][y] == num: return False
# Find top-left corner of the box containing pos
dx, dy = x // BOX_WIDTH, y // BOX_WIDTH
# Check box containing pos
for i in range(BOX_WIDTH*dx, BOX_WIDTH*dx + BOX_WIDTH):
for j in range(BOX_WIDTH*dy, BOX_WIDTH*dy + BOX_WIDTH):
if board[i][j] == num: return False
return True
def find_next_position(board, x, y):
return (x + 1, y) if x + 1 < BOARD_WIDTH else (0, y + 1)
def find_empty_cell(board, start_pos = (0, 0)):
x, y = start_pos
while x < BOARD_WIDTH and y < BOARD_WIDTH and board[x][y] != None:
x, y = find_next_position(board, x, y)
return x, y
def solve_sudoku(board, pos = (0, 0)):
x, y = find_empty_cell(board, pos)
# If all gaps have been filled, return True
if x >= BOARD_WIDTH or y >= BOARD_WIDTH: return True
# Find all valid values
values = [v for v in range(1, BOARD_WIDTH + 1)
if is_valid(v, (x, y), board)]
while len(values) > 0:
# Put them in the cell randomly
board[x][y] = random.choice(values)
# Try to fill the other gaps
if solve_sudoku(board, find_empty_cell(board, (x, y))): return True
# Remove values which do not lead to a solution
values.remove(board[x][y])
board[x][y] = None
return False
def generate_sudoku(gaps):
# Create an empty board
board = [[None for i in range(BOARD_WIDTH)] for j in range(BOARD_WIDTH)]
# Fill board with random values
solve_sudoku(board)
while gaps:
# Find random position
x = random.randint(0, BOARD_WIDTH - 1)
y = random.randint(0, BOARD_WIDTH - 1)
# If the value at that position has already been deleted,
# find another one
if board[x][y] == None: continue
# Otherwise, delete the value
board[x][y] = None
gaps -= 1
return board
def board_to_str(board):
return ('\n'.join([''.join([str(i) if i else ' ' for i in row])
for row in board]))
def row_to_pretty_str(row_values):
return '┃' + '┃'.join('│'.join(
' {} '.format(row_values[i + j*BOX_WIDTH]
if row_values[i + j*BOX_WIDTH] else ' ')
for i in range(BOX_WIDTH))
for j in range(BOX_WIDTH)) + '┃'
def board_to_pretty_str(board):
sudoku = ['┏━━━┯━━━┯━━━┳━━━┯━━━┯━━━┳━━━┯━━━┯━━━┓', None,
'┠───┼───┼───╂───┼───┼───╂───┼───┼───┨', None,
'┠───┼───┼───╂───┼───┼───╂───┼───┼───┨', None,
'┣━━━┿━━━┿━━━╋━━━┿━━━┿━━━╋━━━┿━━━┿━━━┫', None,
'┠───┼───┼───╂───┼───┼───╂───┼───┼───┨', None,
'┠───┼───┼───╂───┼───┼───╂───┼───┼───┨', None,
'┣━━━┿━━━┿━━━╋━━━┿━━━┿━━━╋━━━┿━━━┿━━━┫', None,
'┠───┼───┼───╂───┼───┼───╂───┼───┼───┨', None,
'┠───┼───┼───╂───┼───┼───╂───┼───┼───┨', None,
'┗━━━┷━━━┷━━━┻━━━┷━━━┷━━━┻━━━┷━━━┷━━━┛']
# Insert rows
for i in range(9): sudoku[2*i+1] = row_to_pretty_str(board[i])
return '\n'.join(sudoku)
def parse_args():
parser = argparse.ArgumentParser()
group = parser.add_mutually_exclusive_group()
group.add_argument('-s', '--solve', action = 'store_true',
help = 'solve sudoku')
group.add_argument('-g', '--generate', type = int, dest = 'GAPS',
help = 'generate sudoku with GAPS gaps',
default = random.randint(*DEFAULT_RANDOM_INTERVAL))
parser.add_argument("--pretty", help = 'pretty-print the results',
action="store_true")
return parser.parse_args()
def main():
args = parse_args()
if args.solve:
data = ''
try:
while True: data += input()
except EOFError:
data_len = len(data)
if data_len < BOARD_SIZE: data += ' ' * (BOARD_SIZE - data_len)
elif data_len > BOARD_SIZE: data = data[:BOARD_SIZE]
board = [[int(i) if i != ' ' else None
for i in data[BOARD_WIDTH*j:BOARD_WIDTH*j + BOARD_WIDTH]]
for j in range(BOARD_WIDTH)]
if not solve_sudoku(board):
sys.stderr.write('Solving sudoku failed')
sys.exit(1)
if args.pretty: print(board_to_pretty_str(board))
else: print(board_to_str(board))
else:
if args.pretty:
print(board_to_pretty_str(generate_sudoku(args.GAPS)))
else:
print(board_to_str(generate_sudoku(args.GAPS)))
if __name__ == '__main__':
main()