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-intermediate-lambda-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 #f #t none #f ((lib "draw.ss" "teachpack" "htdp") (lib "arrow.ss" "teachpack" "htdp") (lib "gui.ss" "teachpack" "htdp")))))
4 ;A row is either
5 ;1. empty or
6 ;2. (cons bool ro)
7 ;where bool is a boolean (true/false), and ro is a row.
8 
9 ;A chessboard is either
10 ;1. empty or
11 ;2. (cons r cb)
12 ;where r is a row and cb is a chessboard.
13 
14 ;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.
15 
16 ;build-board : N (N N -> boolean) -> board
17 ;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).
18 
19 ;build-board : N N (N N -> boolean) -> board
20 ;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.
21 
22 ;board-ref : board N[>=1] N[>=1] -> board
23 ;Returns the value of the i x j entry in a-board.
24 
25 ;threatened? : posn posn -> boolean
26 ;Determine if posn1 can threaten posn2.
27 
28 ;threatened-loq? : posn (listof posns) -> boolean
29 ;Determine if aposn is threatened by aloq.
30 
31 ;vertical : posn posn -> boolean
32 ;Given posn1 and posn2, determine if the two posns lie in the same vertical column.
33 
34 ;horizontal : posn posn -> boolean
35 ;Given posn1 and posn2, determine if the two posns lie in the same horizontal row.
36 
37 ;diagonal : posn posn -> boolean
38 ;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.
39 
40 
41 
42 (define (build-board n f)
43   (local ((define (build-board-rows-cols rows cols f)
44             (cond
45               [(or (zero? rows)
46                    (zero? cols)) empty]
47               [else (append (build-board-rows-cols (sub1 rows) cols f)
48                             (list (build-list cols (lambda (x) (f rows (+ x 1))))))])))
49     (build-board-rows-cols n n f)))
50 
51 (define (board-ref a-board i j)
52   (cond
53     [(> i 1) (board-ref (rest a-board) (sub1 i) j)]
54     [else (list-ref (first a-board) (- j 1))]))
55 
56 (define (threatened? posn1 posn2)
57   (local ((define (vertical posn1 posn2)
58             (= (posn-y posn1)
59                (posn-y posn2)))
60           (define (horizontal posn1 posn2)
61             (= (posn-x posn1)
62                (posn-x posn2)))
63           (define (diagonal posn1 posn2)
64             (= (abs (- (posn-x posn1)
65                        (posn-x posn2)))
66                (abs (- (posn-y posn1)
67                        (posn-y posn2))))))
68     (or (vertical posn1 posn2)
69         (horizontal posn1 posn2)
70         (diagonal posn1 posn2))))
71 
72 (define (threatened-loq? aposn aloq)
73   (ormap (lambda (aqueen) (threatened? aposn aqueen)) aloq))
74 
75 (define (build-board-loq n aloq)
76   (build-board n
77                (lambda (row col)
78                  (cond
79                    [(threatened-loq? (make-posn row col) aloq) false]
80                    [else true]))))
81 
82 ;placement : N (listof posns) -> board or false
83 ;Place n queens on a square 8x8 chessboard, returning the board if the placement is possible and false otherwise.
84 
85 ;place-queen-spaces : N (listof posns) (listof posns) -> (listof posns) or false
86 ;Given n and aloq, return a new (listof posns) with a new queen placed if possible.  Otherwise, return false.
87 
88 ;place-queen : N (listof posns) -> (listof posns)
89 ;Given n and aloq, return a new (listof posns) with a new queen placed if possible.  Otherwise, return false
90 
91 ;place-queen-spaces : N (listof posns) (listof posns) -> (listof posns)
92 ;Place n queens in the remaining spaces such that
93 
94 ;build-board-loq : n (listof posns) -> board
95 ;Builds an n by n board with occupied or threatened squares filled in given by aloq (a list of queens represented by (listof posns)).
96 #|
97 (define (placement n aloq)
98   (build-board-loq 8 (place-queen n empty)))
99 |#
100 
101 (define (test-place-queen n)
102   (place-queen n empty))
103 
104 (define (place-queen n aloq)
105   (cond
106     [(zero? n) aloq]
107     [else (local ((define spaces (empty-spaces dim dim aloq))
108                   (define new-loq (place-queen-spaces n spaces aloq)))
109             (cond  
110               [(boolean? new-loq) false]
111               [else new-loq]))]))
112 
113 (define (place-queen-spaces n spaces aloq)
114   (cond
115     [(zero? n) aloq]
116     [(empty? spaces) false]
117     [else
118      (local ((define first-guess (place-queen (sub1 n) (cons (first spaces) aloq))))
119        (cond
120          [(boolean? first-guess)
121           (place-queen-spaces n (rest spaces) aloq)]
122          [else (place-queen (sub1 n) (cons (first spaces) aloq))]))]))
123 
124 ;empty-spaces : N N (listof posns) -> (listof posns)
125 ;Given aloq, determine the empty spaces on an mxn chessboard.
126 
127 (define (empty-spaces m n aloq)
128   (local ((define posn-list (create-posn-list m n)))
129     (filter (lambda (p) (not (threatened-loq? p aloq))) posn-list)))
130 
131 ;Tests
132 ;(empty-spaces 8 8 (list (make-posn 4 1)
133 ;                          (make-posn 8 5)))
134 
135 ;create-posn-list : N N -> (listof posns)
136 ;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.
137 
138 (define (create-posn-list rows cols)
139   (cond
140     [(= rows 0) empty]
141     [(> rows 0) (append (create-posn-list (sub1 rows) cols)
142                         (build-list cols (lambda (c) (make-posn rows (+ c 1)))))]))
143 
144 (define dim 10)
145 (test-place-queen dim)