51. Sudoku¶
Sudoku es un rompecabezas matemático. Consiste en rellenar una cuadrícula de 9x9 con cifras de 1 a 9. Algunas de las casillas están previamente rellenas y una vez completado debe cumplir que:
- Cada fila debe contener todas las cifras del 1 al 9.
- Cada columna debe contener todas las cifras del 1 al 9.
- Cada bloque debe contener todas las cifras del 1 al 9. Se llama bloque a cualquiera de los 9 subcuadros de 3x3 que contiene el tablero (ver figura):
Ejemplo de Sudoku
Un Sudoku bien construido solo debe tener una solución correcta. Es decir, los números que se rellenan incialmente tienen que ser suficientes para eliminar toda posible ambigüedad.
51.1. Comprobar Sudoku¶
El problema a resolver consiste en comprobar si una solución propuesta a un Sudoku determinado es correcta o no.
Por tanto se limita a realizar las comprobaciones correspondientes a las tres propiedades de un Sudoku correcto.
def comprobar_sudoku(s):
return comprobar_filas(s) \
and comprobar_columnas(s) \
and comprobar_bloques(s)
El Sudoku lo modelaremos con una lista de 9 listas, una por cada fila. Cada lista correspondiente a una fila contiene 9 números.
def comprobar_filas(s):
for fila in s:
if not comprobar_lista(fila):
return False
return True
Comprobar una fila es contar el número de ocurrencias de cada dígito. Si no es exactamente 1 es que es incorrecto.
def comprobar_lista(s):
c = [0] * 9
for i in s:
c[i - 1] += 1
return max(c) == 1 and min(c) == 1
Otra forma es pasarlo a una forma canónica y comparar. Cuidado con las
listas, que son mutables. Haz copias antes de modificarla. Por ejemplo,
la función sorted devuelve una nueva copia de la lista ordenada, lo
que permite compararla muy facilmente.
def comprobar_lista(s):
return sorted(s) == range(1,10)
Comprobar cada columna puede reducirse al subproblema anterior si construimos una lista con los elementos de cada columna.
def comprobar_columnas(s):
for col in columnas(s):
if not comprobar_lista(col):
return False
return True
Las columnas pueden devolverse con un generador.
def columnas(s):
for i in range(9):
yield [x[i] for x in s]
O bien si no te resultan cómodos los generadores puedes devolver una lista.
def columnas(s):
cols = []
for i in range(9):
cols.append([x[i] for x in s])
return cols
Los bloques son iguales.
def comprobar_bloques(s):
for bloque in bloques(s):
if not comprobar_lista(bloque):
return False
return True
Generar los bloques es un poquito más complejo.
def bloques(s):
for y in (0,3,6):
for x in (0,3,6):
yield sum([fila[x:x+3] for fila in s[y:y+3]], [])
Con list comprehensions también es posible, ya lo vimos.
def bloques(s):
for y in (0,3,6):
for x in (0,3,6):
yield [e for fila in s[y:y+3] for e in fila[x:x+3]]
O si no te gustan los generadores, con listas.
def bloques(s):
blq = []
for y in (0,3,6):
for x in (0,3,6):
blq.append(sum([fila[x:x+3] for fila in s[y:y+3]], []))
return blq
Ya solo nos queda la lectura del Sudoku. Para ello solo hay que leer cada una de las líneas.
def leer_sudoku():
s = []
for i in range(9):
s.append(leer_linea())
return s
O con list comprehensions un poco más compacto:
def leer_sudoku():
return [ leer_linea() for i in range(9) ]
Cada línea puede leerse como un conjunto de palabras separadas por espacio y posteriormente construir la lista generando los enteros correspondientes.
def leer_linea():
s = input().strip().split(' ')
return [ int(i) for i in s ]
Con todo esto ya podemos construir el programa principal.
s = leer_sudoku()
print(comprobar_sudoku(s))
0 1 2 3 4 5 6 7 8 9
0 1 2 3 4 5 6 7 8 9
0 1 2 3 4 5 6 7 8 9
0 1 2 3 4 5 6 7 8 9
0 1 2 3 4 5 6 7 8 9
0 1 2 3 4 5 6 7 8 9
0 1 2 3 4 5 6 7 8 9
0 1 2 3 4 5 6 7 8 9
0 1 2 3 4 5 6 7 8 9
False