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

awesome

[sofar]

too bad that your code will break with the next python version.

Easy

[Anonymous Coward]

C-x C-m KnightsPuzzle

Re:Easy

[RAMMS EIN]

While your humor is appreciated, I feel compelled to point out that it should be

M-x knights-puzzle

Lisp doesn't use CamelCase.

better algo

[Coneasfast]

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.

Re:better algo

[seann]

Wait a second. What's wrong with recursion?

28 lines in Prolog :-)

[Anonymous Coward]

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

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.

Re:28 lines in Prolog :-)

[IamTheRealMike]

Yeah, that sort of assertion bugs me. My own experience has been the exact opposite - attempting to understand large Python programs that have evolved over a number of years is damn near impossible. I know, I've tried. The terseness of the language and the absolute lack of explicit typing means you can't just open up a random function and understand what's going on. You often have to trace backwards through the code just to discover what it's attempting to do.

Typically Python programmers try and paper over this problem with tons of doc comments. Problem is that like any comment, they can get out of date, and often aren't useful anyway. If I had a dollar for every time I've seen:

foo: The foo to bar.

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?

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.

Re:All done.

[Anonymous Coward]

Except you commented out all of the code.

Re:All done.

[somenickname]

There. I did it in one line of code.

That doesn't look like perl to me...

Perl

[Anonymous Coward]

#!/usr/bin/perl
use Chess;

$knight = Chess::Piece::Knight->new();
$board = Chess::Board->new(100, 100, setup => {
                $knight => "a1";
});

$knight->tour()->show();

Re:Perl

[berend botje]

I thought you were being a smart-ass. You weren't:

Chess::Piece::Knight.

Perl is awesome!

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:A trivial backtracking algorithm and...

[jellomizer]

Of course like all other programmers he thinks he is better then everyone else.

I had to solve it in C

[gillbates]

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.

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