# [racket] N queens, revisited

 From: Matthias Felleisen (matthias at ccs.neu.edu) Date: Fri Jun 11 14:57:29 EDT 2010 Previous message: [racket] Using raco exe [summary] Next message: [racket] Http post using post-impure-port Messages sorted by: [date] [thread] [subject] [author]

```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
its construction.

Design the functions