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

[Anonymous Coward]

And the use of xrange()

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:evolve or die

[Anonymous Coward]

Yawn.

Another claim that Perl is "in its last throes".

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.

Re:Python uses lambda calculus?

[harry666t]

> If you need a function that does two things, you can't use lambda anymore.

wtf? of course you could!

lambda x,y: (spam(x), meth(y)) [-1]

yeah, less readable etc but works. And yes, Python is even capable of executing interesting, obscure one-liners:

http://mobile.slashdot.org/comments.pl?sid=1022735&cid=25689627

Re:Perl

[Anonymous Coward]

(Note: I'm the GP AC.)

Heh. That's funny, but actually, I *was* being a smartass. Don't get me wrong, I love Perl, but the example above is completely made up. (And looking into the Chess package on CPAN, it appears that there is no preimplemented way to generate knight's tours, either.)

Still, I'm glad to hear that Perl's reputation for there being a module for anything and everything on CPAN still lives, at least. ;)

Re:awesome

[earthbound kid]

I got it to run in Python 3, and here are the changes I need to make:

1) The file was screwed up and used a tab instead of 8 spaces (a problem unrelated to Python 3).
2) I had to change all the print statements into print functions by wrapping the argument in parentheses.
3) I had to change xrange to range.
4) I had to add from functools import reduce to the top of the file.

Done. 4 changes made in 5 minutes, the hardest of which (#1) would have screwed up Python 2.x as well.

MAJOR version

[CarpetShark]

The code will break with the next MAJOR version, not revision. That's entirely normal -- it's actually pretty much what version (as opposed to revision) means.

Re:Python uses lambda calculus?

[harry666t]

Not doable.

The colon in lambda is like a guy with a Vista laptop on a LUG meeting. The whole lambda syntax construct is an expression, and def's, if's, while's and all the other guys begin a block of statements (and are statements themselves). In Python, you simply cannot cleanly embed a statement within an expression -- you'd need braces of some kind (and suggesting that to the devs would be like asking to be crucified). Just think, how would this look like:

map(lambda x:
  if abs(x) > 5:
    spam(x)
, [3,-3,5,-5])

With braces, you could write this like map(lambda x {if abs(x) > 5 {spam(x)}}, [3,-3,5,-5]), but well, try "from __future__ import braces".

And btw, what is the return value of the if statement?... -- exactly.

Just define a regular function :)

==

But it's still cool to sometimes try and think why Guido or others haven't yet implemented a seemingly obvious feature X. Here's an interesting post about explicit self:

http://neopythonic.blogspot.com/2008/10/why-explicit-self-has-to-stay.html

(oh, and BTW: list comprehensions, "x if b else y", other lambdas, are all expressions, so if you'd really want to, you can still do a lot with lambdas (loops, fancy nested if's, etc) -- you may even wrap most of the statements (if, while, import, try, exec) into functions and then try to write whole program as a one great expression... Lisp-style. Just for fun ^^)

Re:28 lines in Prolog :-)

[setagllib]

I don't know if you're just being ironic, but your Java code isn't even correct with respect to AWT/Swing threading semantics. You're supposed to create Swing objects only in the AWT event loop thread, using EventQueue.runLater() or one of its wrappers. I guess you're using Thread.sleep() later to get around the threading bugs you just created, but since your code is uncommented it's hard to tell.

Re:All done.

[Anonymous Coward]

fixed for ya.