| Sysop: | Amessyroom |
|---|---|
| Location: | Fayetteville, NC |
| Users: | 23 |
| Nodes: | 6 (0 / 6) |
| Uptime: | 52:41:06 |
| Calls: | 583 |
| Files: | 1,139 |
| D/L today: |
179 files (27,921K bytes) |
| Messages: | 111,617 |
#-(and) "
P90 (**) Eight queens problem
This is a classical problem in computer science. The objective is
to place eight queens on a chessboard so that no two queens are
attacking each other; i.e., no two queens are in the same row, the
same column, or on the same diagonal.
Hint: Represent the positions of the queens as a list of numbers
1..N. Example: [4,2,7,3,6,8,5,1] means that the queen in the first
column is in row 4, the queen in the second column is in row 2,
etc. Use the generate-and-test paradigm.
"
(defvar *queen-board-size* 8)
;; We could use a list instead of a vector with fill pointer to
;; represent the board. But instead of incrementing and decrementing
;; the fill-pointer, we would have to cons or free a cell.
(defun make-board (&optional (initial-size 0))
(make-array *queen-board-size* :fill-pointer initial-size :element-type 'fixnum
:initial-element -1))
(defun put-queen (board col row)
(assert (= col (length board)))
(vector-push row board))
(defun remove-queen (board col)
(assert (= (1+ col) (length board)))
(vector-pop board))
(defun valid-queen-position-p (board col row)
(or (zerop col)
(and
;; not on the same row:
(notany (lambda (other-row) (= other-row row)) board)
;; not on a same diagonal:
(loop
:for other-col :below col
:for other-row :across board
:never (= (- col other-col) (abs (- row other-row)))))))
(defun queens ()
(let ((results '()))
(labels ((collect (board)
(push (copy-seq board) results))
(search-queens (board col)
(if (= col *queen-board-size*)
(collect board)
(loop
:for row :below *queen-board-size*
:when (valid-queen-position-p board col row)
:do (progn
(put-queen board col row)
(search-queens board (1+ col))
(remove-queen board col))))))
(search-queens (make-board) 0)
results)))
#-(and) "
P90 (**) Eight queens problem
This is a classical problem in computer science. The objective is
to place eight queens on a chessboard so that no two queens are
attacking each other; i.e., no two queens are in the same row, the
same column, or on the same diagonal.
Hint: Represent the positions of the queens as a list of numbers
1..N. Example: [4,2,7,3,6,8,5,1] means that the queen in the first
column is in row 4, the queen in the second column is in row 2,
etc. Use the generate-and-test paradigm.
"
(defvar *queen-board-size* 8)
;; We could use a list instead of a vector with fill pointer to
;; represent the board. But instead of incrementing and decrementing
;; the fill-pointer, we would have to cons or free a cell.
(defun make-board (&optional (initial-size 0))
(make-array *queen-board-size* :fill-pointer initial-size :element-type 'fixnum
:initial-element -1))
(defun put-queen (board col row)
(assert (= col (length board)))
(vector-push row board))
(defun remove-queen (board col)
(assert (= (1+ col) (length board)))
(vector-pop board))
(defun valid-queen-position-p (board col row)
(or (zerop col)
(and
;; not on the same row:
(notany (lambda (other-row) (= other-row row)) board)
;; not on a same diagonal:
(loop
:for other-col :below col
:for other-row :across board
:never (= (- col other-col) (abs (- row other-row)))))))
(defun queens ()
(let ((results '()))
(labels ((collect (board)
(push (copy-seq board) results))
(search-queens (board col)
(if (= col *queen-board-size*)
(collect board)
(loop
:for row :below *queen-board-size*
:when (valid-queen-position-p board col row)
:do (progn
(put-queen board col row)
(search-queens board (1+ col))
(remove-queen board col))))))
(search-queens (make-board) 0)
results)))
MatzLisp:
(0..7).to_a.permutation{|b|
p b if [:+,:-].all?{|op| 8==b.map.with_index(&op).uniq.size}}
[0, 4, 7, 5, 2, 6, 1, 3]
[0, 5, 7, 2, 6, 3, 1, 4]
[0, 6, 3, 5, 7, 1, 4, 2]
[0, 6, 4, 7, 1, 3, 5, 2]
[1, 3, 5, 7, 2, 0, 6, 4]
[1, 4, 6, 0, 2, 7, 5, 3]
[1, 4, 6, 3, 0, 7, 5, 2]
[1, 5, 0, 6, 3, 7, 2, 4]
[1, 5, 7, 2, 0, 3, 6, 4]
[1, 6, 2, 5, 7, 4, 0, 3]
[1, 6, 4, 7, 0, 3, 5, 2]
[1, 7, 5, 0, 2, 4, 6, 3]
[2, 0, 6, 4, 7, 1, 3, 5]
[2, 4, 1, 7, 0, 6, 3, 5]
[2, 4, 1, 7, 5, 3, 6, 0]
[2, 4, 6, 0, 3, 1, 7, 5]
[2, 4, 7, 3, 0, 6, 1, 5]
[2, 5, 1, 4, 7, 0, 6, 3]
[2, 5, 1, 6, 0, 3, 7, 4]
[2, 5, 1, 6, 4, 0, 7, 3]
[2, 5, 3, 0, 7, 4, 6, 1]
[2, 5, 3, 1, 7, 4, 6, 0]
[2, 5, 7, 0, 3, 6, 4, 1]
[2, 5, 7, 0, 4, 6, 1, 3]
[2, 5, 7, 1, 3, 0, 6, 4]
[2, 6, 1, 7, 4, 0, 3, 5]
[2, 6, 1, 7, 5, 3, 0, 4]
[2, 7, 3, 6, 0, 5, 1, 4]
[3, 0, 4, 7, 1, 6, 2, 5]
[3, 0, 4, 7, 5, 2, 6, 1]
[3, 1, 4, 7, 5, 0, 2, 6]
[3, 1, 6, 2, 5, 7, 0, 4]
[3, 1, 6, 2, 5, 7, 4, 0]
[3, 1, 6, 4, 0, 7, 5, 2]
[3, 1, 7, 4, 6, 0, 2, 5]
[3, 1, 7, 5, 0, 2, 4, 6]
[3, 5, 0, 4, 1, 7, 2, 6]
[3, 5, 7, 1, 6, 0, 2, 4]
[3, 5, 7, 2, 0, 6, 4, 1]
[3, 6, 0, 7, 4, 1, 5, 2]
[3, 6, 2, 7, 1, 4, 0, 5]
[3, 6, 4, 1, 5, 0, 2, 7]
[3, 6, 4, 2, 0, 5, 7, 1]
[3, 7, 0, 2, 5, 1, 6, 4]
[3, 7, 0, 4, 6, 1, 5, 2]
[3, 7, 4, 2, 0, 6, 1, 5]
[4, 0, 3, 5, 7, 1, 6, 2]
[4, 0, 7, 3, 1, 6, 2, 5]
[4, 0, 7, 5, 2, 6, 1, 3]
[4, 1, 3, 5, 7, 2, 0, 6]
[4, 1, 3, 6, 2, 7, 5, 0]
[4, 1, 5, 0, 6, 3, 7, 2]
[4, 1, 7, 0, 3, 6, 2, 5]
[4, 2, 0, 5, 7, 1, 3, 6]
[4, 2, 0, 6, 1, 7, 5, 3]
[4, 2, 7, 3, 6, 0, 5, 1]
[4, 6, 0, 2, 7, 5, 3, 1]
[4, 6, 0, 3, 1, 7, 5, 2]
[4, 6, 1, 3, 7, 0, 2, 5]
[4, 6, 1, 5, 2, 0, 3, 7]
[4, 6, 1, 5, 2, 0, 7, 3]
[4, 6, 3, 0, 2, 7, 5, 1]
[4, 7, 3, 0, 2, 5, 1, 6]
[4, 7, 3, 0, 6, 1, 5, 2]
[5, 0, 4, 1, 7, 2, 6, 3]
[5, 1, 6, 0, 2, 4, 7, 3]
[5, 1, 6, 0, 3, 7, 4, 2]
[5, 2, 0, 6, 4, 7, 1, 3]
[5, 2, 0, 7, 3, 1, 6, 4]
[5, 2, 0, 7, 4, 1, 3, 6]
[5, 2, 4, 6, 0, 3, 1, 7]
[5, 2, 4, 7, 0, 3, 1, 6]
[5, 2, 6, 1, 3, 7, 0, 4]
[5, 2, 6, 1, 7, 4, 0, 3]
[5, 2, 6, 3, 0, 7, 1, 4]
[5, 3, 0, 4, 7, 1, 6, 2]
[5, 3, 1, 7, 4, 6, 0, 2]
[5, 3, 6, 0, 2, 4, 1, 7]
[5, 3, 6, 0, 7, 1, 4, 2]
[5, 7, 1, 3, 0, 6, 4, 2]
[6, 0, 2, 7, 5, 3, 1, 4]
[6, 1, 3, 0, 7, 4, 2, 5]
[6, 1, 5, 2, 0, 3, 7, 4]
[6, 2, 0, 5, 7, 4, 1, 3]
[6, 2, 7, 1, 4, 0, 5, 3]
[6, 3, 1, 4, 7, 0, 2, 5]
[6, 3, 1, 7, 5, 0, 2, 4]
[6, 4, 2, 0, 5, 7, 1, 3]
[7, 1, 3, 0, 6, 4, 2, 5]
[7, 1, 4, 2, 0, 6, 3, 5]
[7, 2, 0, 5, 1, 4, 6, 3]
[7, 3, 0, 2, 5, 1, 6, 4]