0
$\begingroup$

In the 8 queen puzzle, if we use the incremental approach, i.e. put the queen one by one on the board, the number of possible sequences would be 2057. How is that number calculated?

(This number is taken from the book AI by Peter Norvig)

$\endgroup$
2
  • 2
    $\begingroup$ This forum is not the best for your question. I would suggest a compsci forum on stackexxchange. My guess is there is either an error or something highly nonsymmetric is occurring (as a reflection of a partial placement is another partial placement). Perhaps they limit the queen to four squares on the first row, and count the number of leaves on the resulting pruned search tree. Gerhard "Feelling A Bit Lopsided Presently" Paseman, 2013.05.21 $\endgroup$ May 22, 2013 at 16:39
  • 3
    $\begingroup$ a blog post explaining the number 2057 in the 8-queen puzzle in the AI book sites.google.com/a/lclark.edu/drake/courses/ai/… $\endgroup$
    – meij
    May 22, 2013 at 21:39

2 Answers 2

0
$\begingroup$

This is an exercise in recursion and programming, so in THIS particular instance, id say use bruteforce recursion, (for example the mathematica code below).

However, for $n=8$, there are only 92 solutions, without removing symmetric solutions. Thus, there must be something strange where you see this number. Your number does not seem to appear for any other $n$ on wikipedia. I cannot see where this 2057 is counting.

Queens[n_] := Module[{CheckState, Recurse},

   (* Checks diagonals. 
   Columns/Rows cannot be attacking by design. *)

   CheckState[{}] := True;
   CheckState[state_] := With[
     {p = Last@state, len = Length@state},
     And @@ 
      Table[Abs[state[[i]] - p] != Abs[i - len], {i, len - 1}]];
   (* Recursive function. *)
   Recurse[currentState_] :=
    Which[
     (* If any diagonal attacking, this is not a valid state *)

     CheckState[currentState] == False, 0,
     (* If we have found a state, return 1. *)

     Length@currentState == n, 1,
     (* In any other case, 
     try all rows not already used in next column,
     and sum all valid states reached by these sub-branches. *)

     True,
     Sum[
      Recurse[Append[currentState, s]],
      {s, Complement[Range[n], currentState]}
      ]];

   (* Start with empty state. *)
   Return@Recurse[{}];
   ];
Queens[8]
$\endgroup$
3
  • $\begingroup$ Note that the question mentions sequences and not solutions. Can you modify it to count the leaves under each major branch of the search tree? Gerhard "Ask Me About System Design" Paseman, 2013.05.21 $\endgroup$ May 22, 2013 at 20:30
  • $\begingroup$ I took sequence as solution, since a solution is essentially a permutation of 1..n, (a sequence of numbers). This DOES count leaves. A leaf==solution. $\endgroup$ May 23, 2013 at 6:35
  • $\begingroup$ counting non-solutions, or partial solutions gives higher numbers than 2057... $\endgroup$ May 23, 2013 at 6:42
1
$\begingroup$

This is just the number of states that we need to test. Say we try to place queens from left to right, and top to bottom. For the current column, try each possibility for the queen. Once a row is chosen for that queen, check that if the constraint that no queen attack another is satisfied. If it is, move on to the next column or record the solution if there is no kore column. Otherwise, backtrack. At each step, if either a solution is found or the constraint is violated, increase the counter by $1$. In the end, the value of the counter is the number of states we need to examine. That's probably where the number is coming from. It should be easy to write a program to confirm this.

$\endgroup$
1
  • $\begingroup$ Doesn't this number depend on the order in which you check things? $\endgroup$
    – Peter Shor
    Jun 7, 2013 at 15:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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