L'altra risposta è già piuttosto lunga, quindi la lascio così com'è. Questa risposta è molto migliore, più semplice e anche corretta, mentre l'altra presenta alcuni casi limite che produrranno una risposta sbagliata:lascerò l'esercizio al lettore.
Nota:per maggiore chiarezza vengono aggiunte interruzioni di riga. L'intero blocco è una singola query
;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
Il primo passaggio consiste nell'impostare un'espressione di tabella ricorsiva "walker" che inizierà in ogni cella e si sposterà il più lontano possibile senza ripercorrere alcun passaggio. La verifica che le celle non vengano rivisitate viene eseguita utilizzando la colonna visitata, che memorizza ogni cella che è stata visitata da ogni punto di partenza. In particolare, questa condizione AND W.Visited NOT LIKE '%('+right(P.X,3)+','+right(P.Y,3)+')%' rifiuta le celle che ha già visitato.
Per capire come funziona il resto, è necessario guardare il risultato generato dal CTE "Walker" eseguendo "Select * from Walker order by StartX, StartY" dopo il CTE. Un "pezzo" con 5 celle appare in almeno 5 gruppi, ciascuno con un diverso (StartX,StartY) , ma ogni gruppo ha tutti e 5 i (X,Y) pezzi con percorsi "Visitati" diversi.
La sottoquery (Z) usa un LEFT JOIN + IS NULL per eliminare i gruppi fino alla singola riga in ogni gruppo che contiene la "prima coordinata XY", definita dalla condizione
Other.StartX=W.StartX and Other.StartY=W.StartY
and (Other.Y<W.Y or (Other.Y=W.Y and Other.X<W.X))
L'intenzione è che ogni cella visitabile a partire da (StartX, StartY), si confronti con un'altra cella dello stesso gruppo, e trovi la cella in cui NESSUNA ALTRA cella si trova su una riga superiore, o se si trovano sulla stessa riga, si trova a sinistra di questa cella. Questo ci lascia ancora con troppi risultati, tuttavia. Considera solo un pezzo a 2 celle in (3,4) e (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) ******
Rimangono 2 righe con la "prima coordinata XY" di (3,4), contrassegnata da ****** . Abbiamo solo bisogno di una riga, quindi usiamo Row_Number e dato che stiamo numerando, potremmo anche scegliere il Visited più lungo percorso, che ci darebbe altre di le celle all'interno del pezzo come possiamo ottenere.
La query esterna finale prende semplicemente le prime righe (RN=1) da ciascun gruppo simile (X,Y).
Per mostrare TUTTE le celle di ogni pezzo, cambia la rigaselect X, Y, Visited
nel mezzo a
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
Che danno questo output
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)
