[plt-scheme] HtDP Exercise 43.3.3

Am hoping to prevail upon a fellow Schemer for help debugging my solution to
one of the final HtDP exercises.  So close, yet so far!

The exercise adapts the checking-queens algorithm from Chapter 28 to state
variables.  It asks the student to do two things: 1) design two new
functions, place-queen and unplace-queen, which serve to "set!" the
chessboard as the algorithm backtracks into a solution, and; 2)  implement
those functions into a new version of 'placement.'

Here's a link:

http://www.htdp.org/2003-09-26/Book/curriculum-Z-H-53.html#node_sec_43.3

I've done all that, but my solution fails in a very strange way.
Specifically, it generates the correct solution to for all boards up to 5 x
5:

;(check-expect (placement 1) (vector (vector true)))  ;; passes
;(check-expect (placement 2) false) ;; passes
;(check-expect (placement 3) false) ;; passes
;(check-expect (placement 4) (vector (vector false false true false) (vector
true false false false) (vector false false false true) (vector false true
false false))) ;; passes
;
;(check-expect (placement 5) (vector  ;; passes
;                             (vector false false true false false)
;                             (vector true false false false false)
;                             (vector false false false true false)
;                             (vector false true false false false)
;                             (vector false false false false true)))

On a 6 x 6 board, things start to get weird --

;(check-expect (placement 6) (vector        ;; fails
;                             (vector false false false true false false)
;                             (vector true false false false false false)
;                             (vector false false false false true false)
;                             (vector false true false false false false)
;                             (vector false false false false false true)
;                             (vector false false true false false false)))


Here's what I get instead ---

(vector
 (vector false false false true false false)
 (vector true false false false false false)
 (vector false false false false true false)
 (vector false true false false false false)
 (vector false false false false true true)
 (vector false false true false false false))

Compared to the correct solution, this result is off by one vector value, or
"queen-position": "true" in 5th column, 5th row.   That should be false --
the queen in column 6 should have "flipped" it after being placed.

I tested extensively the place and unplace functions, and they seem to work
fine.  Looking for patterns, I found that if you trace the trajectories of
the queens positioned in *only* vector-column-indexes 0-3, the resulting
board is exactly the one I'm left with. As if the queens in
vector-column-indexes  4 and 5 haven't been placed, even though the queen
positions selected in columns 0-3 are made *as though* they had!

Needless to say, things get progressively worse as the board dimension
inputs get larger.

All my efforts to debug have been fruitless.  I've sat with the Stepper
literally for hours trying to trace the origins of this result, but to no
avail.  I don't understand how I could get the correct solution for 5, but
have it blow up at 6, get worse at 7, etc.  I also don't understand why the
backtracking strategy which succeeded in all cases in Chapter 28 is not
working here.  I know there are subtle differences, especially in the base
case, but it seems the backtracking approach which worked in the first
should translate to the second.  It's making me a little crazy.

I've posted two public ss files to Google docs for anyone who wants to take
a look --

"placement-with-local" which is available here --


https://docs.google.com/leaf?id=0B_ZKElmhzsp-YzY2YzgxOTctYWFjOC00MDUwLWFlMTctYWMwNjk5MzE2MTgy&sort=name&layout=list&num=50

and "TestingFunctions" available here --

https://docs.google.com/leaf?id=0B_ZKElmhzsp-NDZiZWJiNzgtNjJhZC00NGRjLTlmNjAtNDE3ZTMwYzY4MWJl&sort=name&layout=list&num=50

Placement-with-local contains the complete algorithm, while TestingFunctions
contains all my tests for the auxiliary functions.  Data definitions,
written arguments for the algorithm (and a second alternative), function
contracts, purpose statements, etc. are all included.

This is a function with a lot of moving parts, so anyone who dives into with
me to try and help would be doing me an enormous favor.  The only thing I
can offer in return is lots of gratitude.... and maybe my grandmother's
not-really-secret-but-totally-yummie recipe for Spanish "tortilla patata."

As always, any and all suggestions are welcome and appreciated.

Many thanks!

Dave Yrueta
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.racket-lang.org/users/archive/attachments/20100305/6dd08d45/attachment.html>