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?
10255 - The knight's Tour
Moderator: Board moderators
-
LittleJohn
- Learning poster
- Posts: 83
- Joined: Wed Feb 27, 2002 2:00 am
- Location: Taiwan
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!!
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!!
-
LittleJohn
- Learning poster
- Posts: 83
- Joined: Wed Feb 27, 2002 2:00 am
- Location: Taiwan
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.
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.
-
LittleJohn
- Learning poster
- Posts: 83
- Joined: Wed Feb 27, 2002 2:00 am
- Location: Taiwan
10255 though accepted.....
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
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.
-
little joey
- Guru
- Posts: 1080
- Joined: Thu Dec 19, 2002 7:37 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!
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!
Re: 10255 - Knight's Tour
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!
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
You don't need to worry about the case where n=1 in this problem.
jurajz, your output description seems correct.
jurajz, your output description seems correct.
Check input and AC output for thousands of problems on uDebug!