Skip to content

Instantly share code, notes, and snippets.

@yancya
Last active July 29, 2022 05:32
Show Gist options
  • Save yancya/780cbe69e15ca765ec54f8760307a2d8 to your computer and use it in GitHub Desktop.
Save yancya/780cbe69e15ca765ec54f8760307a2d8 to your computer and use it in GitHub Desktop.
エイト・クイーン問題 全解 BigQuery 版
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
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment