La otra respuesta ya es bastante larga, así que la dejo como está. Esta respuesta es mucho mejor, más simple y también correcta, mientras que la otra tiene algunos casos extremos que producirán una respuesta incorrecta. Dejaré ese ejercicio al lector.
Nota:Los saltos de línea se agregan para mayor claridad. Todo el bloque es una sola consulta
;with Walker(StartX,StartY,X,Y,Visited) as (
select X,Y,X,Y,CAST('('+right(X,3)+','+right(Y,3)+')' as Varchar(Max))
from puzzle
union all
select W.StartX,W.StartY,P.X,P.Y,W.Visited+'('+right(P.X,3)+','+right(P.Y,3)+')'
from Walker W
join Puzzle P on
(W.X=P.X and W.Y=P.Y+1 OR -- these four lines "collect" a cell next to
W.X=P.X and W.Y=P.Y-1 OR -- the current one in any direction
W.X=P.X+1 and W.Y=P.Y OR
W.X=P.X-1 and W.Y=P.Y)
AND W.Visited NOT LIKE '%('+right(P.X,3)+','+right(P.Y,3)+')%'
)
select X, Y, Visited
from
(
select W.X, W.Y, W.Visited, rn=row_number() over (
partition by W.X,W.Y
order by len(W.Visited) desc)
from Walker W
left join Walker Other
on Other.StartX=W.StartX and Other.StartY=W.StartY
and (Other.Y<W.Y or (Other.Y=W.Y and Other.X<W.X))
where Other.X is null
) Z
where rn=1
El primer paso es configurar una expresión de tabla recursiva de "caminante" que comenzará en cada celda y viajará tan lejos como pueda sin retroceder ningún paso. Asegurarse de que las celdas no se vuelvan a visitar se hace usando la columna visitada, que almacena cada celda que ha sido visitada desde cada punto de partida. En particular, esta condición AND W.Visited NOT LIKE '%('+right(P.X,3)+','+right(P.Y,3)+')%' rechaza las celdas que ya ha visitado.
Para comprender cómo funciona el resto, debe observar el resultado generado por el CTE "Walker" ejecutando "Select * from Walker order by StartX, StartY" después del CTE. Una "pieza" con 5 celdas aparece en al menos 5 grupos, cada uno con un (StartX,StartY) diferente , pero cada grupo tiene los 5 (X,Y) piezas con diferentes caminos "Visitados".
La subconsulta (Z) usa LEFT JOIN + IS NULL para eliminar los grupos hasta la única fila en cada grupo que contiene la "primera coordenada XY", definida por la condición
Other.StartX=W.StartX and Other.StartY=W.StartY
and (Other.Y<W.Y or (Other.Y=W.Y and Other.X<W.X))
La intención es que cada celda que se pueda visitar a partir de (StartX, StartY), compare entre celdas del mismo grupo y encuentre la celda donde NINGUNA OTRA celda está en una fila superior, o si están en el misma fila, está a la izquierda de esta celda. Sin embargo, esto todavía nos deja con demasiados resultados. Considere solo una pieza de 2 celdas en (3,4) y (4,4):
StartX StartY X Y Visited
3 4 3 4 (3,4) ******
3 4 4 4 (3,4)(4,4)
4 4 4 4 (4,4)
4 4 3 4 (4,4)(3,4) ******
Quedan 2 filas con la "primera coordenada XY" de (3,4), marcada con ****** . Solo necesitamos una fila, por lo que usamos Row_Number y, dado que estamos numerando, también podríamos optar por el Visited más largo camino, lo que nos daría la mayor cantidad de las celdas dentro de la pieza como podemos obtener.
La consulta externa final simplemente toma las primeras filas (RN=1) de cada grupo similar (X,Y).
Para mostrar TODAS las celdas de cada pieza, cambie la líneaselect X, Y, Visited
en el medio para
select X, Y, (
select distinct '('+right(StartX,3)+','+right(StartY,3)+')'
from Walker
where X=Z.X and Y=Z.Y
for xml path('')
) PieceCells
Que dan esta salida
X Y PieceCells
1 1 (1,1)(2,1)(2,2)(3,2)
3 4 (3,4)(4,4)
5 6 (5,6)
7 5 (7,5)(8,5)(9,5)
8 1 (10,1)(8,1)(8,2)(9,1)(9,2)(9,3)
