El caballo no tiene ningun problema personalmente, pero la victoria del jugador Indio Anand contra el Israeli Gelfand en el campeonato del mundo de ajedrez esta semana es buena oportunidad de implicar ajedrez en este blog de TSQL. El problema del caballo es el desafio de pasar en los 64 casillas de la tabla del ajedrez en 63 pasos de caballo, quiere decir- pasar en cada casilla una vez, no mas y no menos. Segun Wikipedia hay 13,267,364,410,532 soluciones ciclicas (comienzan y terminan en la misma casilla) y desconocido numero de soluciones que no son ciclicas, asi que encontrar todas las soluciones pudiera durar miles de años. Nosotros nos coformaremos con una.. Primero que nada crearemos tabla que representara las 64 casillas de la tabla del ajedrez:
With Tabla As
(Select 1 Casilla,
'01' CasillaS,
1/8+1 Fila,
1%8 Columna
Union All
Select Casilla+1 Casilla,
Right('0'+Cast(Casilla+1 As Varchar(2)),2) Casilla,
Casilla/8+1 Fila,
Casilla%8+1 Columna
From Tabla
Where Casilla<64)
Select *
Into T_Tabla
From Tabla;
Select * From T_Tabla;
La ejecución: en cada paso el caballo va 2 casillas a una dirección y 1 casilla a la dirección vertical, por lo tanto que la multiplicación de los cambios en los numeros de la fila y de la columna resultan en |2| (valor absoluto). En cada paso hay que elejir en una casilla donde el caballo no habra estado todavia (los numeros de las casillas se agregan en la columna Track en una cadena de 193 caracteres- 64 numeros de 2 digitos y 65 comas):
With T1 As
(Select 1 Paso,
Cast(','+CasillaS+',' As Varchar(193)) Track,
Fila,
Columna
From T_Tabla
Select T.Paso+1 Paso,
Cast(T.Track+L.CasillaS+',' As Varchar(193)) Track,
L.Fila,
L.Columna
From T1 T
Inner Join T_Tabla L
On (T.Fila-L.Fila)*(T.Columna-L.Columna) In (-2,2)
And T.Track Not Like '%,'+L.CasillaS+',%'
Where T.Paso<64)
Select Top 1 *
From T1
Where Paso=64;
En mi laptop la ejecución duro 1 hora:
El resultado representa la siguiente solución:
Tags: