N-queens project
<racket> (require racket/list) ;gets list-ref, take and drop
- queens.rkt
- Brute force queens solver
- The board is a 4x4 grid of SQUARES.
- There are 4 ROWS and 4 COLUMNS,
- The idea of the game is to place 4 queens in the board
- Not Atacking each other
- =================
- Data definitions
- Val is Boolean
- Board is (listof Val) that is squares long
- interp.
- Visually a board is a 4x4 array of squares, where each square
- has a row and column number (r, c). But we represent it as a
- single flat list, in which the rows are layed out one after
- another in a linear fashion. (See interp. of Pos below for how
- we convert back and forth between (r, c) and position in a board.)
- Pos is Natural[0, 15]
- interp.
- the position of a square on the board, for a given p, then
- - the row is (quotient p 4)
- - the column is (remainder p 4)
- Convert 0-based row and column to Pos
(define (r-c->pos r c) (+ (* r 4) c)) ;helpful for writing tests
- =================
- Constants
(define SIZE 4) ;n queens in n x n board
(define BDZ
(list 0 0 0 0 ;empty
0 0 0 0
0 0 0 0
0 0 0 0))
(define BD0
(list 1 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0))
(define BD1
(list 0 1 0 0
0 0 0 0
0 0 0 0
0 0 0 0))
(define BD2
(list 0 0 1 0
0 0 0 0
0 0 0 0
0 0 0 0))
(define BD3
(list 0 0 0 1
0 0 0 0
0 0 0 0
0 0 0 0))
(define BD4
(list 0 0 0 0
1 0 0 0
0 0 0 0
0 0 0 0))
(define BD5
(list 0 0 0 0
0 1 0 0
0 0 0 0
0 0 0 0))
(define BD0r
(list 0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 1))
(define BD1r
(list 0 0 0 0
0 0 0 0
0 0 0 0
0 0 1 0))
(define BD2r
(list 0 0 0 0
0 0 0 0
0 0 0 0
0 1 0 0))
(define BD3r
(list 0 0 0 0
0 0 0 0
0 0 0 0
1 0 0 0))
(define BD4r
(list 0 0 0 0
0 0 0 0
0 0 0 1
0 0 0 0))
(define BD5r
(list 0 0 0 0
0 0 0 0
0 0 1 0
0 0 0 0))
(define BD21
(list 1 1 0 0
0 0 0 0
0 0 0 0
0 0 0 0))
(define BD22
(list 1 0 1 0
0 0 0 0
0 0 0 0
0 0 0 0))
(define BD23
(list 1 0 0 1
0 0 0 0
0 0 0 0
0 0 0 0))
(define BD24
(list 1 0 0 0
1 0 0 0
0 0 0 0
0 0 0 0))
(define BD25
(list 1 0 0 0
0 1 0 0
0 0 0 0
0 0 0 0))
(define BD26
(list 1 0 0 0
0 0 1 0
0 0 0 0
0 0 0 0))
(define BD31
(list 1 1 1 0
0 0 0 0
0 0 0 0
0 0 0 0))
(define BD32
(list 0 0 0 0
0 0 0 0
1 1 1 0
0 0 0 0))
(define BD33
(list 0 0 0 0
0 0 0 0
0 0 0 0
1 1 1 0))
(define BD34
(list 0 0 0 0
0 0 0 0
0 0 0 0
0 1 1 1))
(define BD41
(list 0 1 0 0
0 0 1 0
0 1 0 0
0 1 0 0))
(define BD42
(list 0 1 1 0
0 0 0 0
0 1 0 0
0 0 1 0))
(define BD43
(list 1 1 1 1
0 0 0 0
0 0 0 0
0 0 0 0))
- =================
- Functions
- (listof Board) -> (listof Board)
- produce list containing only valid boards
(check-expect (keep-only-valid (list BD41 BD42 BD43))
empty)
- (define (keep-only-valid lobd) empty) ;stub
(define (keep-only-valid lobd)
(filter valid-board? lobd))
- Board -> Boolean ...
- produce true if queens do not attack inside a board
(check-expect (valid-board? BD1) true) (check-expect (valid-board? BD2) true) (check-expect (valid-board? BD3) true) (check-expect (valid-board? BD4) true) (check-expect (valid-board? BD5) true)
(define (valid-board? bd) false) ; stub
- Board -> Pos
- produces the position of the blank square after the last QUEEN of board
- ASSUME
- the board in not empty
(check-expect (afterLastQueen BDZ) 0) (check-expect (afterLastQueen BD0) 1) (check-expect (afterLastQueen BD21) 2) (check-expect (afterLastQueen BD22) 3) (check-expect (afterLastQueen BD23) 4) (check-expect (afterLastQueen BD24) 5) (check-expect (afterLastQueen BD25) 6) (check-expect (afterLastQueen BD26) 7) (check-expect (afterLastQueen BD31) 3) (check-expect (afterLastQueen BD32) 11) (check-expect (afterLastQueen BD33) 15) (check-expect (afterLastQueen BD34) 16) (check-expect (afterLastQueen BD41) 14) (check-expect (afterLastQueen BD42) 15) (check-expect (afterLastQueen BD43) 4)
- (define (afterLastQueen bd) 0) ;stub
(define (afterLastQueen bd)
(if (andmap zero? bd)
0
(- 17 (findNextEmpty (reverseBoard bd)))))
- Board -> Board
- produces reversed board
- ASSUME
- Board is not empty list
(check-expect (reverseBoard BD0) BD0r) (check-expect (reverseBoard BD1) BD1r) (check-expect (reverseBoard BD2) BD2r) (check-expect (reverseBoard BD3) BD3r) (check-expect (reverseBoard BD4) BD4r) (check-expect (reverseBoard BD5) BD5r)
- (define (reverseBoard bd) BD0) ;stub
(define (reverseBoard bd)
(reverse bd))
- Board -> Pos
- produces the position of the first blank square of board
- ASSUME
- the board has at least one blank square
(check-expect (findNextEmpty BD0) 1) (check-expect (findNextEmpty BD1) 2) (check-expect (findNextEmpty BD2) 3) (check-expect (findNextEmpty BD3) 4) (check-expect (findNextEmpty BD4) 5) (check-expect (findNextEmpty BD5) 6)
- (define (findNextEmpty bd) 0) ;stub
(define (findNextEmpty bd)
(cond [(empty? bd) 0]
[else
(if (equal? 1 (first bd))
1
(+ (findNextEmpty (rest bd)) 1) ) ]))
- Board Pos -> Boolean
- Produce True if QUEEN at given position on board.
- Assume
- ...
(check-expect (read-square BD1 1) true) (check-expect (read-square BD1 2) false) (check-expect (read-square BD43 3) true)
(define (read-square bd p) (equal? 1 (list-ref bd p)))
- Board Pos -> Board
- produce new board with QUEEN (1) at given position
(check-expect (fill-square BDZ (r-c->pos 0 0) ) BD0) (check-expect (fill-square BD31 (r-c->pos 0 3) ) BD43)
(define (fill-square bd p )
(append (take bd p)
(list 1)
(drop bd (add1 p))))
- Board -> (listof Board)
- produce 16 boards, with new queen
(check-expect (add-qn BDZ)
(list (fill-square BDZ 0 )
(fill-square BDZ 1 )
(fill-square BDZ 2 )
(fill-square BDZ 3 )
(fill-square BDZ 4 )
(fill-square BDZ 5 )
(fill-square BDZ 6 )
(fill-square BDZ 7 )
(fill-square BDZ 8 )
(fill-square BDZ 9 )
(fill-square BDZ 10 )
(fill-square BDZ 11 )
(fill-square BDZ 12 )
(fill-square BDZ 13 )
(fill-square BDZ 14 )
(fill-square BDZ 15 )))
(check-expect (add-qn BD3)
(list (fill-square BD3 0 )
(fill-square BD3 1 )
(fill-square BD3 2 )
(fill-square BD3 3 )
(fill-square BD3 4 )
(fill-square BD3 5 )
(fill-square BD3 6 )
(fill-square BD3 7 )
(fill-square BD3 8 )
(fill-square BD3 9 )
(fill-square BD3 10 )
(fill-square BD3 11 )
(fill-square BD3 12 )
(fill-square BD3 13 )
(fill-square BD3 14 )
(fill-square BD3 15 )))
(check-expect (add-qn BD4)
(list (fill-square BD4 0 )
(fill-square BD4 1 )
(fill-square BD4 2 )
(fill-square BD4 3 )
(fill-square BD4 4 )
(fill-square BD4 5 )
(fill-square BD4 6 )
(fill-square BD4 7 )
(fill-square BD4 8 )
(fill-square BD4 9 )
(fill-square BD4 10 )
(fill-square BD4 11 )
(fill-square BD4 12 )
(fill-square BD4 13 )
(fill-square BD4 14 )
(fill-square BD4 15 )))
- (define (add-qn p bd) empty) ;stub
(define (add-qn bd)
(local [(define (build-one n)
(fill-square bd (+ n 0) ))]
(build-list 16 build-one)))
</racket>
