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

Comments

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

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 :(