1 12687dd9 2023-08-04 jrmu ;; The first three lines of this file were inserted by DrScheme. They record metadata
2 12687dd9 2023-08-04 jrmu ;; about the language level of this file in a form that our tools can easily process.
3 12687dd9 2023-08-04 jrmu #reader(lib "htdp-advanced-reader.ss" "lang")((modname |29.3|) (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 #t #t none #f ((lib "draw.ss" "teachpack" "htdp") (lib "arrow.ss" "teachpack" "htdp") (lib "gui.ss" "teachpack" "htdp")))))
5 12687dd9 2023-08-04 jrmu Exercise 29.3.14. Develop a vector representation for chessboards of size n × n for n in N. Then develop the following two functions on chessboards:
7 12687dd9 2023-08-04 jrmu ;; build-board : N (N N -> boolean) -> board
8 12687dd9 2023-08-04 jrmu ;; to create a board of size n x n,
9 12687dd9 2023-08-04 jrmu ;; fill each position with indices i and j with (f i j)
10 12687dd9 2023-08-04 jrmu (define (build-board n f) ...)
12 12687dd9 2023-08-04 jrmu ;; board-ref : board N N -> boolean
13 12687dd9 2023-08-04 jrmu ;; to access a position with indices i, j on a-board
14 12687dd9 2023-08-04 jrmu (define (board-ref a-board i j) ...)
16 12687dd9 2023-08-04 jrmu ;A row is a (vectorof booleans), and the length of the row (the number of columns) is equivalent to (vector-length r), where r is the row in question.
18 12687dd9 2023-08-04 jrmu ;A chessboard is a (vectorof (vectorof booleans)). Specifically, an rxc chessboard has a length of r, and each element in the chessboard has a length of c. A chessboard is square if r is the same as c. A false value in a chessboard represents a tile that is either occupied by a queen or threatened by one, whereas a true value represents an available square for the non-threatened placement of a new chess piece.
20 12687dd9 2023-08-04 jrmu ;build-board : N (N N -> boolean) -> board
21 12687dd9 2023-08-04 jrmu ;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).
23 12687dd9 2023-08-04 jrmu (define (build-board n f)
24 12687dd9 2023-08-04 jrmu (build-board-rows-cols n n f))
26 12687dd9 2023-08-04 jrmu ;build-board : N N (N N -> boolean) -> board
27 12687dd9 2023-08-04 jrmu ;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.
29 12687dd9 2023-08-04 jrmu (define (build-board-rows-cols rows cols f)
30 12687dd9 2023-08-04 jrmu (build-vector rows (lambda (r)
31 12687dd9 2023-08-04 jrmu (build-vector cols (lambda (c) (f (+ r 1) (+ c 1)))))))
33 12687dd9 2023-08-04 jrmu ;board-ref : board N[>=1] N[>=1] -> board
34 12687dd9 2023-08-04 jrmu ;Returns the value of the i x j entry in a-board.
36 12687dd9 2023-08-04 jrmu (define (board-ref a-board i j)
37 12687dd9 2023-08-04 jrmu (vector-ref (vector-ref a-board (sub1 i)) (sub1 j)))
42 12687dd9 2023-08-04 jrmu (define board-1 (vector (vector true true true)
43 12687dd9 2023-08-04 jrmu (vector false true false)))
44 12687dd9 2023-08-04 jrmu (vector (vector (board-ref board-1 1 1) (board-ref board-1 1 2) (board-ref board-1 1 3))
45 12687dd9 2023-08-04 jrmu (vector (board-ref board-1 2 1) (board-ref board-1 2 2) (board-ref board-1 2 3)))
48 12687dd9 2023-08-04 jrmu ;threatened? : posn posn -> boolean
49 12687dd9 2023-08-04 jrmu ;Determine if posn1 can threaten posn2.
51 12687dd9 2023-08-04 jrmu (define (threatened? posn1 posn2)
52 12687dd9 2023-08-04 jrmu (local ((define (vertical posn1 posn2)
53 12687dd9 2023-08-04 jrmu (= (posn-y posn1)
54 12687dd9 2023-08-04 jrmu (posn-y posn2)))
55 12687dd9 2023-08-04 jrmu (define (horizontal posn1 posn2)
56 12687dd9 2023-08-04 jrmu (= (posn-x posn1)
57 12687dd9 2023-08-04 jrmu (posn-x posn2)))
58 12687dd9 2023-08-04 jrmu (define (diagonal posn1 posn2)
59 12687dd9 2023-08-04 jrmu (= (abs (- (posn-x posn1)
60 12687dd9 2023-08-04 jrmu (posn-x posn2)))
61 12687dd9 2023-08-04 jrmu (abs (- (posn-y posn1)
62 12687dd9 2023-08-04 jrmu (posn-y posn2))))))
63 12687dd9 2023-08-04 jrmu (or (vertical posn1 posn2)
64 12687dd9 2023-08-04 jrmu (horizontal posn1 posn2)
65 12687dd9 2023-08-04 jrmu (diagonal posn1 posn2))))
69 12687dd9 2023-08-04 jrmu ;threatened-loq? : posn (listof posns) -> boolean
70 12687dd9 2023-08-04 jrmu ;Determine if aposn is threatened by aloq.
72 12687dd9 2023-08-04 jrmu ;vertical : posn posn -> boolean
73 12687dd9 2023-08-04 jrmu ;Given posn1 and posn2, determine if the two posns lie in the same vertical column.
75 12687dd9 2023-08-04 jrmu ;horizontal : posn posn -> boolean
76 12687dd9 2023-08-04 jrmu ;Given posn1 and posn2, determine if the two posns lie in the same horizontal row.
78 12687dd9 2023-08-04 jrmu ;diagonal : posn posn -> boolean
79 12687dd9 2023-08-04 jrmu ;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.
84 12687dd9 2023-08-04 jrmu (build-board-rows-cols 8 8 (lambda (x y)
86 12687dd9 2023-08-04 jrmu [(< x y) true]
87 12687dd9 2023-08-04 jrmu [else false])))
90 12687dd9 2023-08-04 jrmu (define (place-queen n aloq)
92 12687dd9 2023-08-04 jrmu [(zero? n) aloq]
93 12687dd9 2023-08-04 jrmu [else (local ((define spaces (empty-spaces dim dim aloq))
94 12687dd9 2023-08-04 jrmu (define new-loq (place-queen-spaces n spaces aloq)))
96 12687dd9 2023-08-04 jrmu [(boolean? new-loq) false]
97 12687dd9 2023-08-04 jrmu [else new-loq]))]))
99 12687dd9 2023-08-04 jrmu (define (place-queen-spaces n spaces aloq)
101 12687dd9 2023-08-04 jrmu [(zero? n) aloq]
102 12687dd9 2023-08-04 jrmu [(empty? spaces) false]
104 12687dd9 2023-08-04 jrmu (local ((define first-guess (place-queen (sub1 n) (cons (first spaces) aloq))))
106 12687dd9 2023-08-04 jrmu [(boolean? first-guess)
107 12687dd9 2023-08-04 jrmu (place-queen-spaces n (rest spaces) aloq)]
108 12687dd9 2023-08-04 jrmu [else first-guess]))]))
110 12687dd9 2023-08-04 jrmu (define (threatened-loq? aposn aloq)
111 12687dd9 2023-08-04 jrmu (ormap (lambda (aqueen) (threatened? aposn aqueen)) aloq))
113 12687dd9 2023-08-04 jrmu ;empty-spaces : N N (listof posns) -> (listof posns)
114 12687dd9 2023-08-04 jrmu ;Given aloq, determine the empty spaces on an mxn chessboard.
116 12687dd9 2023-08-04 jrmu (define (empty-spaces m n aloq)
117 12687dd9 2023-08-04 jrmu (local ((define posn-list (create-posn-list m n)))
118 12687dd9 2023-08-04 jrmu (filter (lambda (p) (not (threatened-loq? p aloq))) posn-list)))
120 12687dd9 2023-08-04 jrmu ;create-posn-list : N N -> (listof posns)
121 12687dd9 2023-08-04 jrmu ;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.
123 12687dd9 2023-08-04 jrmu (define (create-posn-list rows cols)
125 12687dd9 2023-08-04 jrmu [(= rows 0) empty]
126 12687dd9 2023-08-04 jrmu [(> rows 0) (append (create-posn-list (sub1 rows) cols)
127 12687dd9 2023-08-04 jrmu (build-list cols (lambda (c) (make-posn rows (+ c 1)))))]))
129 12687dd9 2023-08-04 jrmu (define dim 8)
130 12687dd9 2023-08-04 jrmu (place-queen dim empty)
136 12687dd9 2023-08-04 jrmu (define (build-board-loq n aloq)
137 12687dd9 2023-08-04 jrmu (build-board n
138 12687dd9 2023-08-04 jrmu (lambda (row col)
140 12687dd9 2023-08-04 jrmu [(threatened-loq? (make-posn row col) aloq) false]
141 12687dd9 2023-08-04 jrmu [else true]))))
143 12687dd9 2023-08-04 jrmu ;placement : N (listof posns) -> board or false
144 12687dd9 2023-08-04 jrmu ;Place n queens on a square 8x8 chessboard, returning the board if the placement is possible and false otherwise.
146 12687dd9 2023-08-04 jrmu ;place-queen-spaces : N (listof posns) (listof posns) -> (listof posns) or false
147 12687dd9 2023-08-04 jrmu ;Given n and aloq, return a new (listof posns) with a new queen placed if possible. Otherwise, return false.
149 12687dd9 2023-08-04 jrmu ;place-queen : N (listof posns) -> (listof posns)
150 12687dd9 2023-08-04 jrmu ;Given n and aloq, return a new (listof posns) with a new queen placed if possible. Otherwise, return false
152 12687dd9 2023-08-04 jrmu ;place-queen-spaces : N (listof posns) (listof posns) -> (listof posns)
153 12687dd9 2023-08-04 jrmu ;Place n queens in the remaining spaces such that
155 12687dd9 2023-08-04 jrmu ;build-board-loq : n (listof posns) -> board
156 12687dd9 2023-08-04 jrmu ;Builds an n by n board with occupied or threatened squares filled in given by aloq (a list of queens represented by (listof posns)).
158 12687dd9 2023-08-04 jrmu (define (placement n aloq)
159 12687dd9 2023-08-04 jrmu (build-board-loq 8 (place-queen n empty)))
162 12687dd9 2023-08-04 jrmu (define (test-place-queen n)
163 12687dd9 2023-08-04 jrmu (place-queen n empty))
166 12687dd9 2023-08-04 jrmu ;empty-spaces : N N (listof posns) -> (listof posns)
167 12687dd9 2023-08-04 jrmu ;Given aloq, determine the empty spaces on an mxn chessboard.
169 12687dd9 2023-08-04 jrmu (define (empty-spaces m n aloq)
170 12687dd9 2023-08-04 jrmu (local ((define posn-list (create-posn-list m n)))
171 12687dd9 2023-08-04 jrmu (filter (lambda (p) (not (threatened-loq? p aloq))) posn-list)))
174 12687dd9 2023-08-04 jrmu ;(empty-spaces 8 8 (list (make-posn 4 1)
175 12687dd9 2023-08-04 jrmu ; (make-posn 8 5)))
178 12687dd9 2023-08-04 jrmu (define dim 10)
179 12687dd9 2023-08-04 jrmu (test-place-queen dim)
