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

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