Eight Queens Problem Solved using Common Table Expressions

eight_queens.sql

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;

script.py

#!/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