10255 - The knight's Tour

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

Moderator: Board moderators

Post Reply
jpfarias
Learning poster
Posts: 98
Joined: Thu Nov 01, 2001 2:00 am
Location: Brazil
Contact:

10255 - The knight's Tour

Post by jpfarias » Mon Mar 18, 2002 3:46 pm

I've used the Warnsdorff rule to solve this problem and the euclidean distance, but got WA on the online judge!!
I also say that there's no circuito for n<=5 and for (n mod 2 == 1).
Can anyone help?

ftomi
Learning poster
Posts: 64
Joined: Sun Jan 06, 2002 2:00 am
Location: Hungary
Contact:

Post by ftomi » Mon Mar 18, 2002 9:08 pm

Consider the case when n=1.
If it's ok, I suppose to chechk yourself: Make a big input with all cases. You will see what's wrong. I did the same.

jpfarias
Learning poster
Posts: 98
Joined: Thu Nov 01, 2001 2:00 am
Location: Brazil
Contact:

Post by jpfarias » Tue Mar 19, 2002 1:48 pm

I've just got ACC!!

Well, I've just looked for a starting point for my algorithm that gives me a circuit, then I
renumber it from the place given in the input.

Thanx anyway!!

LittleJohn
Learning poster
Posts: 83
Joined: Wed Feb 27, 2002 2:00 am
Location: Taiwan

Post by LittleJohn » Mon Mar 25, 2002 10:04 pm

I also use these algorithms to solve this problem, but when I test my program by 50 1 1 ~ 50 50 1, I found two cases has some trouble.
case1: 50 16 1
case2: 50 30 1
It takes 2 seconds to get the answer of case1, and my program can't get the result of case2 (it just run, run, run...). Although it can work from 50 1 1 ~ 50 50 1 except these two cases in 1 sec. Does somebody know why? @@" thanks!!

jpfarias
Learning poster
Posts: 98
Joined: Thu Nov 01, 2001 2:00 am
Location: Brazil
Contact:

Post by jpfarias » Tue Mar 26, 2002 9:30 pm

Can't help u, my program works just fine with this input!!!

LittleJohn
Learning poster
Posts: 83
Joined: Wed Feb 27, 2002 2:00 am
Location: Taiwan

Post by LittleJohn » Tue Mar 26, 2002 10:56 pm

Could you tell me whether the followings are right or not?
1. choose the square that can be reached in one move with the lowest number of new choices in that chosen square.
2. if there's a tie, choose the successor with largest Euclidean distance to the center of the chessboard.
I have no idea what's wrong with my program. If these are correct, I'll check my program again. thank you.

ram
New poster
Posts: 30
Joined: Wed Mar 06, 2002 2:00 am
Contact:

Post by ram » Wed Mar 27, 2002 2:47 am

I was wondering about the circuit path. How can we decide about that. Is the rule
that "n<=5 and n%2==1 chessboards doesnt have circuit paths" correct???

dh3014
New poster
Posts: 24
Joined: Tue Mar 26, 2002 2:00 am
Location: Taiwan
Contact:

Post by dh3014 » Wed Mar 27, 2002 3:19 am

LittleJohn:
Your heuristic is correct.

ram:
that's right.
n <= 5 (except 1!!) && (n mod 2 == 1)
has no circuit tour

LittleJohn
Learning poster
Posts: 83
Joined: Wed Feb 27, 2002 2:00 am
Location: Taiwan

Post by LittleJohn » Wed Mar 27, 2002 7:53 am

Thanks! I find the bug! ^^
I use the original square to calculate distance, not the next square's coordinates..... >_<

chang
New poster
Posts: 16
Joined: Wed Jan 16, 2002 2:00 am

10255

Post by chang » Fri Apr 05, 2002 3:26 pm

Hi !
I've no idea about 'Warnsdorff rule' && 'euclidean distance'. Can any body help me writing the idea here or better give any web-reference to know about it.
Thanks in advance for ur kind response.

ftomi
Learning poster
Posts: 64
Joined: Sun Jan 06, 2002 2:00 am
Location: Hungary
Contact:

Post by ftomi » Fri Apr 05, 2002 6:55 pm


..
A great helper
Posts: 454
Joined: Thu Oct 18, 2001 2:00 am
Location: Hong Kong

10255 though accepted.....

Post by .. » Sat Mar 13, 2004 8:58 pm

Although I get accepted on this problem, I still have many questions about it..
First, in the problem, it is written

[quote]
You can assume that there will be a possible Knight Path Tour from that given position when there exists a knight
My signature:
  • Please make discussion about the algorithm BRFORE posting source code.
    We can learn much more in discussion than reading source code.
  • I HATE testing account.
  • Don't send me source code for debug.

User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey » Wed Mar 17, 2004 1:11 pm

About Manzoor's assumption: it's redundant but not untrue :)
It's the same as saying: "assume a day has 24 hours" or "assume a dog has four legs".

About Warnsdorff's rule: I noticed the same thing, but I believe we both used a too simple version of the rule. Amongst the 50 or so hits google gave on "warnsdorff", I remember reading that originally Warnsdorff used look-ahead to break ties between two or more minimal moves. The 'zero-ply' simplified version I used, sometimes failed finding a path the first time, but succeeded when trying again with different search orders (different offsets in the dx[8] and dy[8] arrays).
Other implementations might use a random function to break ties and be called iteratively until a path is found.

This is a great problem because it's one of the very few (the only one?) in the problemset that can be solved by using a true heuristic rule!

jurajz
Learning poster
Posts: 69
Joined: Sat Sep 02, 2006 7:30 pm
Location: Slovakia

Re: 10255 - Knight's Tour

Post by jurajz » Thu Jun 11, 2009 4:11 pm

Hi,
I made 8 Presentation Errors in this problem. I cannot find, where can I make mistake.

For input
1 1 1
my output is
four spaces+"1"+newline

For input with no solution, my output is only one line:
"No Circuit Tour."+newline

For input with solution, my output is N lines, every line contains N numbers. One figure number has 4 spaces before, 2figure number 3 spaces, 3figure 2 spaces and 4figure number have 1 space before. Every line ends with newline.

Between two test cases I write one blank line, that means after each test case except the last.

Where I am wrong, where may be cause of Presentation Error?

Thanks in advance!

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 10255 - Knight's Tour

Post by brianfry713 » Tue Aug 14, 2012 4:14 am

You don't need to worry about the case where n=1 in this problem.

jurajz, your output description seems correct.
Check input and AC output for thousands of problems on uDebug!

Post Reply

Return to “Volume 102 (10200-10299)”