### 10422 - Knights in FEN

Posted:

**Fri Mar 21, 2003 2:27 am**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...

The Online Judge board

https://uva.onlinejudge.org/board/

https://uva.onlinejudge.org/board/viewtopic.php?f=23&t=11579

Page **1** of **4**

Posted: **Fri Mar 21, 2003 2:27 am**

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...

Posted: **Fri Mar 21, 2003 4:51 pm**

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!

but i think the best approach is to use BFS. some ppl used IDS also.

thanx

-sohel

not to be repeated.my soln. is not fast enough though!

but i think the best approach is to use BFS. some ppl used IDS also.

thanx

-sohel

Posted: **Wed Jun 11, 2003 3:47 am**

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!

Note: after some simple modification, my program gets ACC in <<1 sec !

However, I'm still looking for faster algorithm...

I've just solved the problem by

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

Note: after some simple modification, my program gets ACC in <<1 sec !

However, I'm still looking for faster algorithm...

Posted: **Tue Jun 17, 2003 3:33 am**

Say, how should I solve this problem within reasonable time if **n <= 20**???

Posted: **Tue Jun 17, 2003 9:02 am**

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

Posted: **Tue Jun 17, 2003 10:37 am**

Could you explain more clearly pls??

By the way, it would be great if the*path* can be obtained as well!

By the way, it would be great if the

Posted: **Tue Jun 17, 2003 2:02 pm**

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

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

Posted: **Tue Jun 17, 2003 2:14 pm**

Wow!!!!!!! Really great!!!!!!!!!CelebiX wrote:i used IDA* and solved in 0.000sec.

This method sounds feasible! But I'm still not so familiar with BFS......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

But why would this method be efficient? Could you explain plz?

Posted: **Fri Jul 11, 2003 11:14 am**

Would anyone tell me how to solve the problem ?

Posted: **Fri Jul 11, 2003 12:40 pm**

Hi route

You can use backtracking to solve this problem.

angga888

You can use backtracking to solve this problem.

angga888

Posted: **Sat Jul 12, 2003 4:16 pm**

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 .

Since there is a restriction that it can only move by exchanging the position with the blank square .

Posted: **Mon Aug 04, 2003 4:48 pm**

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!!!!

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!!!!

Posted: **Tue Aug 05, 2003 8:06 pm**

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

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

Posted: **Wed Aug 06, 2003 1:40 am**

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

But how to implement??

But how to implement??

Posted: **Wed Aug 06, 2003 3:15 am**

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.. =)