;; The first three lines of this file were inserted by DrScheme. They record metadata
;; about the language level of this file in a form that our tools can easily process.
#reader(lib "htdp-intermediate-lambda-reader.ss" "lang")((modname |28.2|) (read-case-sensitive #t) (teachpacks ((lib "draw.ss" "teachpack" "htdp") (lib "arrow.ss" "teachpack" "htdp") (lib "gui.ss" "teachpack" "htdp"))) (htdp-settings #(#t constructor repeating-decimal #f #t none #f ((lib "draw.ss" "teachpack" "htdp") (lib "arrow.ss" "teachpack" "htdp") (lib "gui.ss" "teachpack" "htdp")))))
;A row is either
;1. empty or
;2. (cons bool ro)
;where bool is a boolean (true/false), and ro is a row.
;A chessboard is either
;1. empty or
;2. (cons r cb)
;where r is a row and cb is a chessboard.
;Specifically, an nxn chessboard is a (listof (listof booleans)) such that the length of each element in the chessboard is the same as the length of the chessboard itself. That is, the chessboard is square. A false value in a chessboard represents a tile that is either occupied by a queen or threatened by one; a true value represents an available square for the non-threatened placement of a new chess piece.
;build-board : N (N N -> boolean) -> board
;Creates a square chessboard with dimensions n by n, with the i x j position filled with (f i j) where f is a function that returns a boolean given the two indices. Each time we build a row that is cols wide. The board's first entry is the top left corner, 1 x 1 (not 0 x 0).
;build-board : N N (N N -> boolean) -> board
;Creates a chessboard with dimensions rows by cols, with the i x j position filled with (f i j) where f is a function that returns a boolean given the two indices. Each time we build a row that is cols wide. Build-board utilizes structural recursion on rows, and thus must ultimately terminate.
;board-ref : board N[>=1] N[>=1] -> board
;Returns the value of the i x j entry in a-board.
;threatened? : posn posn -> boolean
;Determine if posn1 can threaten posn2.
;threatened-loq? : posn (listof posns) -> boolean
;Determine if aposn is threatened by aloq.
;vertical : posn posn -> boolean
;Given posn1 and posn2, determine if the two posns lie in the same vertical column.
;horizontal : posn posn -> boolean
;Given posn1 and posn2, determine if the two posns lie in the same horizontal row.
;diagonal : posn posn -> boolean
;Determines if posn1 and posn2 lie on a diagonal. If two posns lie on a negative-sloping diagonal, then their difference is a multiple of (1,1). If two posns lie on a positive-sloping diagonal, their difference is a multiple of (1,-1). In general, two posns lie on the same diagonal if the absolute value of the differences between the coordinates are equal.
(define (build-board n f)
(local ((define (build-board-rows-cols rows cols f)
(cond
[(or (zero? rows)
(zero? cols)) empty]
[else (append (build-board-rows-cols (sub1 rows) cols f)
(list (build-list cols (lambda (x) (f rows (+ x 1))))))])))
(build-board-rows-cols n n f)))
(define (board-ref a-board i j)
(cond
[(> i 1) (board-ref (rest a-board) (sub1 i) j)]
[else (list-ref (first a-board) (- j 1))]))
(define (threatened? posn1 posn2)
(local ((define (vertical posn1 posn2)
(= (posn-y posn1)
(posn-y posn2)))
(define (horizontal posn1 posn2)
(= (posn-x posn1)
(posn-x posn2)))
(define (diagonal posn1 posn2)
(= (abs (- (posn-x posn1)
(posn-x posn2)))
(abs (- (posn-y posn1)
(posn-y posn2))))))
(or (vertical posn1 posn2)
(horizontal posn1 posn2)
(diagonal posn1 posn2))))
(define (threatened-loq? aposn aloq)
(ormap (lambda (aqueen) (threatened? aposn aqueen)) aloq))
(define (build-board-loq n aloq)
(build-board n
(lambda (row col)
(cond
[(threatened-loq? (make-posn row col) aloq) false]
[else true]))))
;placement : N (listof posns) -> board or false
;Place n queens on a square 8x8 chessboard, returning the board if the placement is possible and false otherwise.
;place-queen-spaces : N (listof posns) (listof posns) -> (listof posns) or false
;Given n and aloq, return a new (listof posns) with a new queen placed if possible. Otherwise, return false.
;place-queen : N (listof posns) -> (listof posns)
;Given n and aloq, return a new (listof posns) with a new queen placed if possible. Otherwise, return false
;place-queen-spaces : N (listof posns) (listof posns) -> (listof posns)
;Place n queens in the remaining spaces such that
;build-board-loq : n (listof posns) -> board
;Builds an n by n board with occupied or threatened squares filled in given by aloq (a list of queens represented by (listof posns)).
#|
(define (placement n aloq)
(build-board-loq 8 (place-queen n empty)))
|#
(define (test-place-queen n)
(place-queen n empty))
(define (place-queen n aloq)
(cond
[(zero? n) aloq]
[else (local ((define spaces (empty-spaces dim dim aloq))
(define new-loq (place-queen-spaces n spaces aloq)))
(cond
[(boolean? new-loq) false]
[else new-loq]))]))
(define (place-queen-spaces n spaces aloq)
(cond
[(zero? n) aloq]
[(empty? spaces) false]
[else
(local ((define first-guess (place-queen (sub1 n) (cons (first spaces) aloq))))
(cond
[(boolean? first-guess)
(place-queen-spaces n (rest spaces) aloq)]
[else (place-queen (sub1 n) (cons (first spaces) aloq))]))]))
;empty-spaces : N N (listof posns) -> (listof posns)
;Given aloq, determine the empty spaces on an mxn chessboard.
(define (empty-spaces m n aloq)
(local ((define posn-list (create-posn-list m n)))
(filter (lambda (p) (not (threatened-loq? p aloq))) posn-list)))
;Tests
;(empty-spaces 8 8 (list (make-posn 4 1)
; (make-posn 8 5)))
;create-posn-list : N N -> (listof posns)
;Given rows and cols, creates a (listof posns) representing the chessboard of dimensions rows by cols. Each element represents the index of a tile in the rows by cols chessboard.
(define (create-posn-list rows cols)
(cond
[(= rows 0) empty]
[(> rows 0) (append (create-posn-list (sub1 rows) cols)
(build-list cols (lambda (c) (make-posn rows (+ c 1)))))]))
(define dim 10)
(test-place-queen dim)