L'autre réponse est déjà assez longue, donc je la laisse telle quelle. Cette réponse est bien meilleure, plus simple et également correcte alors que l'autre a des cas extrêmes qui produiront une mauvaise réponse - je laisserai cet exercice au lecteur.
Remarque :des sauts de ligne sont ajoutés pour plus de clarté. Le bloc entier est une seule requête
;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
La première étape consiste à configurer une expression de table récursive "walker" qui commencera à chaque cellule et se déplacera aussi loin que possible sans revenir sur aucune étape. S'assurer que les cellules ne sont pas revisitées est fait en utilisant la colonne visitée, qui stocke chaque cellule qui a été visitée à partir de chaque point de départ. En particulier, cette condition AND W.Visited NOT LIKE '%('+right(P.X,3)+','+right(P.Y,3)+')%' rejette les cellules qu'il a déjà visitées.
Pour comprendre comment fonctionne le reste, vous devez regarder le résultat généré par le CTE "Walker" en exécutant "Select * from Walker order by StartX, StartY" après le CTE. Un "morceau" de 5 cellules apparaît dans au moins 5 groupes, chacun avec un (StartX,StartY) différent , mais chaque groupe a tous les 5 (X,Y) pièces avec différents chemins "visités".
La sous-requête (Z) utilise un LEFT JOIN + IS NULL pour réduire les groupes à la seule ligne de chaque groupe contenant la "première coordonnée XY", définie par la condition
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'intention est pour chaque cellule qui peut être visitée à partir de (StartX, StartY), de se comparer entre elles dans le même groupe, et de trouver la cellule où AUCUNE AUTRE cellule n'est sur une ligne supérieure, ou si elles sont sur le même ligne, se trouve à gauche de cette cellule. Cela nous laisse encore trop de résultats, cependant. Considérons juste une pièce à 2 cellules en (3,4) et (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) ******
2 lignes restent avec la "première coordonnée XY" de (3,4), marquée par ****** . Nous n'avons besoin que d'une seule ligne, nous utilisons donc Row_Number et puisque nous numérotons, autant opter pour le plus long Visited chemin, ce qui nous donnerait autant de les cellules dans la pièce que nous pouvons obtenir.
La requête externe finale prend simplement les premières lignes (RN=1) de chaque groupe similaire (X,Y).
Pour afficher TOUTES les cellules de chaque pièce, modifiez la ligneselect X, Y, Visited
au milieu de
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
Ce qui donne cette sortie
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)
