エイト・クイーン問題 全解 BigQuery 版

8queens.sql

CREATE TEMP FUNCTION safe_check(queens ARRAY<STRUCT<x INT64, y INT64>>) RETURNS BOOLEAN AS ((
  SELECT COUNT(x) = COUNT(DISTINCT x) AND
         COUNT(y) = COUNT(DISTINCT y) AND
         COUNT(x+y) = COUNT(DISTINCT x+y) AND
         COUNT(x-y) = COUNT(DISTINCT x-y)
    FROM UNNEST(queens)
));

CREATE TEMP FUNCTION print_queen(x INT64) RETURNS STRING AS (
  (SELECT COALESCE(STRING_AGG('.', ''), '') FROM UNNEST(GENERATE_ARRAY(1, x-1))) ||
  'Q' || 
  (SELECT COALESCE(STRING_AGG('.', ''), '') FROM UNNEST(GENERATE_ARRAY(1, 8-x)))
);

CREATE TEMP FUNCTION print_queens(queens ARRAY<STRUCT<x INT64, y INT64>>) RETURNS STRING AS ((
   SELECT STRING_AGG(print_queen(x), '\n' ORDER BY y)
     FROM UNNEST(queens) AS queen
));

WITH RECURSIVE base AS (
  SELECT x, y
            FROM UNNEST(GENERATE_ARRAY(1, 8)) AS x
                   CROSS JOIN UNNEST(GENERATE_ARRAY(1, 8)) AS y
), t AS (
  SELECT x AS q1_x, y AS q1_y,
         CAST(NULL AS INT64) AS q2_x, CAST(NULL AS INT64) AS q2_y,
         CAST(NULL AS INT64) AS q3_x, CAST(NULL AS INT64) AS q3_y,
         CAST(NULL AS INT64) AS q4_x, CAST(NULL AS INT64) AS q4_y,
         CAST(NULL AS INT64) AS q5_x, CAST(NULL AS INT64) AS q5_y,
         CAST(NULL AS INT64) AS q6_x, CAST(NULL AS INT64) AS q6_y,
         CAST(NULL AS INT64) AS q7_x, CAST(NULL AS INT64) AS q7_y,
         CAST(NULL AS INT64) AS q8_x, CAST(NULL AS INT64) AS q8_y,
    FROM base
   WHERE y = 1

   UNION ALL

  SELECT *
    FROM (SELECT q1_x, q1_y,
                 COALESCE(q2_x, base.x) AS q2_x, COALESCE(q2_y, base.y) AS q2_y,
                 COALESCE(q3_x, CASE WHEN q2_x IS NOT NULL THEN base.x END) AS q3_x,
                 COALESCE(q3_y, CASE WHEN q2_y IS NOT NULL THEN base.y END) AS q3_y,
                 COALESCE(q4_x, CASE WHEN q3_x IS NOT NULL THEN base.x END) AS q4_x,
                 COALESCE(q4_y, CASE WHEN q3_y IS NOT NULL THEN base.y END) AS q4_y,
                 COALESCE(q5_x, CASE WHEN q4_x IS NOT NULL THEN base.x END) AS q5_x,
                 COALESCE(q5_y, CASE WHEN q4_y IS NOT NULL THEN base.y END) AS q5_y,
                 COALESCE(q6_x, CASE WHEN q5_x IS NOT NULL THEN base.x END) AS q6_x,
                 COALESCE(q6_y, CASE WHEN q5_y IS NOT NULL THEN base.y END) AS q6_y,
                 COALESCE(q7_x, CASE WHEN q6_x IS NOT NULL THEN base.x END) AS q7_x,
                 COALESCE(q7_y, CASE WHEN q6_y IS NOT NULL THEN base.y END) AS q7_y,
                 COALESCE(q8_x, CASE WHEN q7_x IS NOT NULL THEN base.x END) AS q8_x,
                 COALESCE(q8_y, CASE WHEN q7_y IS NOT NULL THEN base.y END) AS q8_y,
            FROM t JOIN base ON (
                   (t.q1_y IS NOT NULL AND t.q2_y IS NULL AND base.y = 2) OR
                   (t.q2_y IS NOT NULL AND t.q3_y IS NULL AND base.y = 3) OR
                   (t.q3_y IS NOT NULL AND t.q4_y IS NULL AND base.y = 4) OR
                   (t.q4_y IS NOT NULL AND t.q5_y IS NULL AND base.y = 5) OR
                   (t.q5_y IS NOT NULL AND t.q6_y IS NULL AND base.y = 6) OR
                   (t.q6_y IS NOT NULL AND t.q7_y IS NULL AND base.y = 7) OR
                   (t.q7_y IS NOT NULL AND t.q8_y IS NULL AND base.y = 8)))
   WHERE safe_check([
           (q1_x, q1_y), (q2_x, q2_y), (q3_x, q3_y), (q4_x, q4_y),
           (q5_x, q5_y), (q6_x, q6_y), (q7_x, q7_y), (q8_x, q8_y)
         ])
)

SELECT print_queens([
         (q1_x, q1_y), (q2_x, q2_y), (q3_x, q3_y), (q4_x, q4_y),
         (q5_x, q5_y), (q6_x, q6_y), (q7_x, q7_y), (q8_x, q8_y)
       ])
  FROM t
 WHERE q8_x IS NOT NULL

README.md

これは……

エイト・クイーン問題を BigQuery の SQL で解いたコード