Want to read Slashdot from your mobile device? Point it at m.slashdot.org and keep reading!

 



Forgot your password?
typodupeerror
Programming Math IT Technology Entertainment Games

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

Posted by Soulskill
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!"
This discussion has been archived. No new comments can be posted.

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

Comments Filter:
  • All done. (Score:3, Interesting)

    by DeadDecoy (877617) on Sunday November 30, 2008 @02:06PM (#25935131)
    There. I did it in one line of code.
    #!/usr/bin/env python import sys g_sqSize = -1 # the board size, passed at runtime g_board = [] # the board will be constructed as a list of lists def main(): global g_sqSize if len(sys.argv) != 2: g_sqSize = 8 # Default: Fill the normal 8x8 chess board else: try: g_sqSize = int(sys.argv[1]) # or, the NxN the user wants except: print "Usage: " + sys.argv[0] + " " sys.exit(1) for i in xrange(0, g_sqSize): g_board.append(g_sqSize*[0]) # Fill the board with zeroes Fill(0,0,1) # Start the recursion with a 1 in the upper left print "No solution found" # if the recursion returns, it failed def InRangeAndEmpty(ty,tx): # check if coordinates are within the board return ty>=0 and tx>=0 and ty
  • by gardyloo (512791) on Sunday November 30, 2008 @02:09PM (#25935161)
  • by Anonymous Coward on Sunday November 30, 2008 @02:17PM (#25935257)

    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:awesome (Score:3, Interesting)

    by orkybash (1013349) <tim.bocek@gm a i l . c om> on Sunday November 30, 2008 @02:26PM (#25935365)
  • Perl (Score:5, Interesting)

    by Anonymous Coward on Sunday November 30, 2008 @02:29PM (#25935403)


    #!/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 (Score:5, Interesting)

    by Jecel Assumpcao Jr (5602) on Sunday November 30, 2008 @02:30PM (#25935413) Homepage

    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.

  • Re:J solution (Score:3, Interesting)

    by jackharrer (972403) on Sunday November 30, 2008 @02:48PM (#25935597)

    It's even less readable that PERL. Shit, I didn't think it's possible. And I used to "program" in PERL...

  • by shking (125052) <(babulicm) (at) (cuug.ab.ca)> on Sunday November 30, 2008 @03:13PM (#25935845) Homepage
    Here's a solution in 14 lines of APL [dyalog.com]. 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".
  • by gardyloo (512791) on Sunday November 30, 2008 @03:14PM (#25935857)

    That's because you're looking at some MathML code. What one actually types into Mathematica, and sees in Mathematica (or sees in a raw text file version IF the "InputForm" of the code is looked at) is the following. Unfortunately, the code ends suddenly because slashcode somehow doesn't allow more to be shown. BAAAAAD slashcode.

          Complaining about the readability of what you posted is like complaining about the raw HTML which goes into this webpage.

    KnightTour[rows_Integer, columns_Integer, start_List, end_List:{}, HidePaths_Integer:0] :=
          Module[{sR = rows+1, sC = columns+1, i = 0, j = 0, path, endMoves, tree = {0}, SNew, KnightMoves, FeasibleMoves, area},

                      path = If[IntegerQ[start[[1]]], {start}, start];

            endMoves = If[end != {}, If[IntegerQ[end[[1]]],{end},end], {}];

                            area = (rows*columns) - Length[endMoves];

            KnightMoves[lis_List] := KnightMoves[lis] = Complement[
                    Cases[ Map[ lis +#&, {{1,2},{1,-2},{-1,2},{-1,-2},{2,1},{2,-1},{-2,1},{-2,-1}}],
                                {x_/; 0

  • by Speare (84249) on Sunday November 30, 2008 @03:21PM (#25935931) Homepage Journal
    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 [halley.cc]
    • 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
  • by gillbates (106458) on Sunday November 30, 2008 @03:25PM (#25935949) Homepage Journal

    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.

  • by Intron (870560) on Sunday November 30, 2008 @03:38PM (#25936041)

    http://anthonyf.wordpress.com/2006/07/07/solving-the-knights-tour [wordpress.com]

    I think even if you didn't know any lisp you would find this solution to be pretty readable.

  • by RAMMS+EIN (578166) on Sunday November 30, 2008 @03:39PM (#25936051) Homepage Journal

    Not to stir up old debates again, but if you like Lisp, you might be better off going for Ruby than for Python. Coming from a Scheme background, I find Ruby to be the more elegant language.

    Python is a great language, but my feeling about it is that it's designed to support one way of programming (and not even completely - it's sort of ambivalent between procedural and object-oriented). This is fine, and has the advantage off encouraging consistency among programs from different authors. However, I feel there is a better way: just give programmers building blocks and let the programmers compose them in any way they like. I feel Ruby does this, and the result is a language in which you can elegantly build your program in any way you like. In particular, I feel pure functional style is more natural in Ruby than in Python.

  • by Anonymous Coward on Sunday November 30, 2008 @03:59PM (#25936249)

    Not cool.

  • Re:Try lisp (Score:2, Interesting)

    by maxume (22995) on Sunday November 30, 2008 @04:26PM (#25936523)
    His code:

        # recurse using our neighbours, trying first the ones with the
        # least amount of free neighbours, i.e. the "loners"
        for ty,tx in sorted(emptyNeighbours, key=lambda c: reduce(
        lambda x,y: x+y,
        map(lambda j: InRangeAndEmpty(c[0]+j[0], c[1]+j[1]) and 1 or 0,
            jumps))):
            Fill(ty,tx,counter+1)

    Idiomatic python(or at least more-so):

        def sort_key(c):
            return sum(InRangeAndEmpty(c[0]+j[0], c[1]+j[1]) for j in jumps)

        # recurse using our neighbours, trying first the ones with the
        # least amount of free neighbours, i.e. the "loners"
        for ty,tx in sorted(emptyNeighbours, key=sort_key):
            Fill(ty,tx,counter+1)

    The nest of lambdas that he wrote the article about isn't the clearest way to write it in python (the reduce( lambda x,y: x+y,...) instead of sum(...) is particularly fun). In my code, wrapping the InRangeAndEmpty in an int() might be preferred, I'm not sure (all that would do is make it clear that the sum is counting the number of squares that are in range and empty).
  • by Anonymous Coward on Sunday November 30, 2008 @04:34PM (#25936587)

    See also this sudoku solver
    http://www.youtube.com/watch?v=q1I7WKncE64 [youtube.com]

  • Re:better algo (Score:5, Interesting)

    by eulernet (1132389) on Sunday November 30, 2008 @04:53PM (#25936723)

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

  • printf (Score:3, Interesting)

    by hdon (1104251) on Sunday November 30, 2008 @05:00PM (#25936759)

    A basic print command is needed not a printf replacement.

    Point of fact: Python has the sexiest sprintf() support available. Observe..

    >>> print "I ate %d %s in %.3f seconds" % (99,'hotdogs',62.0895)
    I ate 99 hotdogs in 62.090 seconds

  • by RedWizzard (192002) on Sunday November 30, 2008 @05:02PM (#25936777)
    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).
  • by IamTheRealMike (537420) <mike@plan99.net> on Sunday November 30, 2008 @05:35PM (#25937095) Homepage

    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.

  • Re:better algo (Score:3, Interesting)

    by misterpib (924404) on Sunday November 30, 2008 @05:37PM (#25937127)
    A non-recursive Python version which uses Warnsdorf's heuristic:
    http://github.com/pib/scripts/tree/master/knight.py [github.com]

    It's faster than the one in TFA as well, though it has no backtracking, so it won't find some solutions once you get bigger than 76x76, but at least it doesn't overflow the stack.

    It also will tell you whether it found an open, closed, or incomplete path.
  • by nneonneo (911150) <spam_hole@nOsPaM.shaw.ca> on Sunday November 30, 2008 @05:40PM (#25937155) Homepage

    TFA has basically stumbled upon Warnsdorff's algorithm [wikipedia.org]. It's a great method, but it doesn't work for really large boards due to blind alleys. There's another method available which uses decomposition to achieve a linear running time(in # of squares), but which is quite a bit more complex to implement. There's a nice tweak to the algorithm which can get much farther than the unmodified original: in the event of a tie (where two candidates have the same number of open neighbours), break the tie by choosing the square farthest from the center. This substantially extends the maximum size of the board (to what, I don't know, because it's worked for everything up to around 450x450, which is past what was described by Arnd Roth [wolfram.com]).

  • Re:Try lisp (Score:4, Interesting)

    by BlueCodeWarrior (638065) <steevk@gmail.com> on Sunday November 30, 2008 @06:08PM (#25937409) Homepage

    I won't pretend to remember Lisp inventor John McCarthy's exact words which is odd because there were only about ten but he simply asked if Python could gracefully manipulate Python code as data. "No, John, it can't," said Peter and nothing more, graciously assenting to the professor's critique, and McCarthy said no more though Peter waited a moment to see if he would and in the silence a thousand words were said.

    http://smuglispweeny.blogspot.com/2008/02/ooh-ooh-my-turn-why-lisp.html [blogspot.com]

  • by mkcmkc (197982) on Sunday November 30, 2008 @08:25PM (#25938511)

    I like Lisp a lot, and I certainly prefer its syntax to Java or C (or--god help us all--C++), but I still think that it is clearly less readable than Python.

    If there's a serious argument against this, it must be Lisp's macro capabilities...
     

  • by Anonymous Coward on Sunday November 30, 2008 @09:23PM (#25939013)

    27 lines of Haskell. LogicT monad FTW!

    http://haskell.org/haskellwiki/The_Knights_Tour#LogicT_monad

  • Re:awesome (Score:3, Interesting)

    by earthbound kid (859282) on Sunday November 30, 2008 @10:11PM (#25939361) Homepage

    Here's code you can put in your Python 2.x code today to future proof it against the change to xrange:

    try:
          range = xrange
    except NameError:
          pass

    After that, just write range in your code and it will automatically use the equivalent of Python 2's xrange. If you're running Python 2.6, you can use a print function (instead of a print keyword) by adding from __future__ import print_function to your header as well, and you're good to go for a large number of Python 3 switching problems.

  • 3D chess (Score:2, Interesting)

    by jagdish (981925) on Sunday November 30, 2008 @10:40PM (#25939579)
    But does it work with 3 dimensional chess?
  • Batteries included (Score:4, Interesting)

    by XNormal (8617) on Monday December 01, 2008 @04:03AM (#25941159) Homepage

    There is an elegant Knight's Tour solver right inside your Python distribution. You can find it at /usr/lib/python2.5/test/test_generators.py [python.org]. Written by Tim Peters (a.k.a. timbot).

  • Re:Easy (Score:3, Interesting)

    by Simon Brooke (45012) <stillyet@googlemail.com> on Monday December 01, 2008 @04:29AM (#25941311) Homepage Journal

    Lisp doesn't use CamelCase.

    Don't show off your ignorance too much. LISP has used CamelCase for at least thirty years. Admittedly neither Scheme nor Common LISP conventionally use it, but InterLISP certainly does.

Dennis Ritchie is twice as bright as Steve Jobs, and only half wrong. -- Jim Gettys

Working...