Pilas en Python - Ejemplo práctico 7

16.1 Objetivo

Diseñar un asistente que resuelva Sudokus mediante backtracking, guardando en una pila cada decisión (número colocado y celdas afectadas) para poder retroceder cuando se detecta una contradicción.

16.2 Idea general

Representar el tablero como una matriz 9x9.
Definir una pila de decisiones donde cada nodo almacena la posición, el valor probando y el conjunto de candidatos descartados.
Cuando no haya valores posibles, desapilar la última decisión y probar el siguiente candidato.

16.3 Modo de uso

Se ingresa un Sudoku parcial. El programa ejecuta el asistente mostrando cada paso (colocación, backtrack) y finaliza con la solución o indicando que no tiene resolución.

16.4 Retos resueltos con pilas

Retroceder de forma controlada sin recurrencia, ideal para depurar estrategias.
Registrar decisiones para generar bitácoras o analizar heurísticas.
Separar la lógica de candidatos de la mecánica de backtracking.

16.5 Estructura de la pila

Cada entrada contiene:

Fila/columna.
Valor actual.
Lista de candidatos pendientes para esa celda.

16.6 Implementación en Python

N = 9


def es_valido(tablero, fila, col, valor):
  for i in range(N):
    if tablero[fila][i] == valor or tablero[i][col] == valor:
      return False
  sf = (fila // 3) * 3
  sc = (col // 3) * 3
  for i in range(3):
    for j in range(3):
      if tablero[sf + i][sc + j] == valor:
        return False
  return True


def siguiente_vacio(tablero):
  for i in range(N):
    for j in range(N):
      if tablero[i][j] == 0:
        return i, j
  return None


def candidatos_para(tablero, fila, col):
  return [v for v in range(1, 10) if es_valido(tablero, fila, col, v)]


def resolver(tablero):
  pila = []
  while True:
    pos = siguiente_vacio(tablero)
    if pos is None:
      return True
    fila, col = pos
    candidatos = candidatos_para(tablero, fila, col)
    if candidatos:
      valor = candidatos[0]
      tablero[fila][col] = valor
      pila.append({"fila": fila, "col": col, "candidatos": candidatos, "idx": 1})
      continue

    avanzo = False
    while pila and not avanzo:
      estado = pila.pop()
      tablero[estado["fila"]][estado["col"]] = 0
      while estado["idx"] < len(estado["candidatos"]):
        valor = estado["candidatos"][estado["idx"]]
        estado["idx"] += 1
        if es_valido(tablero, estado["fila"], estado["col"], valor):
          tablero[estado["fila"]][estado["col"]] = valor
          pila.append(estado)
          avanzo = True
          break
    if not avanzo:
      return False


def imprimir(tablero):
  for fila in tablero:
    print(" ".join(str(v) for v in fila))


if __name__ == "__main__":
  tablero = [
    [5, 3, 0, 0, 7, 0, 0, 0, 0],
    [6, 0, 0, 1, 9, 5, 0, 0, 0],
    [0, 9, 8, 0, 0, 0, 0, 6, 0],
    [8, 0, 0, 0, 6, 0, 0, 0, 3],
    [4, 0, 0, 8, 0, 3, 0, 0, 1],
    [7, 0, 0, 0, 2, 0, 0, 0, 6],
    [0, 6, 0, 0, 0, 0, 2, 8, 0],
    [0, 0, 0, 4, 1, 9, 0, 0, 5],
    [0, 0, 0, 0, 8, 0, 0, 7, 9],
  ]

  if resolver(tablero):
    print("Sudoku resuelto:")
    imprimir(tablero)
  else:
    print("Sin solucion")

Abrir editor online

16.7 Extensiones

Agregar heurísticas como “menor cantidad de candidatos primero”.
Mostrar mensajes en cada backtrack para guiar al usuario.
Exponer la pila de decisiones para depurar la estrategia.

Retornar