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!"
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.
Is submitter really thinking he is special because he implemented a trivial backtracking algorithm that every first semester CS student has done?
I would truly be amazed to see anyone writing the same logic in C++ in anything less than 3 times the lines of code I wrote in Python. And even if this is somehow possible (using external libraries like BOOST, I'd wager), the code will take longer to write, and it will be far more difficult to comprehend or refactor...
And I'd wager that this guy has never worked on huge projects. Any chunk of code that is less than a hundred lines is not going to be difficult to refactor; in fact, such a short piece of code probably gets longer and more confusing by adding object oriented structure (notice his code isn't encapsulated into a class or anything). The real advantages of structured programming isn't seen until you have a large project that has constantly changing requirements. That is where flexibility REALLY makes a difference.
I would also argue that any modern language gives you everything you need to write good, flexible code, and the quality of the code produced is more closely related to the skill of the programmer, than it is to the programming language itself.
In fact, for myself, it would not be an exaggeration to say I can write more flexible code in assembly now than I could five years ago in any language. Of course, it would be well structured assembly, not the wild mess of code I've written in previous years. YMMV.
Qxe4
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.
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"
That Java code is only 10 lines longer, but it doesn't include the code for some other classes it uses to solve the problem.
But anyhow, you're missing his point. The basic backtracking algorithm for the problem is simple in any language, and could indeed be made much shorter in Java (w/o the entire search framework). He's talking about improving the search with a heuristic (in his case, what is known as a "minimum remaining values" search heuristic among the AI folks). But he's still probably wrong, as you'd only need to write a Comparator in Java, or overload the operator< in C++ to achieve the same effect, and my guess is it'd only take you about 2x the Python code for the same functionality.
But, IMHO, the problem is not so much the increase in code, it's the shift in thinking which you have to undergo to make your code in Java. You just want to sort a bloody list based on a certain criteria, but now you have to make a class, encode your state data in it, and define a comparator function. Basically the brain -> program mapping is most of the time so much more direct in Python (and other similar languages) than the high-level assembly family of C languages that it isn't even funny. I sometimes feel like being put in a straitjacket when I have to write some Java or C++. Don't get me wrong, I definitely agree that a lousy programmer can make a mess in any programming language (I've written my share of bad code) and that a good programmer can write good code in any programming language (save for COBOL), but why torture yourself?
A good indicator for me is the source code for problems in the AIMA book, check out the different versions and see which ones convey the meaning and ideas more clearly.
This is certainly one of the practical drawbacks of duck-typing. But name-based polymorphism is exceedingly powerful, and with great power comes great responsibility. (Namely, to document one's arguments and return values properly.)