Problem 8 hetman??w
kwiecień 13th, 2008 at 12:59 pm (scheme, algorytmy)
Dzisiaj rozwiÄ?zaÄ? nam przysz??o klasyczne zadanie programistyczne: problem 8 hetman??w. Szablon kodu podany zosta?? w tre??ci zadania, za?? do nas nale??y dopisanie trzech brakujÄ?cych definicji: sta??ej empty-board, i dw??ch procedur: safe? i adjoin-position.
W zadaniu korzystamy z kilku funkcji zdefiniowanych wcze??niej. SÄ? to filter, accumulate, flatmap i enumerate-interval.
Zaczniemy od implementacji zbioru pozycji na szachownicy. Na potrzeby zadania w zupe??no??ci wystarczy u??ycie pary liczb jako pozycji. Szachownica bÄ?dzie za?? po prostu listÄ? takich par.
(define empty-board nil)
(define (make-position row col) (cons row col))
(define position-row car)
(define position-column cdr)
Przy tej implementacji dodanie nowej pozycji do zbioru nie jest trudne:
;; Dodaj na szachownice hetmana w pozycji row/col.
(define (adjoin-position row col board)
(cons (make-position row col) board))
Implementacja procedury safe? wymaga trochÄ? wiÄ?cej zachodu. Dla wygody skorzysta??em z kilku funkcji pomocniczych ze SRFI-1.
(require (only (lib “1.ss” “srfi”) any every find for-each))
;; Zwroc #t jezeli obie pozycje leza w tej samej kolumnie.
(define (same-column? position-1 position-2)
(= (position-column position-1) (position-column position-2)))
;; Zwroc #t jezeli obie pozycje leza w tym samym wierszu.
(define (same-row? position-1 position-2)
(= (position-row position-1) (position-row position-2)))
;; Zwroc #t jezeli obie pozycje leza na tej samej przekatnej.
(define (same-diagonal? position-1 position-2)
(= (abs (- (position-column position-1)
(position-column position-2)))
(abs (- (position-row position-1)
(position-row position-2)))))
;; Zwroc #t jezeli obie pozycje posiadaja te same wspolrzedne.
(define (same-position? position-1 position-2)
(and (same-column? position-1 position-2)
(same-row? position-1 position-2)))
;; Zwroc #t jezeli na szachownicy stoi hetman w podanej pozycji.
(define (position-on-board? position board)
(any (lambda (board-position) (same-position? position board-position)) board))
;; Zwroc #t jezeli hetman postawiony w podanej kolumnie nie szachuje zadnego
;; z pozostalych na szachownicy.
(define (safe? col board)
;; Hetman znajdujacy sie w podanej kolumnie.
(define queen-added (find (lambda (position)
(= (position-column position) col))
board))
;; Zwroc #t jezeli podane dwa hetmany szachuja sie.
(define (in-check? queen-1 queen-2)
(or (same-row? queen-1 queen-2)
(same-column? queen-1 queen-2)
(same-diagonal? queen-1 queen-2)))
(every (lambda (other-queen)
(or (same-position? other-queen queen-added)
(not (in-check? other-queen queen-added))))
board))
W celu wizualizacji rozwiÄ?za?? u??y??em nastÄ?pujÄ?cych funkcji:
;; Wyswietl rozwiazanie dla podanej szachownicy o boku k.
(define (display-board board k)
(for-each
(lambda (row)
(begin
(for-each
(lambda (col)
(display
(if (position-on-board? (make-position row col) board) “# “ “. “)))
(enumerate-interval 1 k))
(newline)))
(enumerate-interval 1 k)))
;; Wyswietl wszystkie rozwiazania dla szachownicy o boku k.
(define (display-results k)
(for-each
(lambda (board)
(begin
(display-board board k)
(newline)))
(queens k)))
By zobaczyÄ? rozwiÄ?zania dla standardowej szachownicy 8×8, wystarczy wykonaÄ? poni??sze polecenie:
(display-results 8)