A outra resposta já é bastante longa, então estou deixando como está. Esta resposta é muito melhor, mais simples e também correta, enquanto a outra tem alguns casos extremos que produzirão uma resposta errada - deixarei esse exercício para o leitor.
Nota:As quebras de linha são adicionadas para maior clareza. O bloco inteiro é uma única 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
A primeira etapa é configurar uma expressão de tabela recursiva "walker" que começará em cada célula e percorrerá o máximo possível sem refazer nenhuma etapa. Certificar-se de que as células não sejam revisitadas é feito usando a coluna visitada, que armazena cada célula visitada de todos os pontos de partida. Em particular, esta condição
AND W.Visited NOT LIKE '%('+right(P.X,3)+','+right(P.Y,3)+')%' rejeita células que já visitou. Para entender como o resto funciona, você precisa olhar o resultado gerado pelo CTE "Walker" executando "Select * from Walker order by StartX, StartY" após o CTE. Uma "peça" com 5 células aparece em pelo menos 5 grupos, cada um com um
(StartX,StartY) diferente , mas cada grupo tem todos os 5 (X,Y) peças com diferentes percursos "Visitados". A subconsulta (Z) usa um LEFT JOIN + IS NULL para eliminar os grupos até a única linha em cada grupo que contém a "primeira coordenada XY", definida pela condição
Other.StartX=W.StartX and Other.StartY=W.StartY
and (Other.Y<W.Y or (Other.Y=W.Y and Other.X<W.X))
A intenção é para cada célula que pode ser visitada a partir de (StartX, StartY), comparar uma com outra célula do mesmo grupo e encontrar a célula onde NENHUMA OUTRA célula está em uma linha superior, ou se elas estão no mesma linha, está à esquerda desta célula. Isso ainda nos deixa com muitos resultados, no entanto. Considere apenas um pedaço de 2 células em (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) ******
2 linhas permanecem com a "primeira coordenada XY" de (3,4), marcada com
****** . Nós só precisamos de uma linha, então usamos Row_Number e já que estamos numerando, podemos ir para o mais longo Visited caminho, o que nos daria quantos as células dentro da peça que podemos obter. A consulta externa final simplesmente pega as primeiras linhas (RN=1) de cada grupo semelhante (X,Y).
Para mostrar TODAS as células de cada peça, altere a linha
select X, Y, Visited
no meio 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 dão esta saída
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)
