[plt-scheme] Re: HtDP Exercise 43.3.3

I think I found the problem....

On Mar 5, 8:32 pm, Gadfly <dyru... at gmail.com> wrote:
> 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
>
> http://docs.google.com/Doc?docid=0AfZKElmhzsp-ZGhkcWgzamZfMzZkcnR4dmh...
>
> and TestingFunctions available here
>
> http://docs.google.com/Doc?docid=0AfZKElmhzsp-ZGhkcWgzamZfMzlmZDduN3p...
>
> 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
>
> _________________________________________________
>   For list-related administrative tasks:
>  http://list.cs.brown.edu/mailman/listinfo/plt-scheme