SICP 4.44

It has been a while since my last post (and also a while since I have last written about SICP). The main reason is that I struggled with Chapter 4 a lot, and only have been escaped the struggle by discovering “the one true REPL-driven programming”. The post on how to setup SICP with Vim will be updated at a later time, I hope. For now, I am going to show you my solution to SICP 4.44, which is something quite fun that I worked on.

Description

Exercise 4.44: Exercise 2.42 described the “eight-queens puzzle” of placing queens on a chessboard so that no two attack each other. Write a nondeterministic program to solve this puzzle.

Eight-queens Puzzle

Let us assume that you are a well-versed Computer Science person, if you actively read my blog and clicked on this my post about SICP and stuff, but… Alright. Again, let us assume that you know basic chess rules. There is a rule about how can queens move: anywhere they want, horizontally, vertically, or diagonally.

Find a way (or different ways) that eight (n) queens can be placed on a 8 x 8 (n x n) board.

Representing Chess Board

Looking at the problem, we can instinctively think of representing the board as a 2D map, with xs, and ys as the coordinations. For example, position (1 3) is something like this:

The “Naivest” Approach That Actually Works

Our naivest (and actually works) approach then is to pick one position to put the queen, again and again, and hope that the picking somehow works out in the end:

1. Pick position (0 0): success 🗸
2. Pick position (1 2): success 🗸
3. Pick position (2 1): fail ✗, since it lies in the same diagonal with (1 2)

What matter is how we pick those positions. In the simplest way, we can:

• Generate (0 0) (0 1) (0 2) ... (1 0) (1 1) (1 2) ... (7 5) (7 6) (7 7)
• Try to pick 8 positions
• See if the newly-created solution is valid

In this way, we have to wade through 64 * 63 * ... * 57 solutions, which is roughly O(n^n), not counting the ways that we have to check for the validation itself. It is not something feasible for our poor computers!

Let us find a better way by more observing:

• After picking a position, every other position with the same row, and the same column is going to be left out:

• Again, pick another position (let us skip the constraint on diagonal lines here):

• Again, pick another position:

No matter how we pick it, the next position’s x is not going to be the previous ones’ x. y has the same pattern. We then come to a simple conclusion: the xs of our solution is going to be a permutation of 0 to 7; same goes for the ys.

Which means, within our algorithm, instead of:

1. Pick position
2. See if it is valid
3. Pick position
4. See if it is valid
5. Pick position
6. See if it is valid
...

We can do:

1. Choose a permutation
2. Choose a permutation
3. Generate the pair as positions
4. See if it is valid

For a really simple example, with n = 5, I am going to have this:

(range 0 8 1)
; (0 1 2 3 4 5 6 7)

(a-permutation-of (range 0 8 1))
; A possible result: (0 1 2 3 4 5 6 7)
; Another possible result: (2 1 3 4 0 5 7 6)

(zip (range 0 4 1) (range 4 8 1))
; ((0 4) (1 5) (2 6) (3 7))

(define xs (a-permutation-of (range 0 8 1)))
(define ys (a-permutation-of (range 0 8 1)))
(define positions (zip xs ys))

The new approach’s complexity gets a bit better: O(n!). There is only one piece left to solve: how can we check that the generated positions do not have lie on the same diagonal?

Let us focus on the “first” diagonal:

Its positions are:

; the first line
(0 0)
(1 1)
(2 2)
(3 3)
; ...

The first line’s “previous” and “next” are like this:

; the "previous" line
(1 0)
(2 1)
(3 2)
(4 3)
; ...

; the "next" line
(0 1)
(1 2)
(2 3)
(3 4)

We then see a pattern:

• If the difference ((- (x-of position) (y-of position))) is the same, then
• the two position lies on the same diagonal.

For example position 1 (1 0) lies on the same diagonal with position 3 (5 4), since (- 1 0) and (- 5 4) both returns 1. We cannot say the same for position 2 (5 1).

Let us look at another “first” diagonal:

The positions are:

(0 7)
(1 6)
(2 5)
(3 4)
; ...

And its “next”, and “previous”:

The positions are:

; the "previous" diagonal
(0 5)
(1 4)
(2 3)
(3 2)
; ...

; the "next" diagonal
(1 7)
(2 6)
(3 5)
(4 4)
; ...

We see the same pattern, but instead of difference, we have sum.

For example, position 1 (0 6) lies on the same diagonal with position 3 (6 0), since the sum of each is 6.

Checking if two of no two positions have lie on the same diagonal is damn simple:

(define diagonals-1
  (map (lambda (position)
         (- (x-of position)
            (y-of position)))
       positions))

(define diagonals-2
  (map (lambda (position)
         (+ (x-of position)
            (y-of position)))
       positions))

(distinct? (list 1 2 3))
; true
(distinct? (list 1 1 3))
; false

(require (distinct? diagonals-1))
(require (distinct? diagonals-2))

Nondeterministic Program

This section in SICP explained it clearly:

Basically, a nondeterministic program’s interpreter allows the usage of a special form called amb:

(amb <e_1> <e_2> ... <e_n>)

… [amb] returns the value of one of the n expressions <e_i> “ambiguously”.

For example

(list (amb 1 2 3)
      (amb 'a 'b))

Can have six possible values:

(1 a) (1 b) (2 a) (2 b) (3 a) (3 b)

Final Solution

Stripping all the “essential” functions, our program is just this:

(define (solve board-size)

  (define xs (a-permutation-of (range 0 board-size 1)))
  (define ys (a-permutation-of (range 0 board-size 1)))
  (define (x-of position)
    (car position))
  (define (y-of position)
    (cadr position))

  (define positions
    (zip xs ys))

  (define diagonals-1
    (map (lambda (position)
           (- (x-of position)
              (y-of position)))
         positions))

  (define diagonals-2
    (map (lambda (position)
           (+ (x-of position)
              (y-of position)))
         positions))

  (require (distinct? diagonals-1))
  (require (distinct? diagonals-2))

  positions)

(solve 5)
; ((0 0) (1 2) (2 4) (3 1) (4 3))
; try-again
; ((0 0) (1 3) (2 1) (3 4) (4 2))

The full code can be found on my GitHub.

Conclusion

In the end, I walked you through the solving of excerise 4.44 of SICP. The code is probably a bit “amb evaluator” specific, but I hope that the solving approach is good and clear to be implemented in any other language. In short, instead of:

- Choose one of `n * n` positions
- Check validity
- Choose another position from those `n * n` positions
- Check validity

This approach of using permutation is much better:

- Choose one permutation
- Choose one permutation
- Pair the two permutations into positions
- Check diagonal validity