Problema del caballo

El problema del caballo es un antiguo problema matemático en el que se pide que, teniendo una cuadrícula de n x n casillas y un caballo de ajedrez colocado en una posición cualquiera ( x, y ), el caballo pase por todas las casillas y una sola vez.

Muchos matemáticos han buscado una solución matemática a este problema, entre ellos Leonhard Euler.

Se han encontrado muchas soluciones a este problema y de hecho no se sabe con seguridad de cuántas maneras diferentes es posible solucionarlo.

Algunas variaciones de este problema han sido estudiadas por los matemáticos, tales como:

Buscar soluciones cíclicas, en la cual se debe llegar a la misma casilla de la cual se partió.
Tableros de diferente número de columnas o diferente número de filas.
Juegos de dos jugadores basados en la idea.
Problemas usando ligeras variaciones en la forma de moverse el caballo.

El problema del caballo es una forma del problema más general problema de la ruta Hamiltoniana en la teoría de grafos.

A la derecha podemos apreciar una de las posibles soluciones en un tablero de ajedrez convencional de ocho columnas por ocho filas. Abajo, una solución cíclica en que la casilla de destino es justo la anterior a la de partida.

63	14	37	24	51	26	35	10
22	39	62	13	36	11	50	27
15	64	23	38	25	52	9	34
40	21	16	61	12	33	28	49
17	60	1	44	29	48	53	8
2	41	20	57	6	55	32	47
59	18	43	4	45	30	7	54
42	3	58	19	56	5	46	31

El problema del caballo en la literatura

Solución del problema del caballo para la novela La vida instrucciones de uso.

Los capítulos de la novela La vida instrucciones de uso (1978) de Georges Perec siguen una ordenación que corresponde a una solución del problema del caballo sobre una cuadrícula de 10×10. La solución fue encontrada experimentalmente por el mismo autor.^[1]

Véase también

Referencias

↑ Macho Stadler, Marta (13 de octubre de 2010). «La vida instrucciones de uso, de Georges Perec». Centro virtual de divulgación de las matemáticas. Archivado desde el original el 16 de enero de 2016. Consultado el 30 de marzo de 2014.

Enlaces externos

The knight's tour (en inglés)
Knight's tour notes (en inglés)
Código del problema del caballo en Javascript

Datos: Q12524
Multimedia: Knight's Tours / Q12524

[1] Macho Stadler, Marta (13 de octubre de 2010). «La vida instrucciones de uso, de Georges Perec». Centro virtual de divulgación de las matemáticas. Archivado desde el original el 16 de enero de 2016. Consultado el 30 de marzo de 2014.

[1]

63	14	37	24	51	26	35	10
22	39	62	13	36	11	50	27
15	64	23	38	25	52	9	34
40	21	16	61	12	33	28	49
17	60	1	44	29	48	53	8
2	41	20	57	6	55	32	47
59	18	43	4	45	30	7	54
42	3	58	19	56	5	46	31

63	14	37	24	51	26	35	10
22	39	62	13	36	11	50	27
15	64	23	38	25	52	9	34
40	21	16	61	12	33	28	49
17	60	1	44	29	48	53	8
2	41	20	57	6	55	32	47
59	18	43	4	45	30	7	54
42	3	58	19	56	5	46	31

63	14	37	24	51	26	35	10
22	39	62	13	36	11	50	27
15	64	23	38	25	52	9	34
40	21	16	61	12	33	28	49
17	60	1	44	29	48	53	8
2	41	20	57	6	55	32	47
59	18	43	4	45	30	7	54
42	3	58	19	56	5	46	31