;; 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)