#lang racket

(require "common.scm")

(define empty-board '())

(define (adjoin-position row col positions)
  (cons (cons row col) positions))

(define (safe? qcol positions)
  (define rest (cdr positions))
  (cond ((empty? rest) #t)
         (define position (car positions))
         (define drow (abs (- (car position) (caar rest))))
         (and (nor (= drow 0) (= drow (abs (- qcol (cdar rest)))))
              (safe? qcol (cons position (cdr rest)))))))

(define (queens board-size)
  (define (queen-cols k)
    (if (= k 0)
        (list empty-board)
         (lambda (positions) (safe? k positions))
          (lambda (new-row)
             (lambda (rest-of-queens)
               (adjoin-position new-row k rest-of-queens))
             (queen-cols (- k 1))))
          (enumerate-interval 1 board-size)))))
  (queen-cols board-size))

; tests

(define start-time (current-inexact-milliseconds))
(define result (queens 8))
(define elapsed-time (/ (- (current-inexact-milliseconds) start-time) 1000))
(display elapsed-time)
(display " seconds")
(length result)
;(map (lambda (positions) 
;       (map (lambda (position)
;              (car position)) positions))
;     result)


9.541095947265624 seconds

(queen-cols (- k 1)) is calculated 8 times for every \(k\). So \(T(Normal)=8^m\cdot T(Louis)\), where \(1<m<8\). The comparison of calculation times gives \(m\approx 3.75\) on my computer.