patternMinor
Why is the size of the search space 2057 in the 8-queen puzzle?
Viewed 0 times
whythespacesearchsizequeen2057puzzle
Problem
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?
According to Peter Norvig's book, there are only 2057 possible sequences. Where does that number come from?
Solution
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$.
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$.
Context
StackExchange Computer Science Q#12317, answer score: 2
Revisions (0)
No revisions yet.