Slashdot Mirror
Solving the Knight's Tour Puzzle In 60 Lines of Python
ttsiod writes "When I was a kid, I used to play the Knight's Tour puzzle with pen and paper: you simply had to pass once from every square of a chess board, moving like a Knight. Nowadays, I no longer play chess; but somehow I remembered this nice little puzzle and coded a 60-line Python solver that can tackle even 100x100 boards in less than a second. Try beating this, fellow coders!"
too bad that your code will break with the next python version.
C-x C-m KnightsPuzzle
There. I did it in one line of code.
#!/usr/bin/env python import sys g_sqSize = -1 # the board size, passed at runtime g_board = [] # the board will be constructed as a list of lists def main(): global g_sqSize if len(sys.argv) != 2: g_sqSize = 8 # Default: Fill the normal 8x8 chess board else: try: g_sqSize = int(sys.argv[1]) # or, the NxN the user wants except: print "Usage: " + sys.argv[0] + " " sys.exit(1) for i in xrange(0, g_sqSize): g_board.append(g_sqSize*[0]) # Fill the board with zeroes Fill(0,0,1) # Start the recursion with a 1 in the upper left print "No solution found" # if the recursion returns, it failed def InRangeAndEmpty(ty,tx): # check if coordinates are within the board return ty>=0 and tx>=0 and ty
He'd hop into KITT and go anywhere he damn well pleases.
... here: http://www.tri.org.au/tourcode.html
Though I have better things to do than actually try, looking over the code FTFA, I have to say that I think a transliteration of this code into Scheme or Lisp would actually look cleaner than Python. And I do know that that would deal with the problem the writer ran into, namely that Python has an absurdly low recursion limit.
I do like Python's syntax (for anything under 100 lines of code) but calling it a model of functional programming is just silly.
Apparently, this isn't NP-complete. There is an algorithm that can solve this in O(n) time, see here: http://mathworld.wolfram.com/KnightsTour.html
This will save a LOT of time for larger boards. Try to implement this.
Marge, get me your address book, 4 beers, and my conversation hat.
I blow my nose at you, so-called "Arthur King", you and all your silly English K-nigg-its.
No folly is more costly than the folly of intolerant idealism. - Winston Churchill
wrapper(Size, [X, Y], Path) :- :- :- :-
X == 1,
Y == 1,
Depth is Size * Size - 1,
worker(Size, [X, Y], Depth, [], ReversedPath),
reverse(ReversedPath, Path),
write(Path), nl.
worker(_, State, 0, CurrentPath, [State|CurrentPath]).
worker(Size, State, Depth, CurrentPath, FinalPath)
DepthM1 is Depth - 1,
move_generator(Size, State, NewState),
not(checker(NewState, CurrentPath)),
worker(Size, NewState, DepthM1, [State|CurrentPath], FinalPath).
checker(State, [State|_]).
checker(State, [_|StateList])
checker(State, StateList).
move_generator(Size, [X, Y], [NewX, NewY])
move(MoveX, MoveY),
NewX is X + MoveX, NewX == 1,
NewY is Y + MoveY, NewY == 1.
move(1, 2).
move(2, 1).
move(2, -1).
move(1, -2).
move(-1, -2).
move(-2, -1).
move(-2, 1).
move(-1, 2).
#!/usr/bin/perl
use Chess;
$knight = Chess::Piece::Knight->new();
$board = Chess::Board->new(100, 100, setup => {
$knight => "a1";
});
$knight->tour()->show();
With the "added intelligence" of the second version, the recursive search devolved into a linear one since the very first attempt at each step will lead to a good solution (add a print to the backtracking part and see if this isn't the case).
So you might as well convert the recursion into a loop and eliminate the stack overflows for large boards.
Is submitter really thinking he is special because he implemented a trivial backtracking algorithm that every first semester CS student has done?
Now let's see, they taught us about this problem back when I was a six- or seven-grader (~'90-91, can't recall exactly) as one of the illustrations for backtracking (yes, I know we can do it without backtracking, that was not the point then I guess). Go figure.
I am putting myself to the fullest possible use, which is all I can think that any conscious entity can ever hope to do.
Alas, Python lambdas are very limited, only allowing a single expression. If you need a function that does two things, you can't use lambda anymore. This is not a great hardship as Python allows you to declare inner-scoped functions and you can use that instead, but it's still annoying. I do recommend Python though, as it's a great language even with the occasional shortcoming.
If you mod me Overrated, you are admitting that you have no penis.
It's even less readable that PERL. Shit, I didn't think it's possible. And I used to "program" in PERL...
"an experienced, industrious, ambitious, and often, quite often, picturesque liar" - Mark Twain
Yawn.
Another claim that Perl is "in its last throes".
Here's a solution in 14 lines of APL. I'm pretty sure they could've made it shorter, but readability would've been even worse. APL has been called a "write-only language".
-- "At Microsoft, quality is job 1.1" -- PC Magazine, Nov. 1994
That's because you're looking at some MathML code. What one actually types into Mathematica, and sees in Mathematica (or sees in a raw text file version IF the "InputForm" of the code is looked at) is the following. Unfortunately, the code ends suddenly because slashcode somehow doesn't allow more to be shown. BAAAAAD slashcode.
Complaining about the readability of what you posted is like complaining about the raw HTML which goes into this webpage.
[
As part of my undergrad education. Taking less than a second on today's hardware is nothing spectacular; the secret is in the algorithm: You rate the squares according to the number of moves available from that square and, when given a choice, pick the square with the least number of moves. This way, you don't work yourself into a dead-end situation as frequently. Combine this with a little backtracking, and you've got a nice example to show how algorithm selection has a much larger impact on runtime performance than language selection.
Incidentally, 200 MHz was considered a fast CPU when I did it, and I remember it taking 8 billion moves and all night without finding a solution. Until, that is, we implemented the preferential choice part of the algorithm. After that, it was pretty much instantaneous.
The society for a thought-free internet welcomes you.
http://anthonyf.wordpress.com/2006/07/07/solving-the-knights-tour
I think even if you didn't know any lisp you would find this solution to be pretty readable.
Intron: the portion of DNA which expresses nothing useful.
Not to stir up old debates again, but if you like Lisp, you might be better off going for Ruby than for Python. Coming from a Scheme background, I find Ruby to be the more elegant language.
Python is a great language, but my feeling about it is that it's designed to support one way of programming (and not even completely - it's sort of ambivalent between procedural and object-oriented). This is fine, and has the advantage off encouraging consistency among programs from different authors. However, I feel there is a better way: just give programmers building blocks and let the programmers compose them in any way they like. I feel Ruby does this, and the result is a language in which you can elegantly build your program in any way you like. In particular, I feel pure functional style is more natural in Ruby than in Python.
Please correct me if I got my facts wrong.
Not cool.
Yes, but a lot of this stuff really isn't worth posting online. Espectially Slashdot I have created many algorithms myself without the need to post it for slashdot acceptance. Some interesting compression algorithms, Memory management algorithms... Whatever that I feel like exploring today. But it is for my own personal knowledge not for public viewing of my code as my method will be to prove some particular point to myself nor will it be efficient or complete, and any attempt to have it posted like the guy who posted this thread will just get critized for anything that is not the best as it could possibly be.
If something is so important that you feel the need to post it on the internet... It probably isn't that important.
Point of fact: Python has the sexiest sprintf() support available. Observe..
>>> print "I ate %d %s in %.3f seconds" % (99,'hotdogs',62.0895)
I ate 99 hotdogs in 62.090 seconds
Well, here's the thing. Perl was used for _everything_ there for a while, sysadmins who thought they were developers were developing full blown applications in Perl and finding, surprise surprise, that it wasn't real maintainable. So I think we're seeing less of that these days. But Perl is not dying, that's silly. If anything Perl is just being relegated to what it's _really_ good at, and that's UNIX automation tasks and quick throw-away scripts, and _sometimes_ smallish applications. There's really no better language for these types of things.
I take the point of the blog plug was that I shouldn't be able to do it in C++ with 60 lines....
//hence the reason I am waiting for c++0x ;
:(
1 #include <set>
2 #include <iostream>
3 #include <cassert>
4 using namespace std;
5
6 int dx[8]={1,1,-1,-1,2,2,-2,-2}, dy[8]={2,-2,2,-2,1,-1,1,-1};
7 int D[50][50];
8 int N,C;
9
10 #define valid(x,y) ((x>=0) && (x<N) && (y>=0) && (y<N) && (D[x][y]==-1 ) )
11
12 bool show()
13 {
14 for (int i=N;i--;)
15 {
16 for (int j=N;j--;)
17 cout<<"\t"<<D[i][j];
18 cout<<"\n";
19 }
20 return true;
21 }
22
23 bool rec(int x, int y)
24 {
25 D[x][y]=C++;
26 if(C==N*N)
27 return show();
28
29 set< pair<int, pair<int,int> > > poss;
30 for (int r=8;r--;)
31 if(valid(x+dx[r], y+dy[r]))
32 {
33 int neighb=0;
34 for (int t=8;t--;)
35 neighb+= valid(x+dx[r]+dx[t],y+dy[r]+dy[t] );
36 poss.insert( make_pair(neighb, make_pair(x+dx[r],y+dy[r] ) ));
37 }
38
39 for (typeof(poss.begin()) q=poss.begin(); q!=poss.end(); q++)
40 if (rec(q->second.first, q->second.second))
41 return true;
42
43 D[x][y]=-1;
44 C--;
45
46 return false;
47 }
48
49 void solve(int n)
50 {
51 N=n, C=0;
52 memset(D,-1,sizeof(D));
53 assert(rec(0,0))
54 }
55
56 int main()
57 {
58 int n;
59 while((cin>>n) && (n>0))
60 solve(n);
61 return 0;
62 }
The bastards! Those darn brackets force me to have 2 extra lines
Copyright infringement is "piracy" in the same way DRM is "consumer rape"
TFA has basically stumbled upon Warnsdorff's algorithm. It's a great method, but it doesn't work for really large boards due to blind alleys. There's another method available which uses decomposition to achieve a linear running time(in # of squares), but which is quite a bit more complex to implement. There's a nice tweak to the algorithm which can get much farther than the unmodified original: in the event of a tie (where two candidates have the same number of open neighbours), break the tie by choosing the square farthest from the center. This substantially extends the maximum size of the board (to what, I don't know, because it's worked for everything up to around 450x450, which is past what was described by Arnd Roth).
He's preached against premature optimization for years.
The code will break with the next MAJOR version, not revision. That's entirely normal -- it's actually pretty much what version (as opposed to revision) means.
Not doable.
:)
The colon in lambda is like a guy with a Vista laptop on a LUG meeting. The whole lambda syntax construct is an expression, and def's, if's, while's and all the other guys begin a block of statements (and are statements themselves). In Python, you simply cannot cleanly embed a statement within an expression -- you'd need braces of some kind (and suggesting that to the devs would be like asking to be crucified). Just think, how would this look like:
map(lambda x:
if abs(x) > 5:
spam(x)
, [3,-3,5,-5])
With braces, you could write this like map(lambda x {if abs(x) > 5 {spam(x)}}, [3,-3,5,-5]), but well, try "from __future__ import braces".
And btw, what is the return value of the if statement?... -- exactly.
Just define a regular function
==
But it's still cool to sometimes try and think why Guido or others haven't yet implemented a seemingly obvious feature X. Here's an interesting post about explicit self:
http://neopythonic.blogspot.com/2008/10/why-explicit-self-has-to-stay.html
(oh, and BTW: list comprehensions, "x if b else y", other lambdas, are all expressions, so if you'd really want to, you can still do a lot with lambdas (loops, fancy nested if's, etc) -- you may even wrap most of the statements (if, while, import, try, exec) into functions and then try to write whole program as a one great expression... Lisp-style. Just for fun ^^)
I like Lisp a lot, and I certainly prefer its syntax to Java or C (or--god help us all--C++), but I still think that it is clearly less readable than Python.
If there's a serious argument against this, it must be Lisp's macro capabilities...
"Not an actor, but he plays one on TV."
object[] finalBoard = System.Math.KnightsTour(64);
But does it work with 3 dimensional chess?
Can't copy n' paste the code here because I get the message: "Try not to use so many 'junky' words"! So, this is how Slashdot behaves to the language that brought it to life. Anyway,you can find the Perl script here.
There is an elegant Knight's Tour solver right inside your Python distribution. You can find it at /usr/lib/python2.5/test/test_generators.py. Written by Tim Peters (a.k.a. timbot).
Stop worrying about the risks of nuclear power and start worrying about the risks of not using nuclear power.
If anything Perl is just being relegated to what it's _really_ good at, and that's UNIX automation tasks and quick throw-away scripts, and _sometimes_ smallish applications.
Yes, like this smallish application
Get free bitcoins: http://freebitco.in