-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathsudoku.py
235 lines (191 loc) · 7.12 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
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
VACIO = 0
ALTO_TABLERO = 9
ANCHO_TABLERO = 9
ALTO_CUADRANTE = 3
ANCHO_CUADRANTE = 3
from random import *
def crear_juego(representacion):
'''
Dada una representación en cadena de un juego de Sudoku,
devuelve un juego de Sudoku.
El juego de Sudoku se representa como una matriz de 9x9
donde cada elemento es un número entero o la constante
VACIO para indicar que no se escribió ningún número en
esa posición.
La representación es una cadena con el siguiente formato:
003020600
900305001
001806400
008102900
700000008
006708200
002609500
800203009
005010300
Donde un 0 significa que la casilla está vacía.
'''
M = []
for line in representacion.splitlines():
row = []
for char in line:
row.append(int(char))
M.append(row)
return M
def hay_valor_en_fila(sudoku, fila, valor):
'''
Devuelve True si ya hay un casillero con el valor
'valor' en la fila 'fila'.
Por ejemplo para fila = 3 deberán revisar todas las
siguientes celdas:
(3, 0), (3, 1), (3, 2), (3, 3), (3, 4), (3, 5), (3, 6), (3, 7), (3, 8)
'''
for i in range (ANCHO_TABLERO):
if sudoku[fila][i] == valor:
return True
return False
def hay_valor_en_columna(sudoku, columna, valor):
'''
Devuelve True si ya hay un casillero con el valor 'valor'
en la columna 'columna'.
Por ejemplo para columna = 3 deberán revisar todas las
siguientes celdas:
(0, 3), (1, 3), (2, 3), (3, 3), (4, 3), (5, 3), (6, 3), (7, 3), (8, 3)
'''
for j in range (ALTO_TABLERO):
if sudoku[j][columna] == valor:
return True
return False
def obtener_origen_region(fila, columna):
'''
Devuelve la posición de la celda de la esquina superior izquierda
de la región en que se encuentra la celda en (fila, columna).
Las regiones se agrupan de la siguiente forma:
*[0,0] [0,1] [0,2] *[0,3] [0,4] [0,5] *[0,6] [0,7] [0,8]
[1,0] [1,1] [1,2] [1,3] [1,4] [1,5] [1,6] [1,7] [1,8]
[2,0] [2,1] [2,2] [2,3] [2,4] [2,5] [2,6] [2,7] [2,8]
*[3,0] [3,1] [3,2] *[3,3] [3,4] [3,5] *[3,6] [3,7] [3,8]
[4,0] [4,1] [4,2] [4,3] [4,4] [4,5] [4,6] [4,7] [4,8]
[5,0] [5,1] [5,2] [5,3] [5,4] [5,5] [5,6] [5,7] [5,8]
*[6,0] [6,1] [6,2] *[6,3] [6,4] [6,5] *[6,6] [6,7] [6,8]
[7,0] [7,1] [7,2] [7,3] [7,4] [7,5] [7,6] [7,7] [7,8]
[8,0] [8,1] [8,2] [8,3] [8,4] [8,5] [8,6] [8,7] [8,8]
Las celdas marcadas con un (*) son las celdas que deberá
devolver esta función para la correspondiente región.
Por ejemplo, para la posición (fila = 1, columna = 4) la función
deberá devolver (0, 3).
'''
i = None
j = None
if fila >= 0 and fila < 3:
i = 0
elif fila >= 3 and fila < 6:
i = 3
elif fila >= 6 and fila < 9:
i = 6
if columna >= 0 and columna < 3:
j = 0
elif columna >= 3 and columna < 6:
j = 3
elif columna >= 6 and columna < 9:
j = 6
return i, j
def hay_valor_en_region(sudoku, fila, columna, valor):
'''
Devuelve True si hay hay algún casillero con el valor `valor`
en la región de 3x3 a la que corresponde la posición (fila, columna).
Ver como se agrupan las regiones en la documentación de la función
obtener_origen_region.
Por ejemplo, para la posición (fila = 0, columna = 1) deberán revisar
si está `valor` en todas las siguientes celdas:
(0, 0), (0, 1) (0, 2), (1, 0), (1, 1), (1, 2), (2, 0), (2, 1), (2, 2).
'''
origen_region = obtener_origen_region(fila, columna)
for i in range (origen_region[0], origen_region[0] + ALTO_CUADRANTE):
for j in range (origen_region[1], origen_region[1] + ANCHO_CUADRANTE):
if sudoku[i][j] == valor:
return True
return False
def es_movimiento_valido(sudoku, fila, columna, valor):
'''
Devuelve True si se puede poner 'valor' en la posición
(fila, columna) y el Sudoku sigue siendo válido; o False
en caso contrario.
'valor' se puede ubicar en la posición (fila, columna) si
se cumple lo siguiente:
- Ningún otro elemento que esté en la misma fila es igual a 'valor'
- Ningún otro elemento que esté en la misma columna es igual a 'valor'
- Ningún otro elemento que esté en la misma región es igual a 'valor'
No modifica el Sudoku recibido.
'''
if not (hay_valor_en_fila(sudoku, fila, valor)
and hay_valor_en_columna(sudoku, columna, valor)
and hay_valor_en_region(sudoku, fila, columna, valor)):
return True
return False
def copiar_matriz(sudoku):
new_sudoku = []
for i in range (ALTO_TABLERO):
row = []
for j in range (ANCHO_TABLERO):
row.append(sudoku[i][j])
new_sudoku.append(row)
return new_sudoku
def insertar_valor(sudoku, fila, columna, valor):
'''
Intenta insertar el valor de la celda en la posición
(fila, columna).
Si el movimiento es válido se devolverá un nuevo Sudoku
con el valor cambiado. En caso contrario se devolverá el
mismo Sudoku que se recibió por parámetro.
'''
if es_movimiento_valido(sudoku, fila, columna, valor):
new_sudoku = copiar_matriz(sudoku) #copio la matriz
new_sudoku[fila][columna] = valor
return new_sudoku
return sudoku
def borrar_valor(sudoku, fila, columna):
'''
Borra el valor de la celda que está en la posición
(fila, columna).
No modifica el Sudoku recibido por parámetro, devuelve uno
nuevo con la modificación realizada.
'''
new_sudoku = copiar_matriz(sudoku)
new_sudoku[fila][columna] = 0
return new_sudoku
def esta_terminado(sudoku):
'''
Devuelve True si el Sudoku está completado
correctamente.
Un Sudoku está completado correctamente cuando todas
sus celdas tienen números y todos los números son válidos
(es decir, no hay repetidos en la columna, ni en la fila
ni en la región).
'''
for fila in range(ALTO_TABLERO):
for columna in range(ANCHO_TABLERO):
for valor in range(1, 10):
if not hay_valor_en_fila(sudoku, fila, valor) or not hay_valor_en_columna(sudoku, columna, valor) or not hay_valor_en_region(sudoku, fila, columna, valor):
return False
return True
def obtener_valor(sudoku, fila, columna):
'''
Devuelve el número que se encuentra en la celda (fila, columna)
o la constante VACIO si no hay ningún número en dicha celda.
'''
if sudoku[fila][columna] >0:
return sudoku[fila][columna]
return VACIO
def hay_movimientos_posibles(sudoku):
'''
Devuelve True si hay al menos un movimiento posible
en el estado actual del juego.
Que exista un movimiento posible no implica que el juego
pueda completarse correctamente, sólamente indica que hay
al menos una posible inserción.
'''
for i in range(ALTO_TABLERO):
for j in range(ANCHO_TABLERO):
if obtener_valor(sudoku, i, j) == VACIO:
return True
return False