In the 8-queen puzzle, to reduce the search space, we can use an incremental approach. We put the first queen in the first column, then the 2nd queen in the 2nd column etc., avoiding the slots that are already being occupied.

According to Peter Norvig's book, there are only 2057 possible sequences. Where does that number come from?

  • 3
    $\begingroup$ It probably comes from an exhaustive search. $\endgroup$ – Yuval Filmus May 23 '13 at 16:23
  • 2
    $\begingroup$ ...which requires only $O(1)$ time. $\endgroup$ – JeffE May 23 '13 at 21:20
  • $\begingroup$ @JeffE If that was sufficient for practical efficiency, the world would be a better place. $\endgroup$ – Raphael May 28 '13 at 17:52
  • $\begingroup$ Perhaps I should have written "Which requires about 15 seconds of computation on your cell phone." $\endgroup$ – JeffE May 28 '13 at 20:22

According to Peter Norvig in 2007, it comes from "... writing a program and counting the states."

For the $n$-queens problem, it is not too hard to show that $(n!)^{(1/3)}$ is a lower bound on the size of state space. This can be calculated by considering the maximum number of squares in each column that might be threatened by queens from previous columns. For $n=8$, this evaluates to $34.29$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.