www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - Knight's Challenge in D

reply Chris Miller <lordSaurontheGreat gmail.com> writes:
I decided to take D for a spin with a very old problem I tried to solve my
freshmen year in Computer Science.  I was using Java, and back then with only
version 1.4.2 it didn't get very far, or very fast, either.

So when I came back to the same problem, I tried to use some more D features
than my previous Java attempts.  I came up with a working solution extremely
quickly (four hours).  That was cool.  (1)

Then I decided to write a D program to make SVG images to illustrate the
solutions. (2)  I reverse-engineered the SVG images from an existing Wikipedia
image script written in Perl, embellishing it to handle variable sized grids. 
That took about six hours, since I had to write a parser.

All in all, it took around 1,000 microseconds to generate the solution sets,
and around half a second to generate all the images. (3)

Complete success.

I thought some people here might like to see it, since it's in D.  I didn't
exactly think it big enough for digitalmars.D.announce, either.

I hope someone likes it!

1. http://www.fsdev.net/browser/Knights_Challenge/Intelligent/8x8/Miller.d
2. http://www.fsdev.net/browser/Knights_Challenge/tools/SVGMaker.d
3. http://www.fsdev.net/wiki/knights-tour/Miller1
Apr 01 2008
next sibling parent janderson <askme me.com> writes:
Chris Miller wrote:

 I decided to take D for a spin with a very old problem I tried to solve my
freshmen year in Computer Science.  I was using Java, and back then with only
version 1.4.2 it didn't get very far, or very fast, either.
 
 So when I came back to the same problem, I tried to use some more D features
than my previous Java attempts.  I came up with a working solution extremely
quickly (four hours).  That was cool.  (1)
 
 Then I decided to write a D program to make SVG images to illustrate the
solutions. (2)  I reverse-engineered the SVG images from an existing Wikipedia
image script written in Perl, embellishing it to handle variable sized grids. 
That took about six hours, since I had to write a parser.
 
 All in all, it took around 1,000 microseconds to generate the solution sets,
and around half a second to generate all the images. (3)
 
 Complete success.
 
 I thought some people here might like to see it, since it's in D.  I didn't
exactly think it big enough for digitalmars.D.announce, either.
 
 I hope someone likes it!
 
 1. http://www.fsdev.net/browser/Knights_Challenge/Intelligent/8x8/Miller.d
 2. http://www.fsdev.net/browser/Knights_Challenge/tools/SVGMaker.d
 3. http://www.fsdev.net/wiki/knights-tour/Miller1


Great Stuff!
Apr 02 2008
prev sibling next sibling parent reply Tower Ty <towerty msn.com.au> writes:
Ill give it a run -Chess being one of my passions .
Didn't see a statement of the problem as you first saw it so don't yet know
what it does . I hope t find out .

Looked at your site and forum but could not leave a pst there so I guess you
have to register for that and I don't join forums which are not free speech
forums. 

I quote from the site and thought the following pretty well says it all.

Free Advice -- If you are keen you will take comments and criticism from any
source and work to fix them avidly . When you lay down rules which say " if you
don't post where I want it  I will ignore it " that tells me immediately your
not likely to succeed. The advice ? change your attitude quickly.   

 [quote]
We prefer that you try to contact us on the forum. It's there for a reason. If
you have a suggestion or a bug for our software, please, use the ticket system.
We tend to ignore things that are placed where they shouldn't be.

We also have a public mailing list which we use for internal announcements.

If you absolutely have to get a hold of someone, there is also the #fsdev IRC
room on freenode.

If nothing else works, you can try to email Lord Sauron directly. It's just
lord_sauron at fsdev dot net.

If that still doesn't work, it's very possible that we're directly ignoring
you. 
[/quote]
Apr 02 2008
parent reply Chris Miller <lordSaurontheGreat gmail.com> writes:
Tower  Ty Wrote:


 Ill give it a run -Chess being one of my passions .


My brother refuses to play me, and has since he was ten.  Six years later I
still can't convince him to play me.

Perhaps I should make a future project of mine an online multiplayer chess game
(in D, using DWT)?  It could be fun to write, and of course, to "debug".


 Didn't see a statement of the problem as you first saw it so don't yet know
what it does . I hope t find out .


There's a good article on Wikipedia.  I'm afraid I lost the original document
which I first got the problem from.


 Looked at your site and forum but could not leave a pst there so I guess you
have to register for that and I don't join forums which are not free speech
forums. 


Hmm...  Excellent point.  I'll have to rethink my submission mechanism.  I was
going to give an email address, though sadly whenever I put it on the 'net in
one more location, that invariably creates more spam for me.

I wouldn't really call my forum non "free speech."  I just want to make sure
that speech is put in the right category so when you're looking for speech,
it's where it should be.  I also keep it closed to prevent the inevitable: spam.

Spam happens everywhere.  I just don't want it on my site, and I don't want to
leave it open.  I don't want to spend my time deleting spam.

And obviously I censor speech that isn't legal in the United States, and stuff
that would violate my web hosting contract.  If you don't like that, well, all
I can say is "take it up with Uncle Sam."


 I quote from the site and thought the following pretty well says it all.
 
 Free Advice -- If you are keen you will take comments and criticism from any
source and work to fix them avidly . When you lay down rules which say " if you
don't post where I want it  I will ignore it " that tells me immediately your
not likely to succeed. The advice ? change your attitude quickly.   


I have learned that from sad experience.  I have run forums, mailing lists, and
sites where users just plain put things in the wrong place.  It's extremely
annoying, and I desperately want to spend more time coding and less time
playing admin.

Also, I do think it says that I tend to ignore things that aren't in the right
place.

I shall amend the rules, since you do make a good point.  I really don't want
too many people registering on my site, anyways.  The more passwords I'm
entrusted to keep secret and away from prying eyes, the more stress on me to
ensure proper security and hashing technique.  A total mess, in other words.


  [quote]
 We prefer that you try to contact us on the forum. It's there for a reason. If
you have a suggestion or a bug for our software, please, use the ticket system.
We tend to ignore things that are placed where they shouldn't be.
 
 We also have a public mailing list which we use for internal announcements.
 
 If you absolutely have to get a hold of someone, there is also the #fsdev IRC
room on freenode.
 
 If nothing else works, you can try to email Lord Sauron directly. It's just
lord_sauron at fsdev dot net.
 
 If that still doesn't work, it's very possible that we're directly ignoring
you. 
 [/quote]


And no, I really don't ignore people very often.  Heck, I can't remember the
last time I ignored someone.  Well, excluding spammers.

I just put it there to prevent any kind of conceivable liability issues. 
Better safe than sorry!
Apr 02 2008
parent reply Georg Wrede <georg nospam.org> writes:
Chris Miller wrote:

 Hmm...  Excellent point.  I'll have to rethink my submission
 mechanism.  I was going to give an email address, though sadly
 whenever I put it on the 'net in one more location, that invariably
 creates more spam for me.


On a web site you could put the mail address simply in a picture.

And another idea: many big sites have these distorted text string 
pictures you have to type in, sort of like a password to prove that 
you're human. Now, most of these are entirely random, computer 
generated, and whatever else fancy.

On a small-volume low profile site (no disrespect intended here), making 
these could be just as simple as writing, say 20 random strings in your 
own handwriting (maybe quickly and sloppily) on a piece of dirty paper, 
digitizing them, and then showing one of them at random to the user.

---

Never pay for a lock stronger than the door. -- Anon.
Apr 03 2008
parent reply BCS <BCS pathlink.com> writes:
Georg Wrede wrote:

 Chris Miller wrote:
 

 Hmm...  Excellent point.  I'll have to rethink my submission
 mechanism.  I was going to give an email address, though sadly
 whenever I put it on the 'net in one more location, that invariably
 creates more spam for me.


 
 
 On a web site you could put the mail address simply in a picture.
 
 And another idea: many big sites have these distorted text string 
 pictures you have to type in, sort of like a password to prove that 
 you're human. Now, most of these are entirely random, computer 
 generated, and whatever else fancy.


http://www.captcha.net/


 
 Never pay for a lock stronger than the door. -- Anon.


Never pay for a door stronger than the wall next to it.
Apr 03 2008
parent Georg Wrede <georg nospam.org> writes:
BCS wrote:

 Georg Wrede wrote:
 

 Chris Miller wrote:


 Hmm...  Excellent point.  I'll have to rethink my submission
 mechanism.  I was going to give an email address, though sadly
 whenever I put it on the 'net in one more location, that invariably
 creates more spam for me.


 On a web site you could put the mail address simply in a picture.

 And another idea: many big sites have these distorted text string 
 pictures you have to type in, sort of like a password to prove that 
 you're human. Now, most of these are entirely random, computer 
 generated, and whatever else fancy.


 
 http://www.captcha.net/
 

 Never pay for a lock stronger than the door. -- Anon.


 
 Never pay for a door stronger than the wall next to it.


Ah, captcha is free. The better!

Never pay for a door if you can get it for free. -- Ibid.
Apr 03 2008
prev sibling next sibling parent Tower Ty <towerty msn.com.au> writes:
In knightstour.SVGMaker I had to change line 12 to......... txtUtil =
tango.text.Util;
Capital U in my distribution of Tango Snapshot-08-03-2008
Apr 02 2008
prev sibling next sibling parent reply Tower Ty <towerty msn.com.au> writes:
I got some solutions printed in the console but how do I get the ssSVG diagrams
like you get please?
Apr 02 2008
parent Chris Miller <lordSaurontheGreat gmail.com> writes:
Tower  Ty Wrote:


 I got some solutions printed in the console but how do I get the ssSVG
diagrams like you get please?


I put the run output into a file, Miller.txt.

Then you take SVGMaker and run it with these command line settings:

SVGMaker.exe f -file"path/to/file"

In the same directory as it was run you should get SVG images named like this:

svg0.svg
svg1.svg
svg2.svg
...

They're in the order of the output.  They're sorta fun to look at, and great
for seeing if your algorithm is really working.  Sometimes looking at the
numbers scroll by can be boring.

I'm planning on adding support for specifying different output paths.

If you run it without arguments it should print out a default SVG to the
console for the closed solution first specified by The Turk.
Apr 02 2008
prev sibling next sibling parent reply bearophile <bearophileHUGS lycos.com> writes:
To help you improve your D skills here are few notes on the first D program
(the solver):
- I suggest you to put as many globals inside functions/structs as possible, to
reduce global namespace pollution, so 'access' can go in loc (Loc) and vectors
in 'get_legal_moves'.
- to improve readability you can put a space around operators, like in
isLegalLocation.
- you may want to use a global const N = 8 instead of putting 8 everywhere.
- print_solution() shows why Python syntax is better, you can replace the first
long ugly line with something like:
print "  ".join("%2d" % el for el in row)
You can do something similar with a functional lib, but it gets a bit too much
hairy:
putr( map((int el){ return format("%2d", el);}, row).join("  ") );
- generally try to use less for() and more foreach, so 'clear_board' can
contain just:
foreach (ref row; board)
    row[] = -1;
- opCmp can be simplified, removing the other struct method.
- Some time is spent sorting, so using a faster sort (like my fastSort) you can
reduce running time. The running time for this first program goes from 0.85 s
to 0.53 s on my old PC.
- In the attach there is the version with those changes (for Phobos!).

The code of your SVGmaker isn't nice looking at all (and it doesn't show the
point of the arrow), the Perl version is much more readable and short (despite
Perl being generally not much readable). Probably Perl is better for that kind
of code, so you may want to keep it in Perl (and use D for the generation of
solutions. Sometimes two languages are better than one). In alternative you can
avoid most of the the parsing, creating a second printing function in the first
program like this:

void print_moves(int start_loc_x, int start_loc_y) {
    char[2 * N * N] moves;
    foreach(r, row; board)
        foreach(c, el; row) {
            moves[el * 2] = '0' + r;
            moves[el * 2 + 1] = '0' + c;
        }
    writefln(moves);
}



I was using Java, and back then with only version 1.4.2 it didn't get very far,
or very fast, either.<


What's the running time of a Java version?

Bye,
bearophile
Apr 02 2008
parent reply Chris Miller <lordSaurontheGreat gmail.com> writes:
bearophile Wrote:


 To help you improve your D skills here are few notes on the first D program
(the solver):
 - I suggest you to put as many globals inside functions/structs as possible,
to reduce global namespace pollution, so 'access' can go in loc (Loc) and
vectors in 'get_legal_moves'.


I didn't know I could put something static into a struct.  Most of this was
translated from memory from another (failed) attempt in C.


 - to improve readability you can put a space around operators, like in
isLegalLocation.


Perhaps.  I wrote this down first on paper because I wasn't at a computer. 
Normally I adhere to Java standards, but this was more like writing C, so my
inexperience rubbed off on it.


 - you may want to use a global const N = 8 instead of putting 8 everywhere.


Yes, revision 2 will be interesting.


 - print_solution() shows why Python syntax is better, you can replace the
first long ugly line with something like:
 print "  ".join("%2d" % el for el in row)
 You can do something similar with a functional lib, but it gets a bit too much
hairy:
 putr( map((int el){ return format("%2d", el);}, row).join("  ") );


So does any of that have a practical application for D?


 - generally try to use less for() and more foreach, so 'clear_board' can
contain just:
 foreach (ref row; board)
     row[] = -1;


I did not know I could do that with an array.  I was under the impression that
I would have to do something more complicated to prevent assigning an integer
to a pointer to an array of integers.


 - opCmp can be simplified, removing the other struct method.


One of those was from when I was first learning how to overload opCmp.  That I
could overload it with a struct and something that isn't an object was quite a
revelation to me!


 - Some time is spent sorting, so using a faster sort (like my fastSort) you
can reduce running time. The running time for this first program goes from 0.85
s to 0.53 s on my old PC.


I have written numerous implementations of sorting algorithms.  I just didn't
feel like writing a shell sort by insertion (which I have found to be the
fastest for this particular data set) just then.


 The code of your SVGmaker isn't nice looking at all (and it doesn't show the
point of the arrow), the Perl version is much more readable and short (despite
Perl being generally not much readable). Probably Perl is better for that kind 


You're probably viewing the default run, which bothers to close the path.  The
circle blots out most of the arrow.

I agree that the Perl version is more readable.  I just needed something in D,
since I don't know Perl, nor do I have a Perl interpreter handy.  My D version
also can handle variable sized boards, which the Perl version cannot.  I did
not feel like learning enough Perl to make it handle variable sized boards,
either.


 of code, so you may want to keep it in Perl (and use D for the generation of
solutions. Sometimes two languages are better than one). In alternative you can
avoid most of the the parsing, creating a second printing function in the first
program like this:
 
 void print_moves(int start_loc_x, int start_loc_y) {
     char[2 * N * N] moves;
     foreach(r, row; board)
         foreach(c, el; row) {
             moves[el * 2] = '0' + r;
             moves[el * 2 + 1] = '0' + c;
         }
     writefln(moves);
 }


I considered ammending my rules to say that, however, the way it outputs now is
nice Wiki Syntax, so I can just throw it into the Wiki without editing it. 
That means I can put the SVGs in when I finally get a free moment.

The Wiki output is also a lot easier to read for debugging purposes.


I was using Java, and back then with only version 1.4.2 it didn't get very far,
or very fast, either.<


 
 What's the running time of a Java version?


On a 1000MHz Pentium M ULV, it was about fifteen seconds for the first solution
set, 30 for the second, and a stack overflow on the third.  I beat the problem
until I figured out that it was a limitation of the VM and the garbage
management.  I could of course force a garbage collection call more frequently,
perhaps in a separate thread, but that would be a little more involved than I
was willing to get.  I was a first year CS student, don't blame me!

Java 1.6 is much faster and more robust.  I'm sure that same code (with a few
migration changes, eg. the "new" for loop) would run far better with the newer
language additions.  I'm not using Java now, I'm learning D.  It was a problem
I was familiar with, so I made an implementation in the new language.  It was
fun.
Apr 02 2008
parent reply bearophile <bearophileHUGS lycos.com> writes:
Chris Miller:


 putr( map((int el){ return format("%2d", el);}, row).join("  ") );


So does any of that have a practical application for D?


1) This is a D forum, and lot of people here like various languages. I like
many languages. I don't think adding few extra lines in my post may hurt.
2) D is an evolving language, and new things may be added to it in the future.
If you don't discuss things you only keep C/C++ as a reference, and you may end
with a C++-like-only language.
3) I think functional programming will become more important in the future. The
last version (the one starting with putr) is actual D code you can run with my
D libs. It's hairy, so it shows why a better syntax is very useful for that
kind of programming. AST macros may help there. There is an alternative syntax
you can use, plus the map of std.algorithms of D 2.x, and the tools by downs,
etc.



I just didn't feel like writing a shell sort by insertion (which I have found
to be the fastest for this particular data set) just then.<


Probably there are other ways to improve that (a priority queue? Fibonacci
Heaps? etc), but fastSort is already written...



I agree that the Perl version is more readable.  I just needed something in D,
since I don't know Perl, nor do I have a Perl interpreter handy.  My D version
also can handle variable sized boards, which the Perl version cannot.<


I think a better-looking (and higher-level) D version can be written.



I did not feel like learning enough Perl to make it handle variable sized
boards, either.<


I see, then you can translate that Perl code to Python instead to D ;-)



I'm learning D.  It was a problem I was familiar with, so I made an
implementation in the new language.  It was fun.<


Good :-)

Bye,
bearophile
Apr 02 2008
parent Chris Miller <lordSaurontheGreat gmail.com> writes:
bearophile Wrote:


 Chris Miller:
 

 putr( map((int el){ return format("%2d", el);}, row).join("  ") );


So does any of that have a practical application for D?


 
 1) This is a D forum, and lot of people here like various languages. I like
many languages. I don't think adding few extra lines in my post may hurt.
 2) D is an evolving language, and new things may be added to it in the future.
If you don't discuss things you only keep C/C++ as a reference, and you may end
with a C++-like-only language.
 3) I think functional programming will become more important in the future.
The last version (the one starting with putr) is actual D code you can run with
my D libs. It's hairy, so it shows why a better syntax is very useful for that
kind of programming. AST macros may help there. There is an alternative syntax
you can use, plus the map of std.algorithms of D 2.x, and the tools by downs,
etc.


I just wanted to know if any of those would actually work in D.  My nasty
method isn't the best by any stretch of the imagination, and aside from boning
back up on regular expressions I couldn't think of a better solution.

If there's a better solution, that is awesome.  I didn't recognize anything as
D, and I didn't know if the last line was for D (whether for a library I do
know/have or not).


I just didn't feel like writing a shell sort by insertion (which I have found
to be the fastest for this particular data set) just then.<


 
 Probably there are other ways to improve that (a priority queue? Fibonacci
Heaps? etc), but fastSort is already written...


Perhaps.  I liked the shell sort by data exchange because it was an in-place
sort, which makes it safer for larger data sets.


I agree that the Perl version is more readable.  I just needed something in D,
since I don't know Perl, nor do I have a Perl interpreter handy.  My D version
also can handle variable sized boards, which the Perl version cannot.<


 
 I think a better-looking (and higher-level) D version can be written.


I don't disagree.  I just wanted something that worked, since having lots of
tables of numbers on the site was really bland.  The images look a lot better,
and help illustrate things far more effectively.

One of the things I'd like to do to the SVG maker is to change the worker
function that actually makes a string that describes an SVG is to modify it to
accept an array of locations as an array of locations (the struct).  That would
remove the necessity of re-parsing the text to make the circle and the ending
arrow.  I added the circle and arrow last, so I wasn't really thinking all the
way through.  It does beg another iteration.

The original parser could also use another do-over.  It just feels a bit too
fault-prone.  I haven't stress-tested it with malformed input to see how it
will react, and it could certainly be a lot better.

Specifically I was in want of a C-like scanf function for the board header.

scanf("found solution for %d %d in %d steps\n", x, y, steps);

It would have been much better.  I was attempting to avoid the use of
tango.stdc libraries in the spirit of SafeD.  For the life of me I couldn't
find a simple exit() function, so I was forced to import stdlib.  I'm still not
sure if Tango has one, though honestly I haven't continued my search.


I did not feel like learning enough Perl to make it handle variable sized
boards, either.<


 
 I see, then you can translate that Perl code to Python instead to D ;-)


Yeah, but the D version was more fun to write.  In addition, I'm not familiar
with Python, and I'd have to make a significant investment in time to locate
reliable documentation and to get myself up to speed with a working
understanding of how to make things tick in Python.  Not an option, given that
I'm under a lot of workload in school right now.  I was sick and missed three
days.  It feels like I missed most of the quarter though.
Apr 02 2008
prev sibling next sibling parent reply Tower Ty <tytower yahoo.com.au> writes:
Here is a fairly good statement of the problem .I remember now looking at it
twenty odd years ago

http://www.tri.org.au/knighttour.html
Apr 02 2008
parent Georg Wrede <georg nospam.org> writes:
Tower Ty wrote:

 Here is a fairly good statement of the problem .I remember now
 looking at it twenty odd years ago
 
 http://www.tri.org.au/knighttour.html


While reading your link, I stumbled on the Sequence database. A good
introduction is here:

http://www.research.att.com/~njas/sequences/demo2.html

(Excluding cheating at homework or on-line IQ tests,) this intro page is 
something I would have liked to read already when I was at school.
Apr 03 2008
prev sibling next sibling parent Tower Ty <tytower hotmail.com> writes:
Good stuff Chris

I got one to run at least and found the original problem. I followed your
advice and the first time I got 2 .svg files . The first of which worked and
looked good . The second gave me an array out of bounds error.

I'll have a closer look in a few hours as I have to go out but I'll chuck it in
here anyway in case you spot it immediately. This was the second try which ave
out of bonds on the first.result.

[tytower localhost mystuffExperimental]$ Miller
found solution 0 0 in 135 steps
||0||33||44||17||46||31||12||15||
||43||18||61||32||13||16||47||30||
||34||1||52||45||60||63||14||11||
||19||42||59||62||51||54||29||48||
||2||35||56||53||58||49||10||25||
||41||20||39||50||55||26||7||28||
||36||3||22||57||38||5||24||9||
||21||40||37||4||23||8||27||6||


found solution 0 1 in 119 steps
||31||0||17||56||33||46||15||12||
||18||59||32||47||16||13||34||45||
||1||30||55||60||57||48||11||14||
||54||19||58||49||52||61||44||35||
||29||2||53||62||43||50||25||10||
||20||5||42||51||26||63||36||39||
||3||28||7||22||41||38||9||24||
||6||21||4||27||8||23||40||37||


found solution 0 2 in 430 steps
||44||31||0||15||46||29||10||13||
||1||16||45||30||11||14||47||28||
||32||43||54||59||52||63||12||9||
||17||2||51||62||55||58||27||48||
||42||33||56||53||60||49||8||23||
||3||18||61||50||57||24||37||26||
||34||41||20||5||36||39||22||7||
||19||4||35||40||21||6||25||38||


found solution 0 3 in 1849 steps
||29||32||15||0||55||34||13||10||
||16||1||30||33||14||11||56||35||
||31||28||61||58||49||54||9||12||
||2||17||50||53||60||57||36||47||
||27||42||59||62||51||48||23||8||
||18||3||52||43||24||63||46||37||
||41||26||5||20||39||44||7||22||
||4||19||40||25||6||21||38||45||


found solution 0 4 in 1849 steps
||10||13||34||55||0||15||32||29||
||35||56||11||14||33||30||1||16||
||12||9||54||49||58||61||28||31||
||47||36||57||60||53||50||17||2||
||8||23||48||51||62||59||42||27||
||37||46||63||24||43||52||3||18||
||22||7||44||39||20||5||26||41||
||45||38||21||6||25||40||19||4||


found solution 0 5 in 230 steps
||13||10||29||46||15||0||31||44||
||28||47||14||11||30||45||16||1||
||9||12||63||52||59||54||43||32||
||48||27||58||55||62||51||2||17||
||23||8||49||60||53||56||33||42||
||26||37||24||57||50||61||18||3||
||7||22||39||36||5||20||41||34||
||38||25||6||21||40||35||4||19||


found solution 0 6 in 113 steps
||12||15||46||33||54||17||0||31||
||45||34||13||16||47||32||53||18||
||14||11||48||55||62||59||30||1||
||35||44||63||58||49||52||19||60||
||10||25||50||43||56||61||2||29||
||39||36||57||26||51||42||5||20||
||24||9||38||41||22||7||28||3||
||37||40||23||8||27||4||21||6||


found solution 0 7 in 133 steps
||15||12||31||46||17||44||33||0||
||30||47||16||13||32||53||18||43||
||11||14||55||52||45||62||1||34||
||48||29||60||63||54||51||42||19||
||25||10||49||56||61||58||35||2||
||28||7||26||59||50||39||20||41||
||9||24||5||38||57||22||3||36||
||6||27||8||23||4||37||40||21||


[1]+  Stopped                 Miller
[tytower localhost mystuffExperimental]$ SVGMaker f -fileresults.txt
0 : SVGMaker
1 : f
2 : -fileresults.txt
file=results.txt
board size 0 x 0 y 0 maxx 0 maxy 0
tango.core.Exception.ArrayBoundsException knightstour.SVGMaker(183): Array
index out of bounds
[tytower localhost mystuffExperimental]$ SVGMaker f -fileresults.txt
0 : SVGMaker
1 : f
2 : -fileresults.txt
file=results.txt
board size 0 x 0 y 0 maxx 0 maxy 0
tango.core.Exception.ArrayBoundsException knightstour.SVGMaker(183): Array
index out of bounds
[tytower localhost mystuffExperimental]$  

Here is the first and second .svg files I got.
Apr 02 2008
prev sibling next sibling parent reply Chris R. Miller <lordSaurontheGreat gmail.com> writes:
Tower  Ty Wrote:


 Good stuff Chris
 
 I got one to run at least and found the original problem. I followed your
advice and the first time I got 2 .svg files . The first of which worked and
looked good . The second gave me an array out of bounds error.
 
 I'll have a closer look in a few hours as I have to go out but I'll chuck it
in here anyway in case you spot it immediately. This was the second try which
ave out of bonds on the first.result.


[snip!]

Well, naturally I was quite amazed that it made an error on what looks like
good output.  However, then I looked closely.  You have two linefeeds in
between solution sets.  I cut it down to one, and it ran just fine.

The issue is due to the parser making a blank board in the event that it finds
two newlines in a row.  It then tries to treat it like a normal board with
things in it.  When it tries to snip a trailing space off of the end of an
array, it tries to find an array index at -1.

I'll be patching the source file shortly to fix that little bug.  Thanks for
the catch.

Also of note, since you made some comments about freedom of speech, I decided
to try and open up both the ticket system and forum to unregistered users.  The
people on the Trac site have their ticket system open to everyone, so that
can't be all too bad.  The forum I'm not so sure about, but I just reasoned
that I'll leave it open until the first spambot targets it.

Thanks for that input, it's really helping make the site better.
Apr 02 2008
next sibling parent Tower Ty <tytower yahoo.com.au> writes:
That was it Chris Thanks 
Now to go study what you did.
Good Luck
Apr 02 2008
prev sibling parent Tower Ty <tytower yahoo.com.au> writes:
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 ?
Apr 03 2008
prev sibling next sibling parent 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
prev sibling parent Chris R. Miller <lordSaurontheGreat gmail.com> writes:
Georg Wrede Wrote:


 Chris Miller wrote:

 Hmm...  Excellent point.  I'll have to rethink my submission
 mechanism.  I was going to give an email address, though sadly
 whenever I put it on the 'net in one more location, that invariably
 creates more spam for me.


 
 On a web site you could put the mail address simply in a picture.
 
 And another idea: many big sites have these distorted text string 
 pictures you have to type in, sort of like a password to prove that 
 you're human. Now, most of these are entirely random, computer 
 generated, and whatever else fancy.
 
 On a small-volume low profile site (no disrespect intended here), making 
 these could be just as simple as writing, say 20 random strings in your 
 own handwriting (maybe quickly and sloppily) on a piece of dirty paper, 
 digitizing them, and then showing one of them at random to the user.


Trac Hacks has a captcha plugin, but it hasn't been updated for 0.11 yet.  I
suppose I could try and update the plugin myself, but that'd require time that
I won't have until the weekend.
Apr 04 2008