I'm currently working through SICP Exercise 2.42. I know that my adjoin-position function is bugged because when I replace it with
(define (adjoin-position-WORKING new-row k rest-of-queens)
(cons (list new-row k) rest-of-queens))
I get sensible output from queens.
Before this replacement, my code, which uses the exercise's template, is as follows:
#lang sicp
;;Boilerplate functions that the exercise calls:
(define (filter predicate sequence)
(cond ((null? sequence) nil)
((predicate (car sequence))
(cons (car sequence)
(filter predicate (cdr sequence))))
(else (filter predicate (cdr sequence)))))
(define (enumerate-interval low high)
(cond ((> low high) nil)
((= low high) (list high))
(else (cons low (enumerate-interval (+ 1 low) high)))))
(define (flatmap proc seq)
(accumulate append nil (map proc seq)))
(define (accumulate op initial sequence)
(if (null? sequence)
initial
(op (car sequence)
(accumulate op initial (cdr sequence)))))
;;;Start of solution:
(define empty-board nil)
;Placeholder, stops the filter from actually filtering anything:
(define (safe? new-queen-col-numb old-solutions) #t)
;;THE RELEVANT BIT
(define (adjoin-position ultimate-row-index new-queen-col-pos old-solutions)
(define (iter to-append-left to-append-right depth)
(cond ((null? to-append-right) to-append-left)
((= depth 1)
(append to-append-left (cons new-queen-col-pos to-append-right)))
(else (iter (append to-append-left (list (car to-append-right)))
(cdr old-solutions)
(- depth 1)))))
(iter nil old-solutions ultimate-row-index))
;;The template provided by the exercise, untouched by me:
(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))
;;Example of adjoin-position working as expected:
(adjoin-position 2 5 (list 10 11 12 13 14 15 16))
;Output: (10 5 11 12 13 14 15 16)
;i.e. it placed 5 at position 2, as I wanted it to.
;;Code to show that my adjoin-position is bugged.
(map queens (enumerate-interval 1 3))
The output for my final function, (map queens (enumerate-interval 1 3)), is a horror:
((())
(() () () ())
(()
()
()
()
()
()
()
()
()
()
()
()
()
()
()
()
()
()
()
()
()
()
()
()
()
()
()))
After replacing adjoin-position with adjoin-position-WORKING, my output is much more tolerable:
((((1 1)))
(((1 2) (1 1)) ((2 2) (1 1)) ((1 2) (2 1)) ((2 2) (2 1)))
(((1 3) (1 2) (1 1))
((2 3) (1 2) (1 1))
((3 3) (1 2) (1 1))
((1 3) (2 2) (1 1))
((2 3) (2 2) (1 1))
((3 3) (2 2) (1 1))
((1 3) (3 2) (1 1))
((2 3) (3 2) (1 1))
((3 3) (3 2) (1 1))
((1 3) (1 2) (2 1))
((2 3) (1 2) (2 1))
((3 3) (1 2) (2 1))
((1 3) (2 2) (2 1))
((2 3) (2 2) (2 1))
((3 3) (2 2) (2 1))
((1 3) (3 2) (2 1))
((2 3) (3 2) (2 1))
((3 3) (3 2) (2 1))
((1 3) (1 2) (3 1))
((2 3) (1 2) (3 1))
((3 3) (1 2) (3 1))
((1 3) (2 2) (3 1))
((2 3) (2 2) (3 1))
((3 3) (2 2) (3 1))
((1 3) (3 2) (3 1))
((2 3) (3 2) (3 1))
((3 3) (3 2) (3 1))))
So, now that we know for certain that the original adjoin-position was bugged and returned a list of empty lists rather than anything including numbers, I'm left with my real question - where did the original adjoin-position go wrong? The biggest surprise for me is not only that (adjoin-position 2 5 (list 10 11 12 13 14 15 16)) works just fine, but that queens should be calling what I understand to be (adjoin-position 1 1 (list nil)), which also gives a usable result: (1 ()). Am I misunderstanding what parameters queens is passing to adjoin-position?
I have not yet learned how to debug Scheme code, but replacing the call to (map (lambda (new-row)... with a call to map-debug:
(define (map-debug proc seq)
(display "Input list: ")
(display seq)
(newline)
(display "Output list:")
(display (map proc seq))
(newline)
(map proc seq))
produces the following output for (map queens (enumerate-interval 1 2))
Input list: (1)
Output list:(())
Input list: (1 2)
Output list:(() ())
Input list: (1 2)
Output list:(() ())
Input list: (1 2)
Output list:(() ())
((()) (() () () ()))
The implication is that the bug is in the following block of code, but I do not see it.
(lambda (rest-of-queens)
(map (lambda (new-row)
(adjoin-position new-row k rest-of-queens))
(enumerate-interval 1 board-size)))
The furthest that I've been able to figure out is that the (= depth 1) branch of adjoin-position's cond statement seems to never run. I do not know why, I just know that sticking a display line in it shows that the branch is never used. It appears that its old-solutions argument is being passed nil?
First let me describe how I understand the program is intended to work. Because if we have different ideas of how it should work then understanding the implementation is hard.
Let's assume we already have the first solutions to the 1-Column and 2-Column problem:
First of 8 Solutions To the 1-Column Problem:
=============================================
_
|_|
|_|
|_|
|_|
|_|
|_|
|_|
|Q|
position: ((1 1))
First of 42 Solutions To the 2-Column Problem:
==============================================
_ _
|_|_|
|_|_|
|_|_|
|_|_|
|_|_|
|_|Q|
|_|_|
|Q|_|
position: ((2 3) (1 1))
For the 3-Column problem we start with the first solution to the 2-Column problem and then generate the 8 possible board positions for the 8 possible rows the queen could be placed within the 3rd column:
First 8 Positions to Test as Possible Solutions To the 3-Column Problem:
========================================================================
_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
|_|_|_ |_|_|_ |_|_|_ |_|_|_ |_|_|_ |_|_|_ |_|_|_ |_|_|?
|_|_|_ |_|_|_ |_|_|_ |_|_|_ |_|_|_ |_|_|_ |_|_|? |_|_|_
|_|_|_ |_|_|_ |_|_|_ |_|_|_ |_|_|_ |_|_|? |_|_|_ |_|_|_
|_|_|_ |_|_|_ |_|_|_ |_|_|_ |_|_|? |_|_|_ |_|_|_ |_|_|_
|_|_|_ |_|_|_ |_|_|_ |_|_|? |_|_|_ |_|_|_ |_|_|_ |_|_|_
|_|Q|_ |_|Q|_ |_|Q|? |_|Q|_ |_|Q|_ |_|Q|_ |_|Q|_ |_|Q|_
|_|_|_ |_|_|? |_|_|_ |_|_|_ |_|_|_ |_|_|_ |_|_|_ |_|_|_
|Q|_|? |Q|_|_ |Q|_|_ |Q|_|_ |Q|_|_ |Q|_|_ |Q|_|_ |Q|_|_
First 8 positions to test:
((3 1) (2 3) (1 1))
((3 2) (2 3) (1 1))
((3 3) (2 3) (1 1))
((3 4) (2 3) (1 1))
((3 5) (2 3) (1 1))
((3 6) (2 3) (1 1))
((3 7) (2 3) (1 1))
((3 8) (2 3) (1 1))
Adjoin-position is called 8 times to create the positions to test by extending a 2-Column solution. (One possible cause of confusion is that the first two arguments to adjoin-position are row then col, but conventionally positions would col then row).
Creating the first 8 positions to test:
(adjoin-position 1 3 ((2 3) (1 1))) => ((3 1) (2 3) (1 1))
(adjoin-position 2 3 ((2 3) (1 1))) => ((3 2) (2 3) (1 1))
(adjoin-position 3 3 ((2 3) (1 1))) => ((3 3) (2 3) (1 1))
(adjoin-position 4 3 ((2 3) (1 1))) => ((3 4) (2 3) (1 1))
(adjoin-position 5 3 ((2 3) (1 1))) => ((3 5) (2 3) (1 1))
(adjoin-position 6 3 ((2 3) (1 1))) => ((3 6) (2 3) (1 1))
(adjoin-position 7 3 ((2 3) (1 1))) => ((3 7) (2 3) (1 1))
(adjoin-position 8 3 ((2 3) (1 1))) => ((3 8) (2 3) (1 1))
These are then filtered giving the four solutions to the 3-Column problem that extend the first 2-Column solution.
First 4 (of 140) Solutions to the 3-Column problem:
===================================================
positions:
((3 5) (2 3) (1 1))
((3 6) (2 3) (1 1))
((3 7) (2 3) (1 1))
((3 8) (2 3) (1 1))
_ _ _ _ _ _ _ _ _ _ _ _
|_|_|_ |_|_|_ |_|_|_ |_|_|Q
|_|_|_ |_|_|_ |_|_|Q |_|_|_
|_|_|_ |_|_|Q |_|_|_ |_|_|_
|_|_|Q |_|_|_ |_|_|_ |_|_|_
|_|_|_ |_|_|_ |_|_|_ |_|_|_
|_|Q|_ |_|Q|_ |_|Q|_ |_|Q|_
|_|_|_ |_|_|_ |_|_|_ |_|_|_
|Q|_|_ |Q|_|_ |Q|_|_ |Q|_|_
As you can see my adjoin-position is quite different from yours, it takes a list of lists and returns a longer list of lists (the coordinates of the queens on the board).
I find it hard enough to understand my own solution, and at the moment I'm struggling to understand how yours works. If the pictorial/algorithmic part of my description matches your solution, and it is only the representation/implementation of the positions that differs, then it might be useful if you could describe how you are representing those positions. E.g., what would you expect to see instead of:
(adjoin-position 1 3 ((2 3) (1 1))) => ((3 1) (2 3) (1 1))
(adjoin-position 2 3 ((2 3) (1 1))) => ((3 2) (2 3) (1 1))
(adjoin-position 3 3 ((2 3) (1 1))) => ((3 3) (2 3) (1 1))
...