-
Notifications
You must be signed in to change notification settings - Fork 0
/
sudoku.py
139 lines (104 loc) · 3.67 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
135
136
137
138
139
# Author: Alexander Posipanko
# Description: Recursive sudoku solver. No GUI or input for now.
# Creation Date: 2/5/2020
# Last Edited: 2/5/2020
from array import *
from graphics import *
from Board import *
import pprint
import math
def main():
win = GraphWin("Sudoku Solver", 400, 400)
board = Board()
draw(win, board)
input()
board = [ [6,0,7,4,1,0,0,9,0],
[0,1,0,3,9,0,6,0,0],
[0,9,0,6,2,0,0,0,5],
[2,0,0,7,5,1,0,8,3],
[7,0,0,8,3,9,0,6,4],
[0,8,3,2,0,0,0,5,1],
[1,7,0,5,4,2,0,3,9],
[0,4,0,9,8,0,1,7,0],
[8,3,9,0,7,6,5,4,0]
]
pos = [0,0]
print("Original Board: ")
print("====================================")
print_board(board)
sol = solve(board,pos)
print("Solved Board: ")
print("====================================")
print_board(board)
def solve(board, pos):
#If we already have a number here, it stays
if board[pos[0]][pos[1]] != 0:
return solve(board, next_position(pos))
options = get_options(board, pos)
# Try all legal options
while len(options) > 0:
val = options.pop() #Take first option off of list
board = place_num(board, pos, val)
if pos[0]*9+pos[1] >= (9*9-1) or solve(board, next_position(pos)): # Escape if the board is solved
return 1
#We're out of options; not the right path to go down
place_num(board, pos, 0) #Return the board to the state it was in before entering the function and return to go down another path
return 0
# Find the next board position
def next_position(pos):
tPos = pos[0]*9 + pos[1] +1;
newpos = [0,0]
newpos[0] = int(tPos / 9)
newpos[1] = tPos % 9
return newpos
# Display the board to the terminal
def print_board(board):
#print("----------------------")
pp = pprint.PrettyPrinter()
pp.pprint(board)
print("")
# Function to get the legal numbers for a spot
def get_options(board, pos):
options = list(range(1,10))
#strike out any options already present in the row
for i in range(0,9):
val = board[pos[0]] [i]
#If the value in the current index exists in our option list, remove it
if val in options:
options.remove(val)
#strike out any options already present in the column
for i in range(0,9):
val = board [ i ][ pos[1] ]
# If the value in the current index exists in our option list, remove it
if val in options:
options.remove(val)
#strike out any options already present in the local box
box_start_x = math.floor(pos[1]/3)*3
box_start_y = math.floor(pos[0]/3)*3
for i in range(box_start_y, box_start_y+3):
for j in range(box_start_x, box_start_x+3):
val = board[i][j]
# If the value in the current index exists in our option list, remove it
if val in options:
options.remove(val)
return options
def place_num(board, pos, val):
board[pos[0]][pos[1]] = val
return board
def draw(window, board):
print("hiyo")
margin = 50
for i in range(0, 3):
for j in range(0, 3):
currX = i*100
currY = j *100
#rect = Rectangle(Point(currX+margin, currY+margin), Point(currX+100+margin, currY+100+margin))
#rect.draw(window)
draw_bold_box(window,currX+margin, currY+margin)
def draw_bold_box(window, x, y):
thickness = 3
for i in range(0, thickness):
rect = Rectangle(Point(x+i,y+i), Point(x+(100+i), y+(100+i)))
rect.draw(window)
if __name__ == '__main__':
main()