8-queen problem using Dynamic programming

Question

I am quite confused with idea of implementing 8-queen problem using dynamic programming. It seems it is not possible at one end as for DP " if the problem was broken up into a series of subproblems and the optimal solution for each subproblem was found, then the resulting solution would be realized through the solution to these subproblems. A problem that does not have this structure cannot be solved with dynamic programming" (Reference). By taking this in account, the optimal solution for 7x7 board might not optimal as well (even incorrect) for 8x8. So, the result of problem might not realize through optimal solution of sub-problem.

At the other hand, DP is optimization for backtracking problems... if so then 8-queen problem can be solved by backtracking... does it mean that by storing only dead-ends can convert backtracking solution into DP? If so, then might 2,1 is not feasible for parent 1,1 but might feasible for 1,2.

Update

anyone have idea that whether 8-queen or n-queen problem can be solved by using dynamic programming? If so then what will be your comments on observations given above?

Answer 1

optimal solution for 7x7 board might not optimal as well (even incorrect) for 8x8.

Yes, you are correct. But this is not a good way to split the problem. Look into paper yi_H posted in his answer, theorem 2.4, and look at the algorithm description. They divide the solutions into equivalence classes according to the sets of closed lines (i.e. lines which are threatened by queens). The theorem 2.4 guarantees that once they solve the sub-problem on the particular set of closed lines, they can solve the rest separately and then combine the result! Very clever.

Answer 2

Just posting the obvious google hit:

A dynamic programming solution to the n-queens problem

Note: this is still very slow for large n's, O ( f(n)*8^n), you better use some other algorithm:

A Polynomial Time Algorithm for the N-Queens Problem