10422 - Knights in FEN

All about problems in Volume 104. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

ditrix
New poster
Posts: 33
Joined: Sat Mar 01, 2003 12:38 am
Location: Paris

10422 - Knights in FEN

Post by ditrix »

What is the best algorithm for this problem? I tried a backtracking and it ran for 2 seconds, but there are more rapid solutions, say instant...
@+!
DitriX

User avatar
saiqbal
New poster
Posts: 36
Joined: Wed Aug 07, 2002 4:52 pm
Location: Dhaka, Bangladesh
Contact:

Post by saiqbal »

i used backtracking a with a little bound. i just checked the last move
not to be repeated.my soln. is not fast enough though! :wink:
but i think the best approach is to use BFS. some ppl used IDS also.

thanx
-sohel

Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong

Post by Observer »

Hello.

I've just solved the problem by DFS. However, my program runs pretty slowly (>> 7 sec)!!!! >_<

I know that there are some much faster methods. Could anyone plz explain them to me??? Many thanks! :roll:


Note: after some simple modification, my program gets ACC in <<1 sec !
However, I'm still looking for faster algorithm... :lol:
Last edited by Observer on Mon Aug 04, 2003 12:31 pm, edited 2 times in total.
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong

Post by Observer »

Say, how should I solve this problem within reasonable time if n <= 20??? :confused:
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

Adrian Kuegel
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

Post by Adrian Kuegel »

if N<=20, try bfs starting from starting and final position and check when they meet at some position.

Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong

Post by Observer »

Could you explain more clearly pls??

By the way, it would be great if the path can be obtained as well! :P
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

CelebiX
New poster
Posts: 5
Joined: Tue Jun 18, 2002 11:05 am

bidirectional bfs

Post by CelebiX »

i used IDA* and solved in 0.000sec.

if n<=20 try bfs from both the start and goal
the bfs tree grown from the start will meet the one grown from the goal at some node x
then start ~> x ~> goal is the path

Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong

Re: bidirectional bfs

Post by Observer »

CelebiX wrote:i used IDA* and solved in 0.000sec.
Wow!!!!!!! Really great!!!!!!!!! :lol: :lol: :lol:
CelebiX wrote:if n<=20 try bfs from both the start and goal
the bfs tree grown from the start will meet the one grown from the goal at some node x
then start ~> x ~> goal is the path
This method sounds feasible! But I'm still not so familiar with BFS......
But why would this method be efficient? Could you explain plz?
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

route
New poster
Posts: 39
Joined: Sat Dec 21, 2002 1:25 am

10422

Post by route »

Would anyone tell me how to solve the problem ?

angga888
Experienced poster
Posts: 143
Joined: Sat Dec 21, 2002 11:41 am
Location: Indonesia

Post by angga888 »

Hi route

You can use backtracking to solve this problem. :wink:

angga888

route
New poster
Posts: 39
Joined: Sat Dec 21, 2002 1:25 am

Post by route »

Can you tell me some more details ?
Since there is a restriction that it can only move by exchanging the position with the blank square .

Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong

Post by Observer »

Hello! It's me again.

While doing BFS we need to keep a boolean array to see whether a "node" is visited, is that correct?

But in this question, possible configurations = 25!/(12! 12!) = 67603900
So keeping such a huge array is definitely impossible!! (MLE for sure!!!)

So what should I do? Plz help!!!! :cry:
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

Whinii F.
Experienced poster
Posts: 151
Joined: Wed Aug 21, 2002 12:07 am
Location: Seoul, Korea
Contact:

Post by Whinii F. »

I came to see this post eventually and did not solve this problem.

Anyway.. as I understand the post, the size of the state space is pretty large, but by using the method posted above, the number of nodes that you actually have to traverse can become VERY small. :) So you can apply some hashing or clever data structures to check if you have visited a node already or not.

It's a late night in Korea and I'm going to bed now, but when I get an AC I'll come back :)
JongMan @ Yonsei

Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong

Post by Observer »

I see that the number of "nodes" visited will never exceed 60000......

But how to implement??
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:

Post by Larry »

I hashed/precalc from the end position to 11 moves away, and while it's not one of the 0.0 solutions, it's at ~ 0.57 seconds.. so ah well.. good enough for me.. =)

Post Reply

Return to “Volume 104 (10400-10499)”