Recursive algorithm seems to slow for n=8. Actually, it depends on the order of moves, but the order fast for n=8 was slow for 6 or 7, the fast one for 7 was slow for 8 and so on... Anyway, I used pregenerated output to solve this.
Is there a way to optimize the algorithm?

there is a greedy solution but non-demonstrable: you start from some position and then you go to the position that has the fewest future possible moves...
here are the solutions that I've computed with this:
for n = 5, 6, 7 and 8;
N = 5:
"a1","b3","a5","c4","e5","d3","e1","c2","a3","b1","d2","e4","c5","a4","b2","d1","e3","d5","b4","a2","c1","e2","c3","b5","d4"

N = 6:
"a1","b3","a5","c6","e5","f3","e1","c2","a3","b1","d2","f1","e3","f5","d4","b5","d6","c4","b6","a4","b2","d1","f2","e4","f6","d5","c3","a2","b4","a6","c5","e6","f4","d3","c1","e2"

N = 7:
"a1","b3","a5","b7","d6","f7","g5","e6","g7","f5","e7","g6","f4","g2","e1","c2","a3","b1","d2","f1","g3","e2","g1","f3","d4","b5","a7","c6","b4","a2","c1","d3","b2","a4","b6","c4","e5","d7","c5","a6","c7","d5","c3","d1","e3","g4","f2","e4","f6"

N = 8:
"a1","b3","a5","b7","d8","f7","h8","g6","f8","h7","g5","h3","g1","e2","c1","a2","b4","a6","b8","c6","a7","c8","e7","g8","h6","g4","h2","f1","d2","b1","a3","c2","e1","f3","h4","g2","e3","d1","b2","a4","c3","b5","d4","f5","d6","c4","e5","d3","f2","h1","g3","e4","c5","d7","b6","a8","c7","d5","f4","e6","g7","e8","f6","h5"

i used back and got AC in 0.46 ....

I wonder: my recursive solution for n=8 works faster than for n=7.

you may be not use recursion.
you may draw on sheet this and type answer to program...

I got AC in 0.031s .
But I not just submit the answer.
I just use DFS.


Edited by author 26.06.2004 10:16

I do it in 0.015 sec
I don`t use CONSTANT solv

I am also use DFS and AC in 0.718s.
Why my program slowly from you?

What is your fu*king dfs solutions? how did u manage that it is impossible!
My answer accepted in 0.734 sec
I also used DFS

Edited by author 01.04.2014 18:17