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

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

### 10255 - The knight's Tour

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

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:

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

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

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

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

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.
Check input and AC output for thousands of problems on uDebug!