[plt-scheme] Re: HtDP Exercise 43.3.3

From: Gadfly (dyrueta at gmail.com)
Date: Fri Mar 5 23:32:25 EST 2010

I just realized that even interested parties might hesitate to
download two random ss files, so I've cut-and-pasted the contents of
both into Google docs:

placement-with-local available here


and TestingFunctions available here


On Mar 5, 8:09 pm, David Yrueta <dyru... at gmail.com> wrote:
> 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-YzY2YzgxOTctYWFjOC00MDUw...
> and "TestingFunctions" available here --
> https://docs.google.com/leaf?id=0B_ZKElmhzsp-NDZiZWJiNzgtNjJhZC00NGRj...
> 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
> _________________________________________________
>   For list-related administrative tasks:
>  http://list.cs.brown.edu/mailman/listinfo/plt-scheme

Posted on the users mailing list.