Faster CTE solution to eight queens puzzle in sqlite

nqueens.sql

-- follows this blog post:
-- http://www.andreas-dewes.de/en/2015/queens-of-the-data-age-abusing-common-table-expressions-to-solve-the-eight-queens-problem-in-sql/
-- but takes under a second, instead of many minutes
--
-- main idea: represent board as permutation of string '12345678',
-- where character at position i is a queen at position (i, s[i])
-- then only check diagonal attacks
-- (this approach is the one traditionally taken in eg Prolog)

with recursive
  positions(i) as (
    values(1)
    union select all
    i+1 from positions where i < 8
    ),
  queens(board, nqueens) as (
    values('', 1)
    union
    select
      substr(board, 1, nqueens - 1) || ps.i, nqueens + 1 as nqueens
    from positions as ps, queens
    where
      nqueens <= 8
    and not exists (
      select 1
      from positions as checkpos
      where checkpos.i < nqueens and
        (cast(substr(board, checkpos.i, 1) as int) = ps.i or
         abs(substr(board, checkpos.i, 1) - ps.i) = abs(nqueens - checkpos.i))
      limit 1
    )
  )
select count(board), nqueens from queens where nqueens = 9;

awesome