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!"

Try lisp

[FlyingBishop]

Advantages that have nothing to do with libraries, and can be traced back to the combination of (a) functional programming and (b) the perfect syntax that Python offers. 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.

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.

Re:better algo

[Anonymous Coward]

"This algorithm is rather complicated because it has to deal with many special cases, but has been implemented in Mathematica by A. Roth."

This would pretty much defeat the fun of coding it in python.

A trivial backtracking algorithm and...

[berend botje]

Is submitter really thinking he is special because he implemented a trivial backtracking algorithm that every first semester CS student has done?

Re:28 lines in Prolog :-)

[phantomfive]

Yeah, and here's one in Java [google.com] that does the same thing but with an animated GUI (with only 10 more lines of code!). Thus the claim from the article is a bit much:

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.

Re:Doing it without CS teaching?

[jellomizer]

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.

Re:evolve or die

[RightSaidFred99]

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 hope a firehose exploit was involved.

[Vexorian]

I take the point of the blog plug was that I shouldn't be able to do it in C++ with 60 lines....

     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++) //hence the reason I am waiting for c++0x
    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 :(

Re:28 lines in Prolog :-)

[omuls are tasty]

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 [berkeley.edu], check out the different versions and see which ones convey the meaning and ideas more clearly.

Re:I hope a firehose exploit was involved.

[chris_7d0h]

Well C(++) doesn't force you to use new lines at all for most purposes. In the PP's example the exception would be the pre-processor directives.
So, the PP's solution would fit in just 4 lines of code, way fewer than the 60 required for the Python example, but what does that prove w.r.t. either language implementation of the algorithm?

Lines of code is a real stupid measurement for complexity, productivity, maintainability and / or elegance and I really wish people would stop using it like that.

Re:28 lines in Prolog :-)

[Tack]

in a Python doc comment, I'd be a rich guy. What is a foo exactly? A class? A tuple? A list of tuples of classes? Or worse, any of the above?

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.)

Re:28 lines in Prolog :-)

[vampiro369]

In contrast, I've found it very easy to dive right into some of the large C++ code bases we have at work and immediately understand what the code does and how it does it, largely because C++ is more explicit and the (partly redundant) specification of type information means you can rapidly find how different components interact. Redundant comments are kept to a minimum. Comprehension is radically improved.

This is very useful when attempting to understand error messages, for instance. My absolute worst nightmare troubleshooting wise is running a giant Python script and getting a type error 20 frames deep, because I know it could easily burn an afternoon just untangling the mess. More explicit languages rarely seem to have this problem.

So you're saying C is better than python just because you're better at C?

I have no problem finding what a function does in python. I can go as far as telling you that it is easier contributing in large projects written in python than contributing in large projects written in C. I'm sure that almost everyone (excluding those impaired by Oppositional Defiant Disorder) will agree that scripting languages have had a huge impact on programming because code is easier to write, easier to maintain, etc. It has everything to do with readibility.

Perl, PHP, Python, Ruby ... the list goes on and on. Millions have benefited from using these and other languages and yet, you claim you find it harder using python than C? And your best defense on readability is claiming that type specification is of uttermost importance?

If you find it hard to understand code because you have to open a file and close it and open another and "damn this wasn't it, better close it and grep -R again", USE AN IDE. There are lots out there and they're reaaaally worth it. Some of them even take you the object's definition (file AND line no.) when you double-click on the name!

C++ has its uses. It would be downright stupid to try and use python for everything. But using C for everything is downright stupid too. My absolute worst nightmare is getting a Segmentation Fault when adding functionality to 15,000+ lines C code. I know, I've tried. And 15,000+ lines of code written a few years ago. Worst. And written by a bad programmer. Worst yet.

The assumptions here should be quite clear: A bored individual decided to tackle a problem he/she finds interesting. He used previously acquired knowledge only. His programming tool was python. The first try was good but sloppy. The second one ran blazingly fast (compared to the first one) and it was still below the 65-lines mark. Good enough, right? He didn't set out to write a paper on the best Knight's Tour algorithm. He didn't even set out to point out that python was better than any other language! He could tackle the problem in a few hours and present a working solution to a crowd that can read the code, understand it and use it and I think python excels in accomplishing that.

But I guess you're writing an OS and scripting doesn't suit you...

Re:evolve or die

[xorsyst]

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 [masonhq.com]

Re:awesome

[mollymoo]

Nah, "for index in range(1, 100):" makes a bloated memory list of 1,2,3,4,5,6,7...99,100 whereas xrange(1,100) is memory-efficient iterator that just returns an incremented value upon each loop.

A valid concern for large lists and essential knowledge for Python programmers, but for the the 64 element list you need to represent a chess board, who really gives a shit? Just write the clean, future-proof code and let the machine do the hard work. You're trading programmer convenience for machine time by using Python anyway.