8-26 碁石の固まりを出力

SQLパズル

goishiテーブル
Color  X   Y
-----  --  --
Black  B   1
Black  B   2
Black  B   3
Black  B   4
Black  B   5
Black  C   4
Black  D   5
Black  E   4
Black  F   3
Black  F   4
Black  F   5
Black  G   4
White  C   2
White  D   2
White  D   3
White  D   4
White  F   1
White  F   2
White  G   2

　ＡＢＣＤＥＦＧ
１┳●┳┳┳○┓
２╋●○○╋○○
３╋●╋○╋●┫
４╋●●○●●●
５╋╋╋●╋●┫

碁石のつながり情報を示す連番を付与して出力する。

出力結果
GID  Color  X  Y
---  ----- -- --
  1  Black  B  1
  1  Black  B  2
  1  Black  B  3
  1  Black  B  4
  1  Black  B  5
  1  Black  C  4
  2  Black  D  5
  3  Black  E  4
  3  Black  F  3
  3  Black  F  4
  3  Black  F  5
  3  Black  G  4
  1  White  C  2
  1  White  D  2
  1  White  D  3
  1  White  D  4
  2  White  F  1
  2  White  F  2
  2  White  G  2

データ作成スクリプト

create table goishi(Color,X,Y) as
select 'Black','B','1' from dual union
select 'Black','B','2' from dual union
select 'Black','B','3' from dual union
select 'Black','B','4' from dual union
select 'Black','B','5' from dual union
select 'Black','C','4' from dual union
select 'Black','D','5' from dual union
select 'Black','E','4' from dual union
select 'Black','F','3' from dual union
select 'Black','F','4' from dual union
select 'Black','F','5' from dual union
select 'Black','G','4' from dual union
select 'White','C','2' from dual union
select 'White','D','2' from dual union
select 'White','D','3' from dual union
select 'White','D','4' from dual union
select 'White','F','1' from dual union
select 'White','F','2' from dual union
select 'White','G','2' from dual;

SQL

--■■■group byを使わない方法■■■
select dense_rank() over(partition by RootColor order by GID) as GID,
RootColor as Color,RootX as X,RootY as Y
from (select RootColor,RootX,RootY,LV,
      min(UKey) over(partition by RootColor,RootX,RootY) as GID
      from (select connect_by_root color as RootColor,
            connect_by_root X as RootX,
            connect_by_root Y as RootY,
            Level as LV,UKey
              from (select color,X,Y,Row_Number() over(order by color,X,Y) as UKey from goishi)
            connect by nocycle prior color = color
                           and abs(ascii(prior X) - ascii(X)) + abs(prior Y - Y) = 1))
where LV=1
order by Color,GID,X,Y;

--■■■group byを使う方法■■■
select dense_rank() over(partition by RootColor order by GID) as GID,
RootColor as Color,RootX as X,RootY as Y
from (select RootColor,RootX,RootY,min(UKey) as GID
      from (select connect_by_root color as RootColor,
            connect_by_root X as RootX,
            connect_by_root Y as RootY,
            UKey
              from (select color,X,Y,Row_Number() over(order by color,X,Y) as UKey from goishi)
            connect by nocycle prior color = color
                           and abs(ascii(prior X) - ascii(X)) + abs(prior Y - Y) = 1)
      group by RootColor,RootX,RootY)
order by Color,GID,X,Y;

解説

一旦、Row_Number関数でユニークキーを付与して、
その大小関係のdenseなrankを連番としています。
なお、RowIDで大小関係を定義してもいいです。

囲碁ソフトで実際に使ってるアルゴリズム

10-233 移動可能な経路ごとに連番付与

---