Slashdot Mirror

← Back to Stories (view on slashdot.org)

Solving the Knight's Tour Puzzle In 60 Lines of Python

Posted by Soulskill on from the snakes-and-horsies dept.

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

4 of 311 comments (clear)

  1. better algo by Coneasfast · · Score: 5, Informative

    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.

    --
    Marge, get me your address book, 4 beers, and my conversation hat.
  2. Re:Perl by berend+botje · · Score: 5, Informative
    I thought you were being a smart-ass. You weren't:

    Chess::Piece::Knight.

    Perl is awesome!

  3. Re:Python uses lambda calculus? by Free+the+Cowards · · Score: 4, Informative

    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.

    --
    If you mod me Overrated, you are admitting that you have no penis.
  4. Re:Easy by RAMMS+EIN · · Score: 5, Informative

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

    M-x knights-puzzle

    Lisp doesn't use CamelCase.

    --
    Please correct me if I got my facts wrong.