;; Dato astratto "Scacchiera"
;;
;; Operazioni:
;;
;;   (empty-board <size>)                :  number -> board
;;
;;   (board-size <board>)                :  board -> number
;;
;;   (assigned-rows <board>)             :  board -> number
;;
;;   (safe-next? <board> <column>)       :  board x index -> boolean
;;
;;   (add-next-queen! <board> <column>)  :  board x index -> board
;;
;;   (remove-last-queen! <board>)        :  board -> board
;;
;;   (arrangement <board>)               :  board -> arrangement


;; Problema delle "n regine" (numero di soluzioni)
;;
;; Programma che applica il paradigma imperativo
;; (da confrontare con la versione funzionale)


(define queens-arrangements
  (lambda (n)
    (queens-completions (empty-board n))
    ))


(define queens-completions
  (lambda (board)
    (if (= (assigned-rows board) (board-size board))
        (begin
          (show! (arrangement board))  ; visualizza la soluzione
          1
          )
        (next-row-trials 1 board)
        )
    ))


(define next-row-trials
  (lambda (c board)
    (let ((depth-completions
           (if (safe-next? board c)            ; (*)
               (begin
                 (add-next-queen! board c)     ; cambia lo stato
                 (let ((n (queens-completions board)))
                   (remove-last-queen! board)  ; ripristina lo stato...
                   n)
                 )
               0)
          ))
      (if (< c (board-size board))  ; ...per cercare altre soluzioni
          (+ depth-completions (next-row-trials (+ c 1) board))
          depth-completions
          ))
    ))

;; (*) Perche' non cosi'? :
;;
;;           ...   ...
;;         (if (safe-next? board c)
;;             (begin
;;               (add-next-queen! board c)
;;               (queens-completions board)
;;               )
;;             0)
;;           ...   ...
;;
;; Prova ad eseguire questa versione (scorretta) del programma
;; per 1, 2, 3, 4, 5, 6, 7, 8:
;;
;;   (queens-arrangements 1)
;;
;;   (queens-arrangements 2)
;;
;;   (queens-arrangements 3)
;;
;;     ...   ...
;;
;;   (queens-arrangements 8)
;;
;; I valori corretti sono, rispettivamente:
;;
;;   1, 0, 0, 2, 10, 4, 40, 92


;; Realizzazione del dato astratto "Scacchiera"

(define empty-board
  (lambda (size)
    (let ((board (make-vector 6))
          )
      (vector-set! board 0  ; 1) posizioni: lista indici di colonna
                   (make-vector size 0))
      (vector-set! board 1  ; 1) colonne libere
                   (make-vector size #t))
      (vector-set! board 2  ; 1) diagonali \ libere
                   (make-vector (- (* 2 size) 1) #t))
      (vector-set! board 3  ; 1) diagonali / libere
                   (make-vector (- (* 2 size) 1) #t))
      (vector-set! board 4  ; 3) dimensione della scacchiera
                   size)
      (vector-set! board 5  ; 4) righe assegnate
                   0)
      board
      )
    ))


(define board-size
  (lambda (board)
    (vector-ref board 4)
    ))

(define assigned-rows
  (lambda (board)
    (vector-ref board 5)
    ))

(define safe-next?
  (lambda (board col)  ; la posizione <row,col> e' disponibile?
    (let ((row (+ (assigned-rows board) 1))
          (size (board-size board))
          )
      (and
       (vector-ref (free-columns    board) (- col 1))
       (vector-ref (free-down-diags board) (+ (- size 1) (- row col)))
       (vector-ref (free-up-diags   board) (- (+ row col) 2))
       ))
    ))

(define add-next-queen!  ; una regina viene collocata nella scacchiera
  (lambda (board col)    ; in posizione <row,col> (disponibile)
    (let ((row (+ (assigned-rows board) 1))
          (size (board-size board))
          )
      (vector-set! (arrangement     board) (- row 1) col)
      (vector-set! (free-columns    board) (- col 1) #f)
      (vector-set! (free-down-diags board) (+ (- size 1) (- row col)) #f)
      (vector-set! (free-up-diags   board) (- (+ row col) 2) #f)
      (vector-set! board 5 row)
      )
    ))

(define remove-last-queen!  ; una regina viene tolta dalla scacchiera
  (lambda (board)
    (let ((row (assigned-rows board))
          (size (board-size board))
          )
      (let ((col (vector-ref (arrangement board) (- row 1)))
            )
        (vector-set! (arrangement     board) (- row 1) 0)
        (vector-set! (free-columns    board) (- col 1) #t)
        (vector-set! (free-down-diags board) (+ (- size 1) (- row col)) #t)
        (vector-set! (free-up-diags   board) (- (+ row col) 2) #t)
        (vector-set! board 5 (- row 1))
        ))
    ))

(define arrangement
  (lambda (board)
    (vector-ref board 0)
    ))


;; Nota per comprendere la codifica:
;; Alla riga r (= 1, 2, ..., n), corrisponde
;; l'indice di vettore r-1 (= 0, 1, ..., n-1);
;; Analogamente, alla colonna c (= 1, 2, ..., n), corrisponde
;; l'indice di vettore c-1 (= 0, 1, ..., n-1);
;; alla diagonale \ attraverso il quadrato di coordinate (r,c)
;; corrisponde l'indice di vettore r-c + n-1 (= 0, 1, ..., 2n-2)
;; perche' r-c e' invariante lungo una stessa diagonale \;
;; alla diagonale / attraverso il quadrato di coordinate (r,c)
;; corrisponde l'indice di vettore r+c - 2 (= 0, 1, ..., 2n-2)
;; perche' r+c e' invariante lungo una stessa diagonale /.


(define free-columns
  (lambda (board)
    (vector-ref board 1)
    ))

(define free-down-diags
  (lambda (board)
    (vector-ref board 2)
    ))

(define free-up-diags
  (lambda (board)
    (vector-ref board 3)
    ))


(define show!
  (lambda (obj)
    (display obj)
    (newline)
    ))