ENG  RUS Timus Online Judge
Online Judge
Problems
Authors
Online contests
Site news
Webboard
Problem set
Submit solution
Judge status
Guide
Register
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

## Discussion of Problem 1298. Knight

recursion?
Posted by [OSTU]Svetkin 7 Apr 2004 01:18
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?
Re: recursion?
Posted by sloboz 7 Apr 2004 03:47
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"
Re: recursion?
Posted by marius dumitran 9 Apr 2004 18:41
i used back and got AC in 0.46 ....
Recursion
Posted by Vlad Veselov 10 Apr 2004 15:48
I wonder: my recursive solution for n=8 works faster than for n=7.
No subject
Posted by test_programs 9 May 2004 19:10
you may be not use recursion.
you may draw on sheet this and type answer to program...
Re: recursion?
Posted by TheBeet 26 Jun 2004 10:15
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
My prog runs realy fast
Posted by Amberchild 23 Mar 2005 16:26
I do it in 0.015 sec
I don`t use CONSTANT solv
Re: recursion?
Posted by Allanur 1 Apr 2014 17:32
I am also use DFS and AC in 0.718s.
Why my program slowly from you?
Re: recursion?
Posted by Bekmyrat 1 Apr 2014 18:16
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