Last active
August 25, 2019 01:04
Nqueens without relying on global state (no backtracking)
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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)) |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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), []); | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#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)) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment