Problem 8 hetmanów

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)

Strumienie danych

Testowanie

Ćwiczenia na deser

W poszukiwaniu idealnej formy

« Wcześniejsze wpisy · Nowsze wpisy »