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

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

[DarkOx]

Nothing is wrong with it at all. In a traditional compiled language its often the most efficent way to write something and it often gets you the most efficent compiled code and when it does not most compilers will be smart enough to build a loop construct when the go to the assembler stage.

If you are using an interpreted langague like python or my favoirte Dialect( needs more respect ) then you have to be a little careful with it because these have a "soft stack" that can only get so deep. They have to keep track of how deep they are and where that have been, rather then just a beq and jmp on some register value, so they know what to do next. Mosty interpreters have a fixed stack depth although some manage to abstact this to linked list like structures internally and can keep going until the heap is exhasted. In any case you can't search to big a space recusively or it will fail.

Re:Perl

[berend botje]

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

Chess::Piece::Knight.

Perl is awesome!

Re:Python uses lambda calculus?

[Free the Cowards]

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.

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.