Today interviewstreet gave a problem that to find one solution to place N queen in NxN board. In addition, a queen is allowed a knight's move.
I wrote a simple backtrack solution which solves N=32, N=35 is doable but takes maybe 30min.
There are solution for the original N queen problem solves N with time O(N^2). Given there are solution solves N up to 10^4, the solution should be applicable to this modified problem as well.
Subscribe to:
Post Comments (Atom)
I don't know why I failed this one. It's a pretty old problem...just O(n) solution...
ReplyDeletethe queen can have knight move, how do you handle that?
ReplyDeleteIt's a very interesting problem. You can find a quick way to solve it by reading wikipedia article.
ReplyDeleteI managed to generate the solution for n = 999 in about ten seconds with my algorithm (in java)