12

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?

Community
  • 1
  • 1
mqpasta
  • 960
  • 3
  • 14
  • 38
  • 1
    @mqpasta, A web search for "8 queens dynamic programming" generates a fair number of hits. Did you read any of these sources to see how they defined DP _for this problem_? And do you disagree? You are correct that a 7-queen solution is not a component of an 8-queen solution, so your question is very interesting. – Ray Toal Aug 14 '11 at 09:31
  • Well, I didn't come across any resource describing 8-queen as DP... but I believe it must be as DP is for optimization for backtracking... but no point to prove this... – mqpasta Aug 14 '11 at 09:36
  • Theoretically an interesting question (though I don't see how DP could be used for this) but I don't know why you want to further optimize it, a good backtracking algo will check less than 4*7! placements which is 20160 (and remember, a lot of these will terminate earlier because of the diagonals) – Karoly Horvath Aug 14 '11 at 09:47
  • 1
    4*7! - for n = 8. What if n > 100? – TheHorse Aug 14 '11 at 11:49
  • @yi_H: TheHorse is right, the *"8-Queen"* is just the name of the problem, referring also to the general "n-Queen" one. – ypercubeᵀᴹ Aug 14 '11 at 13:28
  • @TheHorse: I posted a DP solution paper which solves it in O(f(n)*8^n). Does that answer your "what if" question? :) – Karoly Horvath Aug 14 '11 at 15:10

2 Answers2

5

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.

Tomas
  • 57,621
  • 49
  • 238
  • 373
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

Karoly Horvath
  • 94,607
  • 11
  • 117
  • 176
  • 1
    Your first entry for "A dynamic programming solution to the n-queens problem" is not quite clear. I read that document. Even there is running example given provided by author. For Second link, it works on permutation or random solutions.. its more likely Genetic! anyhow... I am thinking to plan a DP problem for correction of incorrect 8-queen problem... nice idea! – mqpasta Aug 14 '11 at 16:43
  • But, I am still looking for an answer to describe or comments on observation stated in my questions. – mqpasta Aug 14 '11 at 16:46