Nqueens without relying on global state (no backtracking)

8queens_noglobal.py

def twoD_from_nD(l):
    for i in l:
        if len([x for x in i if type(x) is list]) > 0:
            yield from twoD_from_nD(i)
        else:
            yield i

def threatened(solution, column):
    if column in solution:
        return True
    
    j = 1
    for i in range(len(solution), 0, -1):
        if abs(column - solution[i-1]) == j:
            return True
        j += 1
        
    return False

def nqueens(n, solution=[]):
    if len(solution) == n:
        return solution
    
    paths = []
    for column in range(n):
        if not threatened(solution, column):
            paths.append(nqueens(n, solution + [column]))
    
    paths =  [p for p in paths if len(p) != 0]
        
    if len(solution) == 0: # base case
        return [i for i in twoD_from_nD(paths)]
    
    return paths
    
print(nqueens(8))

nqueens.js

var {range} = require('range')
        
function isThreatened(board, pos) {
  return board.includes(pos) ||
         board.any((e, i, a) =>
           a.length - i === Math.abs(e - pos)
         )
}
      
function nqueens(n, board=[]) {
  let moves = range(n).filter(e=>
    !isThreatened(board, e)
  )
        
  return board.length === n - 1
    ? moves
    : moves.map(move=>
        nqueens(n, board.concat([move])).map(sol=>
          [move].concat(sol)
        )
      ).reduce((acc, cur) => acc.concat(cur), []);
}

nqueens_noglobal.rkt

#lang racket

; decided to try in Lisp now and make it more pure-functional (no state anywhere!)

(require srfi/1) ; gives us drop-right

(define (horizontal-threat? board column)
  (member column board))

(define (diagonal-threat? board column (distance 1))
  (if (zero? (length board))
      false
      (if (= (abs (- column (last board)))
             distance)
          true
          (diagonal-threat? (drop-right board 1) column (+ distance 1)))))

(define (threatened? board column)
  (or (horizontal-threat? board column)
      (diagonal-threat? board column)))

(define (group-into n l)
  (if (empty? l) l (cons (take l n) (group-into n (list-tail l n)))))

(define (nqueens n (board '()))
  (if (= (length board) n)
      board                 
      (let ((solutions
             (map (λ (col) (nqueens n (append board (list col))))
                  (filter (λ (col)
                            (not (threatened? board col)))
                          (range n)))))
        (if (empty? board) ; base case
            (group-into n (flatten solutions))
            solutions))))

(length (nqueens 8))