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

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

[RedWizzard]

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

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.

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();

dump the recursion

[Jecel Assumpcao Jr]

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.

...and then there's APL

[shking]

Here's a solution in 14 lines of APL. 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

[Speare]

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

• 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

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

Re:better algo

[eulernet]

The ultimate algorithm is called Warnsdorf's heuristic:
http://www.delphiforfun.org/programs/knights_tour.htm
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/