-
Notifications
You must be signed in to change notification settings - Fork 0
/
sudoku_solution_validator.py
134 lines (100 loc) · 2.59 KB
/
sudoku_solution_validator.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
# THREE GOLD STARS
# Sudoku [http://en.wikipedia.org/wiki/Sudoku]
# is a logic puzzle where a game
# is defined by a partially filled
# 9 x 9 square of digits where each square
# contains one of the digits 1,2,3,4,5,6,7,8,9.
# For this question we will generalize
# and simplify the game.
# Define a procedure, check_sudoku,
# that takes as input a square list
# of lists representing an n x n
# sudoku puzzle solution and returns the boolean
# True if the input is a valid
# sudoku square and returns the boolean False
# otherwise.
# A valid sudoku square satisfies these
# two properties:
# 1. Each column of the square contains
# each of the whole numbers from 1 to n exactly once.
# 2. Each row of the square contains each
# of the whole numbers from 1 to n exactly once.
# You may assume the the input is square and contains at
# least one row and column.
correct = [[1,2,3],
[2,3,1],
[3,1,2]]
incorrect = [[1,2,3,4],
[2,3,1,3],
[3,1,2,3],
[4,4,4,4]]
incorrect2 = [[1,2,3,4],
[2,3,1,4],
[4,1,2,3],
[3,4,1,2]]
incorrect3 = [[1,2,3,4,5],
[2,3,1,5,6],
[4,5,2,1,3],
[3,4,5,2,1],
[5,6,4,3,2]]
incorrect4 = [['a','b','c'],
['b','c','a'],
['c','a','b']]
incorrect5 = [ [1, 1.5],
[1.5, 1]]
incorrect6 = [ [2, 1, 3],
[3, 2, 1]]
def validate_square(square): #Check if elements are all integers and if columns=rows
rows=len(square)
for e in square:
cols=len(e)
if rows!=cols:
return False
for f in e:
if type(f)!=int: return False
return True
def check_line(line):
n = len(line)
i=0
while i < n:
# print 'Linea da controllare: ' + str(e)
# print 'Elemento da controllare: ' + str(i+1)
# print (i+1) in e
if (i+1) not in line:
return False
else: i = i+1
return True
def check_sudoku(square):
if not validate_square(square):
return False
n = len(square)
# Check all rows
for e in square:
if not check_line(e):
return False
# Check all cols
j=0
while j<n:
col_to_check=[]
for e in square:
col_to_check.append(e[j])
if not check_line(col_to_check):
return False
j=j+1
return True
#TEST LAZ
#print validate_square(incorrect6)
#print check_sudoku(incorrect6)
#>>> False
#print check_sudoku(incorrect)
#>>> False
#print check_sudoku(correct)
#>>> True
print check_sudoku(incorrect2)
#>>> False
#print check_sudoku(incorrect3)
#>>> False
#print check_sudoku(incorrect4)
#>>> False
#print check_sudoku(incorrect5)
#>>> False