Razón Artificial

La ciencia y el arte de crear videojuegos

El salto del caballo, backtracking

Escrito por adrigm el 8 de enero de 2010 en Inteligencia Artificial, Programación | 13 Comentarios.

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.

# -*- 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)

13 Comentarios en "El salto del caballo, backtracking"

  1. jacobo dice:

    oie, que representa este pedazo de código?

    tablero[f]1
    es de la linea 24.

    lo pregunto porque lo intenté correr pero da error de sintaxis en esa parte.

  2. adrigm dice:

    Es para Python 2.x asegúrate que no estás usando una versión 3.x

  3. Richard dice:

    Disculpa, en Python 2.7 Portable me bota error de sintaxis en la linea 21. Agradeceria tu ayuda.

  4. karina dice:

    Disculpa que representa esto:
    "CC"

    cuando corro el programa me muestra error en esas partes
    gracias

  5. karina dice:

    22/04/2012 a las 18:20 pm
    Disculpa que representa esto:
    ” "CC"”cuando corro el programa me muestra error en esas partes
    gracias

  6. Llanos dice:

    alguien sabe cómo se puede hacer en Java?

  7. cemete dice:

    porqué pones “tablero[f]1″ y cómo puedo cambiarlo para que no me dé error? Uso python 2.7

  8. cemete dice:

    He quitado el 1 y lo he dejado como tablero[f] y parece que funciona, pero ahora me da este error en la linea 123: ‘str’ object does not support item assignment

  9. alex dice:

    este programa sirve también para netbeans ????

  10. Juan Miguel dice:

    # Bibliotecas
    import random
    import sys
    import time

    # — Constantes —
    ANCHO = 8
    ALTO = 8
    MOVIMIENTO_CABALLO = 8
    VACIO = 0
    # — Funciones —

    # Dibuja el tablero
    def dibujar(tablero):
    # Crea un tablero auxiliar
    tab = “”
    for fila in range(ALTO):
    for columna in range(ANCHO):
    # Crea una celda con la pieza centrada a 3 espacios
    celda = str(tablero[fila][columna]).center(3,’ ‘)
    tab = tab + celda + “”
    # Agrega un salto de linea
    tab = tab + “\n”
    # Muestra el tablero
    print(tab)
    time.sleep(2)

    # Devuelve una lsita con las coordenadas del caballo
    def pos_caballo(tablero):
    for fila in range(ALTO):
    for columna in range(ANCHO):
    # Si encuentra la posicion del caballo
    if tablero[fila][columna] == “C”:
    # Guarda la posicion del caballo
    pos = [fila, columna]
    return pos

    # Devuelve 1 si el tablero esta lleno
    def esta_lleno(tablero):
    for fila in range(ALTO):
    for columna in range(ANCHO):
    # Pregunta si la casilla esta vacia
    if tablero[fila][columna] == “*”:
    # Por una estar vacia el tablero no esta lleno
    return 0
    # Si sale del ciclo for con exito significa que todas las casillas estan ocupadasss
    return 1

    # Mueve desde CC desde inicial hasta final
    def mover(inicial, final, tablero, contador):
    # Asigna el numero actual en la posicion inical
    tablero[inicial[0]][inicial[1]] = str(contador)
    # Asigna la nueva posicion del caballo
    tablero[final[0]][final[1]] = “C”

    # Retrocede una posicion
    def retroceder(inicial, final, tablero):
    # Remueve la posicion inicial del caballo
    tablero[inicial[0]][inicial[1]] = “*”
    # Lo ubica en su nueva posicion
    tablero[final[0]][final[1]] = “C”

    # Devuelve una lista con los movimientos posibles
    def posibles_movimientos(mov, pos, tablero):
    posibles = []
    # Recorre por los 8 movimientos posibles del caballo
    for x in range(MOVIMIENTO_CABALLO):
    valor1 = pos[0] + mov[x][0]
    valor2 = pos[1] + mov[x][1]
    # Confirma de uqe la nueva posicion no este fuera de los limites
    if (valor1) in range(ANCHO) and (valor2) in range(ANCHO):
    # Pregunta si la nueva posicion esta libre
    if tablero[valor1][valor2] == “*”:
    # Asigna la nueva posicion en ‘posibles’
    v = [valor1, valor2]
    posibles.append(v)
    return posibles

    # Ordena dos listas en funcion de la primera (menor a mayor)
    def ordenar(lista_a, lista_b):
    # Si la lista_b esta vacia la retorna
    if lista_b == []: return lista_b
    else:
    # Recorre cada elemento de la lista_a
    for i in range(len(lista_a)):
    for j in range(len(lista_a) – 1):
    # Si el elemento siguiente es mayor que el actual
    if lista_a[j] > lista_a[j+1]:
    # cambia la posicion en ambas listas
    lista_b[j], lista_b[j+1] = lista_b[j+1], lista_b[j]
    lista_a[j], lista_a[j+1] = lista_a[j+1], lista_a[j]
    return lista_b

    # Ordena los valores de manera que el primero se va a los menos probables
    def heuristica(pos_mov, tablero, mov):
    n_pos = []
    for n in range(len(pos_mov)):
    pos = len(posibles_movimientos(mov, pos_mov[n], tablero))
    n_pos.append(pos)
    return ordenar(n_pos, pos_mov)

    # Fucion recursiva principal
    def caballo(contador, tablero):
    contador += 1
    pos = pos_caballo(tablero)
    # Movimientos posible del caballo en forma de “L”
    mov = [[2, 1], [1, 2], [-2, 1], [2, -1], [-1, 2], [1, -2], [-2, -1], [-1, -2]]

    pos_mov = posibles_movimientos(mov, pos, tablero)
    # Aplica el algoritmo de ‘heristica’ con los posibles movimientos
    pos_mov = heuristica(pos_mov, tablero, mov)

    # Evalua todos los movimientos que ‘heuristica’ entrega
    for i in range(len(pos_mov)):
    # Guarda la posicion del caballo antes de moverlo
    pos_ant = pos
    # Ejecuta un movimiento
    mover(pos, pos_mov[i], tablero, contador)
    dibujar(tablero)
    # Si despues del movimiento se llena el tablero, entonces se sale del programa
    if esta_lleno(tablero):
    sys.exit() # Salir del programa
    # Si sigue la ejecucion significa que aun no se ha llenado el tablero
    pos = pos_caballo(tablero)
    caballo(contador, tablero)
    # Si pasa por este punto significa que el caballo se quedo sin movimiento y necesita retorceder
    retroceder(pos, pos_ant, tablero)
    pos = pos_caballo(tablero)
    dibujar(tablero)

    def main():
    # Crea un tablero ANCHO x ALTO
    tablero = [x for x in range(ANCHO)]
    for n in tablero:
    tablero[n] = [str(x) for x in range(ALTO)]

    # Pone el tablero a cero
    for fila in range(ALTO):
    for columna in range(ANCHO):
    # Elimina los numeros y los sustituye por asteriscos
    tablero[fila][columna] = “*”

    # Posicion inicial del caballo
    tablero[0][0] = “C”

    # Comienza el programa
    dibujar(tablero)
    contador = 0
    caballo(contador, tablero)

    if __name__ == ‘__main__':
    main()

Deja un comentario