SICP 연습문제 2.42 친절한 풀이

문제

'에잇-퀸 퍼즐^{eight-queens puzzle}’은, 체스판에 퀸 여덟을 놓되 서로 공격할 수 있는 자리에 오지 못하게 두는 방법이 무엇인지 찾아내는 수수께끼다. (다시 말해서, 두 퀸이 마주보지 않도록 한 가로줄, 세로줄, 대각선 위에 퀸 두 개가 오면 안된다.) 이 수수께끼를 푸는 한 가지 방법은, 그림 2.8에서 보여주듯이 체스판을 가로지르면서 세로줄마다 하나씩 퀸을 놓는 것이다. 따라서 퀸 k-1개를 제대로 두었다고 치면, k번째 퀸은 다른 퀸을 공격하지 못하는 자리에 와야 한다.

이런 방식을 되돌이^재귀로 정리해 보면 이러하다. 퀸 k-1개를 세로줄 k-1개에 두는 방법을 모두 찾아냈다고 치자. 그렇게 찾아낸 방법 하나하나에 대하여 k번째 세로줄의 가로줄마다 k번째 퀸을 놓는다고 치고, 그 자리 값을 보탠다. 이로부터 k번째 세로줄에 있는 퀸이 공격 받지 않는 자리 값만 골라낸다. 이리하면 k개 세로줄에 퀸 k개를 안전하게 놓을 수 있는 방법을 몽땅 얻을 수 있다. 이런 과정을 계속 밟아 가면, 답 하나가 아니라 이 수수께끼를 푸는 모든 답을 얻어낼 수 있다.

이 풀이법을 queens 프로시저로 실현해 보자. queens는 퀸 n개를 n×n 체스판에 놓는다고 할 때, 얻을 수 있는 모든 답을 차례열로 묶어 낸다. queens에 갇힌 프로시저 queen-cols는 세로줄 k개에 퀸을 놓을 수 있는 모든 방법을 차례열로 묶어낸다.

(define (queens board-size)
  (define (queen-cols k)
    (if (= k 0)
        (list empty-board)
        (filter
         (lambda (positions) (safe? k positions))
         (flatmap
          (lambda (rest-of-queens)
            (map (lambda (new-row)
                   (adjoin-position new-row k rest-of-queens))
                 (enumerate-interval 1 board-size)))
          (queen-cols (- k 1))))))
  (queen-cols board-size))

이 프로시저에서 rest-of-queens는 세로줄 k-1개에 퀸 k-1개를 놓는 방법 하나를 나태내고, new-row는 k번째 세로줄에 k번째 퀸을 놓을 수 있는 가로줄을 나타낸다. 이 프로그램을 마무리 짓기 위하여, 체스판의 자리 값을 원소로 하는 집합의 표현 방식을 정하라. 그 다음, 그 집합에 새로운 가로-세로 자리 값을 집어 넣는 프로시저 adjoin-position, 또 공집합을 나타내는 프로시저 empty-board를 구현하라. 이에 아울러, k번째 퀸이 나머지 다른 퀸에서 안전한지 알아볼 수도 있도록 safe?라는 술어 프로시저도 만들어라. (이때 나머지 퀸들은 벌써 안전한 자리를 잡고 있다 치고, 새로 놓을 퀸이 안전한지만 따져보면 된다.)

문제로 부터 얻은 것

프로시저의 위치를 보고 이 프로시저가 어떤 반환값을 반환해야 하는지 추론하는 능력이 상승했습니다.
차례열을 처리하는 car, cadr, cdr 프로시저에 조금 더 익숙해질 수 있었습니다.
append에 nil을 첫번째 원소로 넣었을 때 어떤 일이 일어나는 지를 알 수 있었습니다.

문제 풀이에 필요한 프로시저들

(define (enumerate-interval low high)
  (if (> low high)
      nil
      (cons low (enumerate-interval (+ low 1) high))))

(define (accumulate op initial sequence)
  (if (null? sequence)
      initial
      (op (car sequence)
          (accumulate op initial (cdr sequence)))))

(define (flatmap proc seq)
  (accumulate append nil (map proc seq)))
  
(define (filter predicate seq)
  (cond ((null? seq) nil)
        ((predicate (car seq))
         (cons (car seq)
               (filter predicate (cdr seq))))
        (else (filter predicate (cdr seq)))))

문제풀이

저는 이 문제를 푸는데 상당히 애를 먹었습니다. 첫번째로 애를 먹은 부분은, 완성된 결과가 어떤 모양인지 문제에서 정확히 제시해주지 않은 점입니다. 완성된 queens 프로시저의 결과값 중 하나는 이렇게 생겼습니다.

((2 1) (4 2) (6 3) (1 4) (3 5) (5 6))

queens 프로시저는 모든 가능한 퀸의 위치를 flatmap을 이용해서 만들어낸 후, 그 중에서 조건에 맞는 위치들의 차례열을 필터링하는 프로시저입니다.

1. adjoin-position

adjoin-position 프로시저를 구현하기 위해서는 이 프로시저가 어떤 값을 인자로 받고 어떤 값을 반환해야 하는 지를 확인해야 합니다. 이 프로시저의 위치로 보았을때, 인자로 받는 값은 1부터 n사이의 정수값입니다. 그리고 그 정수값을 이용해서 반환해야 하는 값은, 기존의 퀸의 위치를 나타낸 차례열에 (정수값 new-row, 열 k) 쌍을 이어붙인 값입니다. 프로시저로 구현하면 아래와 같습니다.

(define (adjoin-position new-row k rest-of-queens)
  (append rest-of-queens (list (list new-row k))))

처음에 저는 (list (list new-row k)) 대신에 (list new-row k)를 넣었습니다. 이는 append의 기능을 착각해서 생긴 문제입니다. 우리가 원하는 기능은 다음과 같습니다. “((1 1) (2 2)) 쌍에 (3 3)을 넣어서 ((1 1) (2 2) (3 3))을 만드는 것” 하지만 리스트를 두번 사용하지 않으면 다음과 같은 과정을 진행해버립니다. “((1 1) (2 2)) 쌍에 (3 3)을 넣어서 ((1 1) (2 2) 3 3)을 만드는 것” append는 리스트의 원소들을 빼내서 다시 넣어주는 프로시저이기 때문에 쌍을 넣고 싶다면 list를 두번 사용해야 합니다.

2. empty-board

empty-board가 어떻게 쓰이는지를 살펴보겠습니다. empty-board가 반환해야 하는 값은, (queen-cols 0)을 의미해야 합니다. (queen-cols 0)은 프로시저 안의 flatmap에서 쓰이는데, 기존의 퀸의 위치를 나타내는 차례열에 새로운 퀸의 위치쌍을 append하는 형태로 쓰입니다. 즉, 아래의 식을 만족해야 하는 것입니다.

(append (queen-cols 0) (list 1 1))
>>> (list 1 1) 

appned 프로시저는 (append nil something)을 something으로 반환해 줍니다. 따라서 프로시저는 아래와 같습니다.

(define empty-board nil)

3.1 safe?

가장 생각도 많이 필요하고 시간도 오래 걸린 프로시저입니다. 처음으로 완성한 프로시저는 다음과 같습니다.

(define (safe? k positions)
  (define (horizontal-check-iter value positions)
    (if (null? positions)
        #f
        (or (= (car (car positions)) value)
            (horizontal-check-iter value (cdr positions)))))
  
  (define (diagnol-check-iter value distance positions)
    (if (null? positions)
        #f
        (or (= (car (car positions)) (+ value distance))
            (= (car (car positions)) (- value distance))
            (diagnol-check-iter value (+ distance 1) (cdr positions)))))
  
  (define (check? k positions)
    (let ((row-value (car (car positions))))
      (if (= k 1)
          #f
          (or (horizontal-check-iter row-value (cdr positions))
              (diagnol-check-iter row-value 1 (cdr positions))
              (check? (- k 1) (cdr positions))))))

  (if (check? k positions)
      #f
      #t))

첫번째로 떠올린 아이디어입니다. 가장 첫번째 퀸의 row값을 기준으로 horizontal-check-iter로 수평 방향으로 겹치는 퀸이 있는지 확인하고, diagnol-check-iter로 대각선 방향으로 겹치는 퀸이 있는지 확인한 후 다음 퀸으로 넘어가서 다시 확인하는 프로시저입니다.

3.2. safe?

두번째로 떠올린 아이디어는 두 포지션간 서로 공격이 가능한지 알아보는 (check? p1 p2)를 만들어서 구현하는 것입니다.

(define (safe? k positions)
  (define (check? p1 p2)
    (let ((row-1 (car p1))
          (col-1 (cadr p1))
          (row-2 (car p2))
          (col-2 (cadr p2)))
      (or (= row-1 row-2)
          (= (- col-2 col-1) (abs (- row-2 row-1))))))

  (define (check-positions-iter this-position other-positions)
      (if (null? other-positions)
          #f
          (or (check? this-position (car other-positions))
              (check-positions-iter this-position (cdr other-positions)))))
  
  (define (check-iter k positions)
    (if (= k 1)
        #f
        (or (check-positions-iter (car positions) (cdr positions))
            (check-iter (- k 1) (cdr positions)))))
  
  (if (check-iter k positions)
      #f   ;unsafe
      #t)) ;safe

읽어주셔서 감사합니다.