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)
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)
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]
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.