backtracking - El salto del caballo

   ,   



El salto del caballo es un viejo problema que existe mucho antes que los ordenadores. Consiste en, dada una posición inicial, en un tablero de ajedrez recorrer todas las casillas del tablero únicamente con los movimientos del caballo sin repetir ninguna casilla.
Este problema antiguamente se resolvía “a mano” probando posibles soluciones y anotando las que eran erróneas, es decir método prueba-error. Con la llegada de los ordenadores se soluciono mediante técnicas de inteligencia artificial. Usando algoritmos de búsqueda de caminos.



He creado una versión en Python de este problema típico de IA. Yo no se usar de momento los árboles en Python que sería lo ideal para resolver este problema así que lo he hecho de la manera que se me ha ido ocurriendo.
Partiendo de la idea de que el caballo puede mover como máximo a 8 posiciones diferentes el algoritmo consiste en pasar a una función los posibles movimientos del caballo descartar los que estén fuera del tablero y las casillas ya visitadas y probar con el resto. Si una posición se queda sin posibles siguientes movimientos, volver a la anterior posición y probar la siguiente posible. Lo he implementado con una función recursiva, se llama así misma.

Heurística

En cuanto a la heurística, huy un método que dice que se debe visitar primero las casillas con menos movimientos posibles. Así que he hecho una función que analiza los posibles movimientos de los vecinos y ordenada la lista de movimientos de menor a mayor.
El juego es de un tablero de 8×8, es decir 64 posiciones diferentes, que son las de un tablero de ajedre, aunque se puede ajustar el juego para que halle la solución de un tablero de nxn
Bueno dejo el código después del salto.
001
002
003
004
005
006
007
008
009
010
011
012
013
014
015
016
017
018
019
020
021
022
023
024
025
026
027
028
029
030
031
032
033
034
035
036
037
038
039
040
041
042
043
044
045
046
047
048
049
050
051
052
053
054
055
056
057
058
059
060
061
062
063
064
065
066
067
068
069
070
071
072
073
074
075
076
077
078
079
080
081
082
083
084
085
086
087
088
089
090
091
092
093
094
095
096
097
098
099
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
# -*- coding: utf-8 -*-
###########################
# Salto del Caballo
# Versión: 0.2
# Autor: Adrigm
# Email: adrigm.admin@gmail.com
# Web: www.adrigm.es
# Licencia: GPL
###########################
# Bibliotecas.
import random
import sys
# Funciones.
# ---------------------------------------------------------------------
# Dibuja el tablero.
def dibujar(tablero):
    tab = ""
    for f in range(8):
        for c in range(8):
            if tablero[f]1 < 10:
                celda = " " + str(tablero[f]1)
            else:
                celda = str(tablero[f]1)
            tab = tab + celda + " "
        tab = tab + "\n"
    print tab
# Devuelve una lista con las coordenadas del caballo.
def pos_c(tablero):
    for f in range(8):
        for c in range(8):
            if tablero[f]1 == "CC":
                pos = [f, c]
                return pos
# Devuelve 1 si el tablero está lleno.
def lleno(tablero):
    for f in range(8):
        for c in range(8):
            if tablero[f]1 == "__":
                return 0
    return 1
# Mueve desde CC desde inicial hasta final.
def mover(inicial, final, tablero, contador):
    tablero[inicial[0]][inicial[1]] = contador
    tablero[final[0]][final[1]] = "CC"
# Retrocede una posición.
def retroceder(inicial, final, tablero):
    tablero[inicial[0]][inicial[1]] = "__"
    tablero[final[0]][final[1]] = "CC"
# devuelve una lista con los movimientos posibless.
def posibles(mov, pos, tablero):
    posibles = []
    for n in range(8):
        if (pos[0] + mov[n][0]) in range(8) and (pos[1] + mov[n][1]) in range(8):
            if tablero[pos[0] + mov[n][0]][pos[1] + mov[n][1]] == "__":
                v = [pos[0]+mov[n][0], pos[1]+mov[n][1]]
                posibles.append(v)
    return posibles
# Ordena dos listas en función de la primera.
def ordenar(lista, listb):
    if listb == []:
        return listb
    else:
        for i in range(len(lista)):
            for j in range(len(lista) -1):
                if lista[j] > lista[j+1]:
                    listb[j], listb[j+1] = listb[j+1], listb[j]
                    lista[j], lista[j+1] = lista[j+1], lista[j]
    return listb
# Ordena los valores de manera que primero se mueva a las menos probables.
def heuristica(pos_mov, tablero, mov):
    n_pos = []
    for n in range(len(pos_mov)):
        pos = len(posibles(mov, pos_mov[n], tablero))
        n_pos.append(pos)
    return ordenar(n_pos, pos_mov)
# Función recursiva principal.
def caballo(contador):
    contador += 1
    pos = pos_c(tablero)
    mov = [[2, 1], [1, 2], [-2, 1], [2, -1], [-1, 2], [1, -2], [-2, -1], [-1, -2]]
    pos_mov = posibles(mov, pos, tablero)
    pos_mov = heuristica(pos_mov, tablero, mov)
    for i in range(len(pos_mov)):
        pos_ant = pos
        mover(pos, pos_mov[i], tablero, contador)
        dibujar(tablero)
        if lleno(tablero):
            sys.exit()
        pos = pos_c(tablero)
        caballo(contador)
        retroceder(pos, pos_ant, tablero)
        pos = pos_c(tablero)
        dibujar(tablero)
# ---------------------------------------------------------------------
# Crea un tablero de 8x8.
tablero = range(8)
for n in tablero:
    tablero[n] = range(8)
# Pone el tablero a 0.
for f in range(8):
    for c in range(8):
        tablero[f]1 = "__"
# Posición inicial caballo.
tablero[random.randint(0,7)][random.randint(0,7)] = "CC"
# Comienza el programa.
dibujar(tablero)
contador = 0
caballo(contador)