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

awesome

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

Re:awesome

Thanks for that link, the new print command makes a lot more sense than the old one.

Re:evolve or die

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.

Easy

C-x C-m KnightsPuzzle

Re:Easy

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

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

This will save a LOT of time for larger boards. Try to implement this.

Re:better algo

The ultimate algorithm is called Warnsdorf's heuristic:
http://www.delphiforfun.org/programs/knights_tour.htm [delphiforfun.org]
It solves all possible orders (>100x100) in less than a second.

The algorithm cited in the article is really shitty, because it requires recursion.

Hint: I implemented an algorithm to enumerate all magic knight tours (magic, like in magic squares):
http://magictour.free.fr/ [magictour.free.fr]

28 lines in Prolog :-)

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

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:28 lines in Prolog :-)

It can be done concisely in functional languages, e.g. Haskell:

knights :: Int -> [[(Int,Int)]]
knights n = loop (n*n) [[(1,1)]]
        where loop 1 = map reverse . id
                loop i = loop (i-1) . concatMap nextMoves

                nextMoves already@(x:xs) = [next:already | next <- possible]
                        where possible = filter (\x -> on_board x && not (x `elem` already)) $ jumps x

                jumps (x,y) = [(x+a, y+b) | (a,b) <- [(1,2), (2,1), (2,-1), (1,-2), (-1,-2), (-2,-1), (-2,1), (-1,2)]]
                on_board (x,y) = (x >= 1) && (x <= n) && (y >= 1) && (y <= n)

(from http://www.haskell.org/haskellwiki/99_questions/90_to_94).

Perl

#!/usr/bin/perl
use Chess;

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

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

Re:Perl

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

Chess::Piece::Knight [cpan.org].

Perl is awesome!

dump the recursion

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.

A trivial backtracking algorithm and...

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

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

Re:Doing it without CS teaching?

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.

...and then there's APL

Here's a solution in 14 lines of APL [dyalog.com]. 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".

Pentominoes Quine in Perl

I know it's a joke to refer to "obfuscated Perl" but this was my one attempt at doing something silly with it. http://www.halley.cc/ed/linux/scripts/quine.html [halley.cc]

• It finds solutions to the 6x10 pentominoes board (exhaustively)
• To find places that pieces will fit, it employs regular expressions
• To draw pieces into the board, it employs an embedded tape-driven LOGO-like turtle language
• It prints solutions as a specially formatted quine of its own source code
• Any printed solution can be run separately
• It takes hours and hours to find solutions

I had to solve it in C

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.

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:All done.

Except you commented out all of the code.

Re:All done.

From experience, commenting out the code makes it better. :P

Re:All done.

There. I did it in one line of code.

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

Re:All done.

Woosh.

Re:Python uses lambda calculus?

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.