1 ;; The first three lines of this file were inserted by DrScheme. They record metadata
2 ;; about the language level of this file in a form that our tools can easily process.
3 #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")))))
4 #|
5 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:
6 
7 ;; build-board : N (N N  ->  boolean)  ->  board
8 ;; to create a board of size n x n, 
9 ;; fill each position with indices i and j with (f i j)
10 (define (build-board n f) ...)
11 
12 ;; board-ref : board N N  ->  boolean
13 ;; to access a position with indices i, j on a-board
14 (define (board-ref a-board i j) ...)
15 |#
16 ;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.
17 
18 ;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.
19 
20 ;build-board : N (N N -> boolean) -> board
21 ;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).
22 
23 (define (build-board n f)
24   (build-board-rows-cols n n f))
25 
26 ;build-board : N N (N N -> boolean) -> board
27 ;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.
28 
29 (define (build-board-rows-cols rows cols f)
30   (build-vector rows (lambda (r)
31                        (build-vector cols (lambda (c) (f (+ r 1) (+ c 1)))))))
32 
33 ;board-ref : board N[>=1] N[>=1] -> board
34 ;Returns the value of the i x j entry in a-board.
35 
36 (define (board-ref a-board i j)
37   (vector-ref (vector-ref a-board (sub1 i)) (sub1 j)))
38 
39 #|
40 ;Tests
41 
42 (define board-1 (vector (vector true true true)
43                         (vector false true false)))
44 (vector (vector (board-ref board-1 1 1) (board-ref board-1 1 2) (board-ref board-1 1 3))
45         (vector (board-ref board-1 2 1) (board-ref board-1 2 2) (board-ref board-1 2 3)))
46 |#
47 
48 ;threatened? : posn posn -> boolean
49 ;Determine if posn1 can threaten posn2.
50 
51 (define (threatened? posn1 posn2)
52   (local ((define (vertical posn1 posn2)
53             (= (posn-y posn1)
54                (posn-y posn2)))
55           (define (horizontal posn1 posn2)
56             (= (posn-x posn1)
57                (posn-x posn2)))
58           (define (diagonal posn1 posn2)
59             (= (abs (- (posn-x posn1)
60                        (posn-x posn2)))
61                (abs (- (posn-y posn1)
62                        (posn-y posn2))))))
63     (or (vertical posn1 posn2)
64         (horizontal posn1 posn2)
65         (diagonal posn1 posn2))))
66 
67 
68 
69 ;threatened-loq? : posn (listof posns) -> boolean
70 ;Determine if aposn is threatened by aloq.
71 
72 ;vertical : posn posn -> boolean
73 ;Given posn1 and posn2, determine if the two posns lie in the same vertical column.
74 
75 ;horizontal : posn posn -> boolean
76 ;Given posn1 and posn2, determine if the two posns lie in the same horizontal row.
77 
78 ;diagonal : posn posn -> boolean
79 ;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.
80 
81 
82 #|
83 ;Test
84 (build-board-rows-cols 8 8 (lambda (x y)
85                              (cond
86                                [(< x y) true]
87                                [else false])))
88 |#
89 
90 (define (place-queen n aloq)
91   (cond
92     [(zero? n) aloq]
93     [else (local ((define spaces (empty-spaces dim dim aloq))
94                   (define new-loq (place-queen-spaces n spaces aloq)))
95             (cond  
96               [(boolean? new-loq) false]
97               [else new-loq]))]))
98 
99 (define (place-queen-spaces n spaces aloq)
100   (cond
101     [(zero? n) aloq]
102     [(empty? spaces) false]
103     [else
104      (local ((define first-guess (place-queen (sub1 n) (cons (first spaces) aloq))))
105        (cond
106          [(boolean? first-guess)
107           (place-queen-spaces n (rest spaces) aloq)]
108          [else first-guess]))]))
109 
110 (define (threatened-loq? aposn aloq)
111   (ormap (lambda (aqueen) (threatened? aposn aqueen)) aloq))
112 
113 ;empty-spaces : N N (listof posns) -> (listof posns)
114 ;Given aloq, determine the empty spaces on an mxn chessboard.
115 
116 (define (empty-spaces m n aloq)
117   (local ((define posn-list (create-posn-list m n)))
118     (filter (lambda (p) (not (threatened-loq? p aloq))) posn-list)))
119 
120 ;create-posn-list : N N -> (listof posns)
121 ;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.
122 
123 (define (create-posn-list rows cols)
124   (cond
125     [(= rows 0) empty]
126     [(> rows 0) (append (create-posn-list (sub1 rows) cols)
127                         (build-list cols (lambda (c) (make-posn rows (+ c 1)))))]))
128 
129 (define dim 8)
130 (place-queen dim empty)
131 
132 
133 #|
134 
135 
136 (define (build-board-loq n aloq)
137   (build-board n
138                (lambda (row col)
139                  (cond
140                    [(threatened-loq? (make-posn row col) aloq) false]
141                    [else true]))))
142 
143 ;placement : N (listof posns) -> board or false
144 ;Place n queens on a square 8x8 chessboard, returning the board if the placement is possible and false otherwise.
145 
146 ;place-queen-spaces : N (listof posns) (listof posns) -> (listof posns) or false
147 ;Given n and aloq, return a new (listof posns) with a new queen placed if possible.  Otherwise, return false.
148 
149 ;place-queen : N (listof posns) -> (listof posns)
150 ;Given n and aloq, return a new (listof posns) with a new queen placed if possible.  Otherwise, return false
151 
152 ;place-queen-spaces : N (listof posns) (listof posns) -> (listof posns)
153 ;Place n queens in the remaining spaces such that
154 
155 ;build-board-loq : n (listof posns) -> board
156 ;Builds an n by n board with occupied or threatened squares filled in given by aloq (a list of queens represented by (listof posns)).
157 #|
158 (define (placement n aloq)
159   (build-board-loq 8 (place-queen n empty)))
160 |#
161 
162 (define (test-place-queen n)
163   (place-queen n empty))
164 
165 
166 ;empty-spaces : N N (listof posns) -> (listof posns)
167 ;Given aloq, determine the empty spaces on an mxn chessboard.
168 
169 (define (empty-spaces m n aloq)
170   (local ((define posn-list (create-posn-list m n)))
171     (filter (lambda (p) (not (threatened-loq? p aloq))) posn-list)))
172 
173 ;Tests
174 ;(empty-spaces 8 8 (list (make-posn 4 1)
175 ;                          (make-posn 8 5)))
176 
177 
178 (define dim 10)
179 (test-place-queen dim)
180 |#