One approach to achieve goal state is to "add a queen to any square in the leftmost empty column such that it is not attacked by any other queen". And this approach will have a state space of 2057 (also wondering How to compute this?)
What is the time complexity if I am using Depth First search algorithm (which I think is the most suitable one)? How about the space complexity?
I am puzzled because the brunching of the search tree is reducing greatly when goes deep. O(8**8) looks too much for time complexity, even for worst case.
Thanks
Depth First Search's time depends on how smart the algorithm is to decide which branch to investigate first.
N queens has a cheat: it has a heuristic (see description on wikipedia) which gives a perfect solution in polynomial time. If your Depth First Search's decisions simply mimic that heuristic's decisions, then your Dept First Search is poly time too.
Collected from the Internet
Please contact [email protected] to delete if infringement.
Comments