Horace and others who have tackled the N queens
problem in HtDP. Below find a first draft of an
exercise that will go into HtDP/2e. It demonstrates
the importance of formulating good data representations
especially with the use of (what we called) data
accumulators in HtDP/1e. Enjoy -- Matthias
You have solved the N queens problem using the
a seeminly natural representation of the board
as an N by N grid. Now you notice that your
solution takes quite some time. After thinking
about it for a while, you realize that two of
the operations on board representations are
critical
-- finding those positions that are still safe
-- placing a queen on a board
The key is to make these operations fast.
Once you have studied accumulators and especially
the notion of data accumulators (see Missionary
and Cannibals), you can tackle this problem easily.
Represent boards with data that keeps track of
all placed queens and all safe positions. For
the initial board, there are no queens and all
positions are safe. When you place a queen on
a board, you add the queen('s position) to the
collection of queens, but you also remove all
those positions from the collection of safe
positions that are now threatened. A board
thus constructed accumulates knowledge about
its construction.
Design the functions
add-queen
find-open-spots
for this data representation and re-use the
original solution with this representation.
(Hint: this solution should run at least 20x
faster than the previous one.)
_________________________________________________
For list-related administrative tasks:
http://lists.racket-lang.org/listinfo/users
