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-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")))))
4 12687dd9 2023-08-04 jrmu ;A row is either
6 12687dd9 2023-08-04 jrmu ;2. (cons bool ro)
7 12687dd9 2023-08-04 jrmu ;where bool is a boolean (true/false), and ro is a row.
9 12687dd9 2023-08-04 jrmu ;A chessboard is either
10 12687dd9 2023-08-04 jrmu ;1. empty or
11 12687dd9 2023-08-04 jrmu ;2. (cons r cb)
12 12687dd9 2023-08-04 jrmu ;where r is a row and cb is a chessboard.
14 12687dd9 2023-08-04 jrmu ;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.
16 12687dd9 2023-08-04 jrmu ;build-board : N (N N -> boolean) -> board
17 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).
19 12687dd9 2023-08-04 jrmu ;build-board : N N (N N -> boolean) -> board
20 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. Each time we build a row that is cols wide. Build-board utilizes structural recursion on rows, and thus must ultimately terminate.
22 12687dd9 2023-08-04 jrmu ;board-ref : board N[>=1] N[>=1] -> board
23 12687dd9 2023-08-04 jrmu ;Returns the value of the i x j entry in a-board.
25 12687dd9 2023-08-04 jrmu ;threatened? : posn posn -> boolean
26 12687dd9 2023-08-04 jrmu ;Determine if posn1 can threaten posn2.
28 12687dd9 2023-08-04 jrmu ;threatened-loq? : posn (listof posns) -> boolean
29 12687dd9 2023-08-04 jrmu ;Determine if aposn is threatened by aloq.
31 12687dd9 2023-08-04 jrmu ;vertical : posn posn -> boolean
32 12687dd9 2023-08-04 jrmu ;Given posn1 and posn2, determine if the two posns lie in the same vertical column.
34 12687dd9 2023-08-04 jrmu ;horizontal : posn posn -> boolean
35 12687dd9 2023-08-04 jrmu ;Given posn1 and posn2, determine if the two posns lie in the same horizontal row.
37 12687dd9 2023-08-04 jrmu ;diagonal : posn posn -> boolean
38 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.
42 12687dd9 2023-08-04 jrmu (define (build-board n f)
43 12687dd9 2023-08-04 jrmu (local ((define (build-board-rows-cols rows cols f)
45 12687dd9 2023-08-04 jrmu [(or (zero? rows)
46 12687dd9 2023-08-04 jrmu (zero? cols)) empty]
47 12687dd9 2023-08-04 jrmu [else (append (build-board-rows-cols (sub1 rows) cols f)
48 12687dd9 2023-08-04 jrmu (list (build-list cols (lambda (x) (f rows (+ x 1))))))])))
49 12687dd9 2023-08-04 jrmu (build-board-rows-cols n n f)))
51 12687dd9 2023-08-04 jrmu (define (board-ref a-board i j)
53 12687dd9 2023-08-04 jrmu [(> i 1) (board-ref (rest a-board) (sub1 i) j)]
54 12687dd9 2023-08-04 jrmu [else (list-ref (first a-board) (- j 1))]))
56 12687dd9 2023-08-04 jrmu (define (threatened? posn1 posn2)
57 12687dd9 2023-08-04 jrmu (local ((define (vertical posn1 posn2)
58 12687dd9 2023-08-04 jrmu (= (posn-y posn1)
59 12687dd9 2023-08-04 jrmu (posn-y posn2)))
60 12687dd9 2023-08-04 jrmu (define (horizontal posn1 posn2)
61 12687dd9 2023-08-04 jrmu (= (posn-x posn1)
62 12687dd9 2023-08-04 jrmu (posn-x posn2)))
63 12687dd9 2023-08-04 jrmu (define (diagonal posn1 posn2)
64 12687dd9 2023-08-04 jrmu (= (abs (- (posn-x posn1)
65 12687dd9 2023-08-04 jrmu (posn-x posn2)))
66 12687dd9 2023-08-04 jrmu (abs (- (posn-y posn1)
67 12687dd9 2023-08-04 jrmu (posn-y posn2))))))
68 12687dd9 2023-08-04 jrmu (or (vertical posn1 posn2)
69 12687dd9 2023-08-04 jrmu (horizontal posn1 posn2)
70 12687dd9 2023-08-04 jrmu (diagonal posn1 posn2))))
72 12687dd9 2023-08-04 jrmu (define (threatened-loq? aposn aloq)
73 12687dd9 2023-08-04 jrmu (ormap (lambda (aqueen) (threatened? aposn aqueen)) aloq))
75 12687dd9 2023-08-04 jrmu (define (build-board-loq n aloq)
76 12687dd9 2023-08-04 jrmu (build-board n
77 12687dd9 2023-08-04 jrmu (lambda (row col)
79 12687dd9 2023-08-04 jrmu [(threatened-loq? (make-posn row col) aloq) false]
80 12687dd9 2023-08-04 jrmu [else true]))))
82 12687dd9 2023-08-04 jrmu ;placement : N (listof posns) -> board or false
83 12687dd9 2023-08-04 jrmu ;Place n queens on a square 8x8 chessboard, returning the board if the placement is possible and false otherwise.
85 12687dd9 2023-08-04 jrmu ;place-queen-spaces : N (listof posns) (listof posns) -> (listof posns) or false
86 12687dd9 2023-08-04 jrmu ;Given n and aloq, return a new (listof posns) with a new queen placed if possible. Otherwise, return false.
88 12687dd9 2023-08-04 jrmu ;place-queen : N (listof posns) -> (listof posns)
89 12687dd9 2023-08-04 jrmu ;Given n and aloq, return a new (listof posns) with a new queen placed if possible. Otherwise, return false
91 12687dd9 2023-08-04 jrmu ;place-queen-spaces : N (listof posns) (listof posns) -> (listof posns)
92 12687dd9 2023-08-04 jrmu ;Place n queens in the remaining spaces such that
94 12687dd9 2023-08-04 jrmu ;build-board-loq : n (listof posns) -> board
95 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)).
97 12687dd9 2023-08-04 jrmu (define (placement n aloq)
98 12687dd9 2023-08-04 jrmu (build-board-loq 8 (place-queen n empty)))
101 12687dd9 2023-08-04 jrmu (define (test-place-queen n)
102 12687dd9 2023-08-04 jrmu (place-queen n empty))
104 12687dd9 2023-08-04 jrmu (define (place-queen n aloq)
106 12687dd9 2023-08-04 jrmu [(zero? n) aloq]
107 12687dd9 2023-08-04 jrmu [else (local ((define spaces (empty-spaces dim dim aloq))
108 12687dd9 2023-08-04 jrmu (define new-loq (place-queen-spaces n spaces aloq)))
110 12687dd9 2023-08-04 jrmu [(boolean? new-loq) false]
111 12687dd9 2023-08-04 jrmu [else new-loq]))]))
113 12687dd9 2023-08-04 jrmu (define (place-queen-spaces n spaces aloq)
115 12687dd9 2023-08-04 jrmu [(zero? n) aloq]
116 12687dd9 2023-08-04 jrmu [(empty? spaces) false]
118 12687dd9 2023-08-04 jrmu (local ((define first-guess (place-queen (sub1 n) (cons (first spaces) aloq))))
120 12687dd9 2023-08-04 jrmu [(boolean? first-guess)
121 12687dd9 2023-08-04 jrmu (place-queen-spaces n (rest spaces) aloq)]
122 12687dd9 2023-08-04 jrmu [else (place-queen (sub1 n) (cons (first spaces) aloq))]))]))
124 12687dd9 2023-08-04 jrmu ;empty-spaces : N N (listof posns) -> (listof posns)
125 12687dd9 2023-08-04 jrmu ;Given aloq, determine the empty spaces on an mxn chessboard.
127 12687dd9 2023-08-04 jrmu (define (empty-spaces m n aloq)
128 12687dd9 2023-08-04 jrmu (local ((define filled-board (build-board-loq n aloq))
129 12687dd9 2023-08-04 jrmu (define posn-list (create-posn-list m n)))
130 12687dd9 2023-08-04 jrmu (filter (lambda (p) (board-ref filled-board (posn-x p) (posn-y p))) posn-list)))
133 12687dd9 2023-08-04 jrmu ;create-posn-list : N N -> (listof posns)
134 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.
136 12687dd9 2023-08-04 jrmu (define (create-posn-list rows cols)
138 12687dd9 2023-08-04 jrmu [(= rows 0) empty]
139 12687dd9 2023-08-04 jrmu [(> rows 0) (append (create-posn-list (sub1 rows) cols)
140 12687dd9 2023-08-04 jrmu (build-list cols (lambda (c) (make-posn rows (+ c 1)))))]))
142 12687dd9 2023-08-04 jrmu (define dim 8)
143 12687dd9 2023-08-04 jrmu (test-place-queen dim)
