View mode: basic / threaded / horizontal-split · Log in · Help
April 03, 2008
Re: Knight's Challenge in D
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.
April 05, 2008
Re: Knight's Challenge in D
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...
April 05, 2008
Re: Knight's Challenge in D
Yes Chris I am enjoying this too . I changed the program to change the board array and ran the same algorithm and it produced output ok . I commented out the newline too so it went straight to svg drawings . I notice on this it starts at square 1 ,then 2 .....64 and really just moves the result along one square . So Ill have a look at the new one and see what it does .
April 05, 2008
Re: Knight's Challenge in D
Ty Tower Wrote:

> Yes Chris I am enjoying this too . I changed the program to change the board array and ran the same algorithm and it produced output ok . I commented out the newline too so it went straight to svg drawings . I notice on this it starts at square 1 ,then 2 .....64 and really just moves the result along one square . So Ill have a look at the new one and see what it does .

I just wish I had my little SVG program four years ago in CS.  It would have made my horrid Java program so much easier to debug!
Top | Discussion index | About this forum | D home