Download Taller de Backtracking

Taller de Backtracking
Introducción a la computación (Matemática)
Agustin Montero
Agustin Montero
Taller de Backtracking
Menú
• Taller de Backtraking
• Ejercicio: ¡Sudoku!
Agustin Montero
Taller de Backtracking
Backtracking
Agustin Montero
Taller de Backtracking
Backtracking
8 reinas
Agustin Montero
Taller de Backtracking
¡Sudoku!
Agustin Montero
Taller de Backtracking
¡Sudoku!
variante: killer sudoku
Agustin Montero
Taller de Backtracking
¡Sudoku!
volviendo al original
Agustin Montero
Taller de Backtracking
¡Sudoku!
volviendo al original
• Ejercicio:
Implementar en Python un programa que resuelva Sudokus
Agustin Montero
Taller de Backtracking
¡Sudoku!
volviendo al original
• Ejercicio:
Implementar en Python un programa que resuelva Sudokus
• Aprovechar la técnica de Backtracking
Agustin Montero
Taller de Backtracking
Implementando Sudoku en Python
main.py
#!/usr/bin/env python
import sys
import time
from TAD_Sudoku import Sudoku
def main():
entrada = open(str(sys.argv[1]),’r’)
sudoku= Sudoku(entrada)
t= time.time()
sudoku.resolver()
t= time.time() - t
sudoku.mostrar()
print "Tiempo total: ", t
main()
Agustin Montero
Taller de Backtracking
Implementando Sudoku en Python
Entradas
sudoku0.txt
2
0
2
0
4
1
0
0
0
0
0
4
0
0
3
0
0
sudoku1.txt
3
0
1
0
0
0
0
5
0
4
6
0
0
0
0
0
0
0
0
5
7
8
0
6
0
0
0
0
0
0
0
2
0
5
0
8
0
3
0
0
0
8
0
0
0
7
0
5
0
1
0
3
0
0
0
0
0
0
0
3
0
6
4
2
0
0
0
0
0
0
0
0
1
7
0
1
0
0
0
0
3
0
Agustin Montero
Taller de Backtracking
Implementando Sudoku en Python
TAD_Sudoku.py
#!/usr/bin/env python
class Sudoku:
def __init__(self, entrada=None):
if entrada is None:
# si no hay entrada, uso uno default
self.tam, self.tabl= Sudoku.__default()
else:
self.tabl = []
self.tam = int(entrada.readline())
n= self.tam**2
for i in range(n):
row= map(int,entrada.readline().split())
self.tabl.append(row)
self.resuelto= self.__esSolucion()
Agustin Montero
Taller de Backtracking
Implementando Sudoku en Python
TAD_Sudoku.py
def mostrar(self)
def resolver(self)
def __esSolucion(self)
def __posicionesLibres(self)
def __backtrack(self, ????? )
• Un detalle más:
python main.py sudoku0.txt
Agustin Montero
Taller de Backtracking
Backtracking podado
8 reinas
Agustin Montero
Taller de Backtracking
Implementando Sudoku en Python
Backtracking + Poda
def mostrar(self)
def resolver(self)
def __esSolucion(self)
def __esFactible(self)
def __backtrack(self, ????? )
Agustin Montero
Taller de Backtracking
Implementando Sudoku en Python
Backtracking + Poda
• Idea:
Agustin Montero
Taller de Backtracking
Para pensar
Problema del caballo
Agustin Montero
Taller de Backtracking