www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - Re: Knight's Challenge in D

reply Chris R. Miller <lordSaurontheGreat gmail.com> writes:
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.
Apr 03 2008
parent reply Chris R. Miller <lordSaurontheGreat gmail.com> writes:
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...
Apr 04 2008
parent reply Ty Tower <towerty msn.com.au> writes:
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 .
Apr 04 2008
parent Chris R. Miller <lordSaurontheGreat gmail.com> writes:
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!
Apr 04 2008