Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Eight Queens Problem Solved using Common Table Expressions
WITH RECURSIVE
positions(i) as (
VALUES(0)
UNION SELECT ALL
i+1 FROM positions WHERE i < 63
),
solutions(board, n_queens) AS (
SELECT '----------------------------------------------------------------', cast(0 AS bigint)
FROM positions
UNION
SELECT
substr(board, 1, i) || '*' || substr(board, i+2),n_queens + 1 as n_queens
FROM positions AS ps, solutions
WHERE n_queens < 8
AND substr(board,1,i) != '*'
AND NOT EXISTS (
SELECT 1 FROM positions WHERE
substr(board,i+1,1) = '*' AND
(
i % 8 = ps.i %8 OR
cast(i / 8 AS INT) = cast(ps.i / 8 AS INT) OR
cast(i / 8 AS INT) + (i % 8) = cast(ps.i / 8 AS INT) + (ps.i % 8) OR
cast(i / 8 AS INT) - (i % 8) = cast(ps.i / 8 AS INT) - (ps.i % 8)
)
LIMIT 1
)
ORDER BY n_queens DESC --remove this if you want to use Postgres instead (ORDER BY in CTEs is not supported there)
)
SELECT board,n_queens FROM solutions WHERE n_queens = 8;
#!/usr/bin/env python
import sqlite3
import sys
conn = sqlite3.connect(':memory:')
version = sqlite3.sqlite_version.split(".")
if version[1] < 8 or version[2] < 3:
print "Warning: Your SQLite version might be too old to run this query! You need at least 3.8.3."
with open('eight_queens.sql','r') as script_file:
sql_script = script_file.read()
c = conn.cursor()
DIM = 8
print "Calculating solutions, please stand by..."
result = c.execute(sql_script)
cnt = 0
for row in result:
cnt+=1
print "\n".join([row[0][i*DIM:i*DIM+DIM] for i in range(len(row[0])/DIM)]),"\n"
assert cnt == 92
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.