title: N-Queens puzzle solution - cannot understand
body: <p>I am reading a description to a solution for the N-Queens puzzle on SICP and I cannot understand most of them. Here is the solution:</p>
  
  <blockquote>
    <p>One way to solve the puzzle is to work across the board, placing a
    queen in each column. Once we have placed k - 1 queens, we must place
    the kth queen in a position where it does not check any of the queens
    already on the board. We can formulate this approach recursively:
    Assume that we have already generated the sequence of all possible
    ways to place k - 1 queens in the first k - 1 columns of the board.
    For each of these ways, generate an extended set of positions by
    placing a queen in each row of the kth column. Now filter these,
    keeping only the positions for which the queen in the kth column is
    safe with respect to the other queens. This produces the sequence of
    all ways to place k queens in the first k columns. By continuing this
    process, we will produce not only one solution, but all solutions to
    the puzzle.</p>
  </blockquote>
  
  <p>Suppose that an 8 by 8 chessboard looks like this: My eyes are destroyed so I cannot use pictures. 0 means no queen, 1 means queen.</p>
  
  <pre><code>0 0 0 0 0 0 0 0
  0 0 0 0 0 0 0 0
  0 0 0 0 0 0 0 0
  0 0 0 0 0 0 0 0
  0 0 0 0 0 0 0 0
  0 0 0 0 0 0 0 0
  0 0 0 0 0 0 0 0
  0 0 0 0 0 0 0 0
  </code></pre>
  
  <blockquote>
    <p>work across the board, placing a queen in each column.</p>
  </blockquote>
  
  <p>My understanding is columns are read vertically and rows are read horizontally. Does the text mean something like this?</p>
  
  <pre><code>1 0 0 0 0 0 0 0
  0 1 0 0 0 0 0 0
  0 0 0 0 1 0 0 0
  0 0 0 0 0 1 0 0
  0 0 0 0 1 0 0 0
  0 0 0 1 0 0 0 0
  0 0 1 0 0 0 0 0
  0 1 0 0 0 0 0 0
  </code></pre>
  
  <p>I have placed a queen in each column but no rows are specified, but since this is done recursively I assume I already generated the ways of positions where two queens are not in check from each other.</p>
  
  <blockquote>
    <p>Assume that we have already generated the sequence of all possible
    ways to place k - 1 queens in the first k - 1 columns of the board.</p>
  </blockquote>
  
  <p>Say k = 1. So 1-1 = column 0 which have one way of generating the positions because it's an empty board.</p>
  
  <blockquote>
    <p>For each of these ways, generate an extended set of positions by
    placing a queen in each row of the kth column.</p>
  </blockquote>
  
  <p>My solution to column 0 is 1 way, but I absolutely have no idea what following means.</p>
  
  <blockquote>
    <p>generate an extended set of positions by placing a queen in each row
    of the kth column.</p>
  </blockquote>
  
  <p>What does "generate an extended set of positions" and placing a queen in each row of the column mean? Is it like this if k = 1?</p>
  
  <pre><code>1 0 0 0 0 0 0 0
  1 0 0 0 0 0 0 0
  1 0 0 0 0 0 0 0
  1 0 0 0 0 0 0 0
  1 0 0 0 0 0 0 0
  1 0 0 0 0 0 0 0
  1 0 0 0 0 0 0 0
  1 0 0 0 0 0 0 0
  </code></pre>
  
  <p>But then all of the queens aren't safe because they all are in the same columns right?</p>
  
  <p>I am totally lost on how to proceed. Can someone explain this to me?</p>
  
  <p>Note: If you would like to give a visual explanation, please also provide a textual explanation because I can't see images and pictures. Thanks</p>