Knight's Challenge in D

[Chris R. Miller]

Chris R. Miller Wrote:

> Tower  Ty Wrote:
> 
> > Interesting 
> > 
> > Your access array is as so
> > const int[8][8] access=[
> > 	[2, 4, 6, 6, 6, 6, 4, 2],
> > 	[4, 6, 8, 8, 8, 8, 6, 4],
> > 	[6, 6, 8, 8, 8, 8, 6, 6],
> > 	[6, 6, 8, 8, 8, 8, 6, 6],
> > 	[6, 6, 8, 8, 8, 8, 6, 6],
> > 	[6, 6, 8, 8, 8, 8, 6, 6],
> > 	[4, 6, 8, 8, 8, 8, 6, 4],
> > 	[2, 4, 6, 6, 6, 6, 4, 2]
> > 
> > Just taking the first line which explains the side squares of the board I can only see 3 legal moves on each tile you show 4 , and 4 on each tile you show 6. So what am I not seeing ?
> 
> What you're seeing is my typo.  I typed that down from memory, something I worked out almost four years ago.  Apparently my memory isn't as good as I'd like it to be.
> 
> Now that I look at that matrix, I'm seeing errors that I didn't notice that could significantly change the performance of my algorithm. I'll have to fix that when I get home (and to my compiler).
> 
> I think it should be:
> 
> const int access[][]= [
>     [ 2, 3, 4, 4, 4, 4, 3, 2],
>     [ 3, 4, 6, 6, 6, 6, 4, 3],
>     [ 4, 6, 8, 8, 8, 8, 6, 4],
>     [ 4, 6, 8, 8, 8, 8, 6, 4],
>     [ 4, 6, 8, 8, 8, 8, 6, 4],
>     [ 4, 6, 8, 8, 8, 8, 6, 4],
>     [ 3, 4, 6, 6, 6, 6, 4, 3],
>     [ 2, 3, 4, 4, 4, 4, 3, 2]
> ];
> 
> I have the original matrix I used in C fromm all those years ago stored away somewhere.  The defining feature of a good backup is inaccessibility, so it only follows that I can't find it.  Thanks for the catch.  I'll probably patch my algorithm and then only bother to regenerate the SVGs when I get a script to generate the Wiki page as well - last time I had to write in each image link by hand, which wasn't fun.

Absolutely fascinating.  I finally got enough spare time to alter the algorithm for the fixed access matrix.  I ran it, and it took longer!  I was really not expecting that!  The results of the run are here: http://www.fsdev.net/wiki/knights-tour/Miller2

I think it's because there are twice as many directions to go in, since the original ("broken") matrix created a North/South axis.  The "correct" matrix creates a flat effect, making it strangely less likely to rapidly find a solution.

This indicates that there is significant potential in studying the effects of varying access matrices on the performance of the algorithm and why they differ.

Very interesting...