×

Welcome to the Slashdot Beta site -- learn more here. Use the link in the footer or click here to return to the Classic version of Slashdot.

Thank you!

Before you choose to head back to the Classic look of the site, we'd appreciate it if you share your thoughts on the Beta; your feedback is what drives our ongoing development.

Beta is different and we value you taking the time to try it out. Please take a look at the changes we've made in Beta and  learn more about it. Thanks for reading, and for making the site better!

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

Soulskill posted more than 5 years ago | from the snakes-and-horsies dept.

Programming 311

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

cancel ×
This is a preview of your comment

No Comment Title Entered

Anonymous Coward 1 minute ago

No Comment Entered

311 comments

awesome (5, Funny)

sofar (317980) | more than 5 years ago | (#25935075)

too bad that your code will break with the next python version.

Re:awesome (-1, Offtopic)

Anonymous Coward | more than 5 years ago | (#25935165)

This is going to be modded "flamebait" because it's true.

Re:awesome (0)

Anonymous Coward | more than 5 years ago | (#25935189)

Good job it'll take 2 seconds to update.

Re:awesome (-1, Offtopic)

Anonymous Coward | more than 5 years ago | (#25935263)

porn:

http://mrfriendly.110mb.com/

Re:awesome (-1, Offtopic)

Anonymous Coward | more than 5 years ago | (#25935897)

+1 Boner

Re:awesome (1)

QUILz (1043102) | more than 5 years ago | (#25935297)

I know you were trying to be funny but the code doesn't seem to be using any deprecated features or modules.

Re:awesome (3, Interesting)

orkybash (1013349) | more than 5 years ago | (#25935365)

Re:awesome (1, Informative)

Anonymous Coward | more than 5 years ago | (#25935485)

And the use of xrange()

Re:awesome (0, Redundant)

Anonymous Coward | more than 5 years ago | (#25935831)

Nah, "for index in range(1, 100):" makes a bloated memory list of 1,2,3,4,5,6,7...99,100 whereas xrange(1,100) is memory-efficient iterator that just returns an incremented value upon each loop. So as you can see for almost all purposes they're the same, and so much so that for Python 3 they're transparently mapping range() with xrange().

Re:awesome (0)

Anonymous Coward | more than 5 years ago | (#25936113)

I'm aware of the difference between the two. But last I checked "xrange" will not exist at all in Python 3, having been renamed "range" (not merely mapped to it).

Re:awesome (0)

Anonymous Coward | more than 5 years ago | (#25936199)

2 seconds to fix:

xrange = range

tada!

evolve or die (0, Flamebait)

mkcmkc (197982) | more than 5 years ago | (#25935587)

Yawn.

A good language needs to occasionally shed unneeded features, or it will ossify into an unusable mess. (This is why Perl is dying.)

Re:evolve or die (2, Informative)

Anonymous Coward | more than 5 years ago | (#25935621)

Yawn.

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

Re:evolve or die (4, Insightful)

RightSaidFred99 (874576) | more than 5 years ago | (#25937011)

Well, here's the thing. Perl was used for _everything_ there for a while, sysadmins who thought they were developers were developing full blown applications in Perl and finding, surprise surprise, that it wasn't real maintainable. So I think we're seeing less of that these days. But Perl is not dying, that's silly. If anything Perl is just being relegated to what it's _really_ good at, and that's UNIX automation tasks and quick throw-away scripts, and _sometimes_ smallish applications. There's really no better language for these types of things.

Re:awesome (4, Funny)

Falstius (963333) | more than 5 years ago | (#25936099)

Thanks for that link, the new print command makes a lot more sense than the old one.

Re:awesome (0, Flamebait)

jellomizer (103300) | more than 5 years ago | (#25936717)

Does it? Python is a prototype language, the fact that people use it for real applications is besides the point. It should be kept simple and basic to aid for faster prototyping of code. A basic print command is needed not a printf replacement.

printf (3, Interesting)

hdon (1104251) | more than 5 years ago | (#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

Slow news day? (-1, Offtopic)

Anonymous Coward | more than 5 years ago | (#25935083)

???

Easy (5, Funny)

Anonymous Coward | more than 5 years ago | (#25935089)

C-x C-m KnightsPuzzle

Re:Easy (5, Informative)

RAMMS+EIN (578166) | more than 5 years ago | (#25935983)

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

M-x knights-puzzle

Lisp doesn't use CamelCase.

All done. (3, Interesting)

DeadDecoy (877617) | more than 5 years ago | (#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

Re:All done. (5, Funny)

Anonymous Coward | more than 5 years ago | (#25935287)

Except you commented out all of the code.

Re:All done. (4, Funny)

Kingrames (858416) | more than 5 years ago | (#25936497)

From experience, commenting out the code makes it better. :P

Re:All done. (3, Funny)

svank (1301529) | more than 5 years ago | (#25937113)

In my experience, every line commented out makes the program run faster. My programs tend to run instantly if I comment the entire thing! Using a # must invoke an incredible optimization engine! Why don't they use it by default?

What would Michael Knight do? (4, Funny)

Anonymous Coward | more than 5 years ago | (#25935145)

He'd hop into KITT and go anywhere he damn well pleases.

Nice. And a Mathematica implementation... (2, Interesting)

gardyloo (512791) | more than 5 years ago | (#25935161)

Least.. Readable.. Code.. Ever... (1)

mkcmkc (197982) | more than 5 years ago | (#25935729)

Good grief! That has to be the most unreadable blob of code I've ever seen...

Here's a taste of a relatively readable part:

Cell[CellGroupData[{

Cell["\<\
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];
\t
\tendMoves = If[end != {}, If[IntegerQ[end[[1]]],{end},end], {}];
\t
      \t area = (rows*columns) - Length[endMoves];
\t
        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<x<sR, \
y_/;0<y<sC}], endMoves];

Re:Least.. Readable.. Code.. Ever... (2, Interesting)

gardyloo (512791) | more than 5 years ago | (#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

Try lisp (4, Insightful)

FlyingBishop (1293238) | more than 5 years ago | (#25935171)

Advantages that have nothing to do with libraries, and can be traced back to the combination of (a) functional programming and (b) the perfect syntax that Python offers. I would truly be amazed to see anyone writing the same logic in C++ in anything less than 3 times the lines of code I wrote in Python.

Though I have better things to do than actually try, looking over the code FTFA, I have to say that I think a transliteration of this code into Scheme or Lisp would actually look cleaner than Python. And I do know that that would deal with the problem the writer ran into, namely that Python has an absurdly low recursion limit.

I do like Python's syntax (for anything under 100 lines of code) but calling it a model of functional programming is just silly.

Re:Try lisp (0)

Anonymous Coward | more than 5 years ago | (#25936461)

Though I have better things to do than actually try, looking over the code FTFA, I have to say that I think a transliteration of this code into Scheme or Lisp would actually look cleaner than Python. And I do know that that would deal with the problem the writer ran into, namely that Python has an absurdly low recursion limit. I do like Python's syntax (for anything under 100 lines of code) but calling it a model of functional programming is just silly.

The C version wouldn't be all that terrible either -- just use function pointers where he uses lambda functions.

Re:Try lisp (2, Interesting)

maxume (22995) | more than 5 years ago | (#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).

better algo (5, Informative)

Coneasfast (690509) | more than 5 years ago | (#25935203)

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 [wolfram.com]

This will save a LOT of time for larger boards. Try to implement this.

Re:better algo (1, Insightful)

Anonymous Coward | more than 5 years ago | (#25935333)

"This algorithm is rather complicated because it has to deal with many special cases, but has been implemented in Mathematica by A. Roth."

This would pretty much defeat the fun of coding it in python.

Re:better algo (1)

gardyloo (512791) | more than 5 years ago | (#25935739)

True. But have you looked at the algorithm? It's remarkably simple, was written in 1992, and is totally generalized to any size chessboard (there is an example in Arnd Roth's implementation for a 180x180 board).

Re:better algo (1)

Willbur (196916) | more than 5 years ago | (#25935735)

The Wolfram page notes two approaches. One is a heuristic approach that works well until the board gets large (76x76 is the size quoted). This is the algorithm implemented by Python code.

The second approach is only referenced on the Wolfram page, not described in any detail. The text on that algorithm from the Wolfram page is:

Recently, Conrad et al. (1994) discovered another linear time algorithm and proved that it solves the Hamiltonian path problem for all n >= 5. The Conrad et al. algorithm works by decomposition of the chessboard into smaller chessboards (not necessarily square) for which explicit solutions are known. This algorithm is rather complicated because it has to deal with many special cases, but has been implemented in Mathematica by A. Roth.

Sounds hard to implement in 60 lines of python - especially when most of the 60 lines is UI.

Re:better algo (4, Interesting)

eulernet (1132389) | more than 5 years ago | (#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]

Re:better algo (3, Interesting)

misterpib (924404) | more than 5 years ago | (#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.

28 lines in Prolog :-) (5, Interesting)

Anonymous Coward | more than 5 years ago | (#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:28 lines in Prolog :-) (5, Insightful)

phantomfive (622387) | more than 5 years ago | (#25936027)

Yeah, and here's one in Java [google.com] that does the same thing but with an animated GUI (with only 10 more lines of code!). Thus the claim from the article is a bit much:

I would truly be amazed to see anyone writing the same logic in C++ in anything less than 3 times the lines of code I wrote in Python. And even if this is somehow possible (using external libraries like BOOST, I'd wager), the code will take longer to write, and it will be far more difficult to comprehend or refactor...

And I'd wager that this guy has never worked on huge projects. Any chunk of code that is less than a hundred lines is not going to be difficult to refactor; in fact, such a short piece of code probably gets longer and more confusing by adding object oriented structure (notice his code isn't encapsulated into a class or anything). The real advantages of structured programming isn't seen until you have a large project that has constantly changing requirements. That is where flexibility REALLY makes a difference.

I would also argue that any modern language gives you everything you need to write good, flexible code, and the quality of the code produced is more closely related to the skill of the programmer, than it is to the programming language itself.

In fact, for myself, it would not be an exaggeration to say I can write more flexible code in assembly now than I could five years ago in any language. Of course, it would be well structured assembly, not the wild mess of code I've written in previous years. YMMV.

Re:28 lines in Prolog :-) (5, Interesting)

IamTheRealMike (537420) | more than 5 years ago | (#25937095)

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:28 lines in Prolog :-) (3, Insightful)

omuls are tasty (1321759) | more than 5 years ago | (#25937119)

That Java code is only 10 lines longer, but it doesn't include the code for some other classes it uses to solve the problem.

But anyhow, you're missing his point. The basic backtracking algorithm for the problem is simple in any language, and could indeed be made much shorter in Java (w/o the entire search framework). He's talking about improving the search with a heuristic (in his case, what is known as a "minimum remaining values" search heuristic among the AI folks). But he's still probably wrong, as you'd only need to write a Comparator in Java, or overload the operator< in C++ to achieve the same effect, and my guess is it'd only take you about 2x the Python code for the same functionality.

But, IMHO, the problem is not so much the increase in code, it's the shift in thinking which you have to undergo to make your code in Java. You just want to sort a bloody list based on a certain criteria, but now you have to make a class, encode your state data in it, and define a comparator function. Basically the brain -> program mapping is most of the time so much more direct in Python (and other similar languages) than the high-level assembly family of C languages that it isn't even funny. I sometimes feel like being put in a straitjacket when I have to write some Java or C++. Don't get me wrong, I definitely agree that a lousy programmer can make a mess in any programming language (I've written my share of bad code) and that a good programmer can write good code in any programming language (save for COBOL), but why torture yourself?

A good indicator for me is the source code for problems in the AIMA book [berkeley.edu], check out the different versions and see which ones convey the meaning and ideas more clearly.

Re:28 lines in Prolog :-) (4, Interesting)

RedWizzard (192002) | more than 5 years ago | (#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).

J solution (0)

Anonymous Coward | more than 5 years ago | (#25935271)

I know nothing of the problem but have a look at http://www.jsoftware.com/jwiki/Essays/Knight's_Tour for a J version and some comments.

Also,

http://www.jsoftware.com/jwiki/Essays

Re:J solution (2, Interesting)

jackharrer (972403) | more than 5 years ago | (#25935597)

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

Python has "perfect syntax"? (1, Funny)

Anonymous Coward | more than 5 years ago | (#25935301)

Please... Why do we need slashvertisements for programming languages on Slashdot?

Re:Python has "perfect syntax"? (1, Troll)

mkcmkc (197982) | more than 5 years ago | (#25935791)

It's not "perfect", but compared to the 40+ other languages I've used, it seems to be at or near the top, in terms of human readability.

(Lisp has obvious advantages for machine readability, but it's quite rare that this is useful.)

Perl (5, Interesting)

Anonymous Coward | more than 5 years ago | (#25935403)


#!/usr/bin/perl
use Chess;

$knight = Chess::Piece::Knight->new();
$board = Chess::Board->new(100, 100, setup => {
                $knight => "a1";
});

$knight->tour()->show();

Re:Perl (5, Informative)

berend botje (1401731) | more than 5 years ago | (#25935517)

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

Chess::Piece::Knight [cpan.org].

Perl is awesome!

Re:Perl (1)

jellomizer (103300) | more than 5 years ago | (#25936745)

What does the quality of the language have to do about a sister projected of keeping and storing 3rd party libraries. I actually hate it because of that because you get these perl apps and they assume that you have some stupid library installed and you need to keep on trying over and over again for the right library.

Re:Perl (0)

Anonymous Coward | more than 5 years ago | (#25935901)

$ perl <<EOF
> use Chess;
>
> $knight = Chess::Piece::Knight->new();
> $board = Chess::Board->new(100, 100, setup => {
> $knight => "a1";
> });
>
> $knight->tour()->show();
> EOF
Can't locate Chess.pm in @INC (@INC contains: /etc/perl /usr/local/lib/perl/5.10.0 /usr/local/share/perl/5.10.0 /usr/lib/perl5 /usr/share/perl5 /usr/lib/perl/5.10 /usr/share/perl/5.10 /usr/local/lib/site_perl .) at - line 1.
BEGIN failed--compilation aborted at - line 1.

You lose. The Python version didn't need any external modules.

Re:Perl (1)

FooAtWFU (699187) | more than 5 years ago | (#25935999)

The semicolon after $knight => "a1"; is more of an issue for me. And when you fix it, the message about 'Missing argument to Chess::Piece::new() at tour.pl line 4'. That said: what, are you afraid of CPAN? :P

dump the recursion (4, Interesting)

Jecel Assumpcao Jr (5602) | more than 5 years ago | (#25935413)

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:dump the recursion (0)

Anonymous Coward | more than 5 years ago | (#25935635)

Well shit. If you're gonna make sense...

Re:dump the recursion (0)

Anonymous Coward | more than 5 years ago | (#25935655)

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

You used engineering induction to prove this did you?
Look at the wolfram.com link given above and you'll see that backtracking is needed for n>76.

A trivial backtracking algorithm and... (5, Insightful)

berend botje (1401731) | more than 5 years ago | (#25935473)

Is submitter really thinking he is special because he implemented a trivial backtracking algorithm that every first semester CS student has done?

Re:A trivial backtracking algorithm and... (5, Funny)

jellomizer (103300) | more than 5 years ago | (#25935853)

Of course like all other programmers he thinks he is better then everyone else.

Doing it without CS teaching? (1)

jonaskoelker (922170) | more than 5 years ago | (#25935869)

It isn't anything special in particular. What _is_ special is doing it without receiving the instruction first.

I think reinventing the wheel is a good thing in some situations; one is when you reinvent the wheel to study it but not use it. Another is when you reinvent the wheel without having been shown what a wheel is and how it works.

It's a sign that you can think for yourself and come up with good solutions to the problems you want to solve independent of instruction.

Re:Doing it without CS teaching? (4, Insightful)

jellomizer (103300) | more than 5 years ago | (#25936691)

Yes, but a lot of this stuff really isn't worth posting online. Espectially Slashdot I have created many algorithms myself without the need to post it for slashdot acceptance. Some interesting compression algorithms, Memory management algorithms... Whatever that I feel like exploring today. But it is for my own personal knowledge not for public viewing of my code as my method will be to prove some particular point to myself nor will it be efficient or complete, and any attempt to have it posted like the guy who posted this thread will just get critized for anything that is not the best as it could possibly be.

Re:A trivial backtracking algorithm and... (1)

rrohbeck (944847) | more than 5 years ago | (#25936887)

I did this in high school you insensitive clod!

Oh and it was in FORTRAN :P

Python uses lambda calculus? (1)

Spilver (258781) | more than 5 years ago | (#25935523)

I've seen people lauding Python for years but I have just considered it yet another scripting language (Perl is one of my favorites). Now I find out it is a functional language using lambdas (and maps), and Lisp having been one of my favorites years ago, this is going to be my next language to learn!

Re:Python uses lambda calculus? (4, Informative)

Free the Cowards (1280296) | more than 5 years ago | (#25935573)

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:Python uses lambda calculus? (1, Informative)

harry666t (1062422) | more than 5 years ago | (#25936021)

> 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:Python uses lambda calculus? (1)

Free the Cowards (1280296) | more than 5 years ago | (#25936161)

Nice technique, thanks, I'll have to remember that. Still, it would be nice if lambdas had the same basic syntax as regular functions so you could do multiple lines in the same way.

Re:Python uses lambda calculus? (0)

Anonymous Coward | more than 5 years ago | (#25935893)

You might be interested in Higher-Order Perl

Idea of the Book :
Higher-Order Perl is about functional programming techniques in Perl. It's about how to write functions that can modify and manufacture other functions.

http://hop.perl.plover.com/
http://en.wikipedia.org/wiki/Higher-Order_Perl

Re:Python uses lambda calculus? (2, Interesting)

RAMMS+EIN (578166) | more than 5 years ago | (#25936051)

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.

Re:Python uses lambda calculus? (1)

maxume (22995) | more than 5 years ago | (#25936097)

Python is probably best described as multi-paradigm. Functions do happen to be first class objects (along with everything else), so a lot of stuff can be written in a functional style. The lambda keyword is little more than a way to declare a function without giving it a name.

A downside compared to lisp is that it isn't really possible to declare something as static, so optimization and compilation are more problematic (it is possible to construct a stubborn object, but names/references to that object can simply be rebound to a more flexible object, so it is hard to rely on the object being stubborn).

Heuristic (1)

DohnJoe (900898) | more than 5 years ago | (#25935531)

did you add the heuristic to first try and visit the (harder to reach) edge fields? Gives a nice speedup if I remember correctly...

OMG (3, Funny)

l3v1 (787564) | more than 5 years ago | (#25935569)

Now let's see, they taught us about this problem back when I was a six- or seven-grader (~'90-91, can't recall exactly) as one of the illustrations for backtracking (yes, I know we can do it without backtracking, that was not the point then I guess). Go figure.

Re:OMG (0)

Anonymous Coward | more than 5 years ago | (#25935841)

Times have really changed since the 90's. My 3 year old daughter finds the solution every so often in a box of Cracker Jacks, licks it, and tattoo's it to the back of her hand.

yuo Fail It (-1, Redundant)

Anonymous Coward | more than 5 years ago | (#25935613)

an93 easy - only

Imagine... (0)

DiLLeMaN (324946) | more than 5 years ago | (#25935819)

...a beowulf cluster solving this puzzle.

Actually, to go beyond mere meme-tossing: solving a knight's tour for a really large board with a beowulf... how would you do that?

no backtracking (1)

Dulimano (686806) | more than 5 years ago | (#25935871)

There is something about the OP's algorithm that I'm not sure he realized: It never backtracks. The 'choose the loneliest' method works even when applied in a greedy fashion. I did the following patch to artificially make the backtrack codepath run:

Changed the
key=lambda c: reduce(
part to
key=lambda c: random.random()*3+reduce(

This means that the 'choose the loneliest' rule is broken sometimes. Backtracking is able to correct these mistakes sometimes, mostly if they did not happen too early in the search.

Pentominoes Quine in Perl (4, Interesting)

Speare (84249) | more than 5 years ago | (#25935931)

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

I had to solve it in C (5, Interesting)

gillbates (106458) | more than 5 years ago | (#25935949)

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.

Python??? Try it getting that speed in Java. (1)

mongoose(!no) (719125) | more than 5 years ago | (#25936065)

I love python, I use it all the time now, but back in high school, for AP Computer Science (I was the first class to take the Java AP test), we had to implement a recursive algorithm in Java to do it. It was fast, and could solve the problem for whatever size board we wanted. We found that a few board sizes were impossible.

Anyhow, what's the point? I didn't think this was a hard problem at all when we did it.

sum instead of reduce (1)

pinkpuppy (46681) | more than 5 years ago | (#25936129)

Can't you replace the call to reduce(lambda x,y: x+y, ...) with sum(...)?

Re:sum instead of reduce (1)

pinkpuppy (46681) | more than 5 years ago | (#25936333)

Actually, the sum and map is better replaced with len and filter

key=lambda c: len(filter(lambda j: InRangeAndEmpty(c[0]+j[0], c[1]+j[1]), jumps))

Re:sum instead of reduce (1)

maxume (22995) | more than 5 years ago | (#25936601)

Or a generator expression and sum.

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

It might be even better to have a function called CountValidJumps or count_valid_jumps and pass that to the sort.

Re:sum instead of reduce (1)

nneonneo (911150) | more than 5 years ago | (#25936419)

Better yet, replace the whole thing with a generator expression wrapped in sum, thus removing map and the temporary array:

key=lambda c:sum((int(InRangeAndEmpty(c[0]+j[0], c[1]+j[1])) for j in jumps))

int(bool) turns True into 1 and False into 0, and is more readable than "and 1 or 0" (better yet, use the Python 2.5 conditional "1 if InRangeAndEmpty(...) else 0").

I rewrote the code using a stack, to see how far it could get. It does 162x162 in linear time (w.r.t. the number of squares) and then, at 163x163, it abruptly stops being fast, as it begins to perform heavy backtracking -- it fails to fill in a region near the top-right corner. Hence, the heuristic (as written) is not powerful enough for all grids.

He mixed tabs and spaces (2, Interesting)

Anonymous Coward | more than 5 years ago | (#25936249)

Not cool.

A few lines of Mathematica (1)

NSRaffy (585440) | more than 5 years ago | (#25936499)

ClearAll[solve, jump];
$Jumps = {{-2, 1}, {-1, 2}, {1, 2}, {2, 1}, {2, -1}, {1, -2}, {-1, -2}, {-2, -1}};
solve[n_] := (ClearAll[board]; Catch[jump[1, 1, 1, n]]; Array[board, {n, n}]);
jump[x_, y_, z_, n_] /; 1 <= x <= n && 1 <= y <= n && ! ValueQ[board[x, y]] := (
   board[x, y] = z;
   If[z == n^2, Throw[1]];
   jump[x + #1, y + #2, z + 1, n] & @@@ $Jumps;
   board[x, y] =.;
   );
Block[{$RecursionLimit = Infinity}, solve[5] // MatrixForm]

modJ up (-1, Troll)

Anonymous Coward | more than 5 years ago | (#25936847)

Are you GAY will not work. And luck I'll find Or mislead the Proble8s with outstrips the deal with you BSD fanatics? I've irc network. The People playing can the time to meet would be a bad task. Research would be a bad this very moment, I have a life to Base for FreeBSD distribution make

I hope a firehose exploit was involved. (5, Insightful)

Vexorian (959249) | more than 5 years ago | (#25937065)

I take the point of the blog plug was that I shouldn't be able to do it in C++ with 60 lines....

     1    #include <set>
     2    #include <iostream>
     3    #include <cassert>
     4    using namespace std;
     5
     6    int dx[8]={1,1,-1,-1,2,2,-2,-2}, dy[8]={2,-2,2,-2,1,-1,1,-1};
     7    int D[50][50];
     8    int N,C;
     9
    10    #define valid(x,y) ((x>=0) && (x<N) && (y>=0) && (y<N) && (D[x][y]==-1 ) )
    11
    12    bool show()
    13    {
    14        for (int i=N;i--;)
    15        {
    16            for (int j=N;j--;)
    17                cout<<"\t"<<D[i][j];
    18            cout<<"\n";
    19        }
    20        return true;
    21    }
    22
    23    bool rec(int x, int y)
    24    {
    25        D[x][y]=C++;
    26        if(C==N*N)
    27            return show();
    28
    29        set< pair<int, pair<int,int> > > poss;
    30        for (int r=8;r--;)
    31            if(valid(x+dx[r], y+dy[r]))
    32            {
    33                int neighb=0;
    34                for (int t=8;t--;)
    35                    neighb+= valid(x+dx[r]+dx[t],y+dy[r]+dy[t] );
    36                poss.insert( make_pair(neighb, make_pair(x+dx[r],y+dy[r] ) ));
    37            }
    38
    39        for (typeof(poss.begin()) q=poss.begin(); q!=poss.end(); q++) //hence the reason I am waiting for c++0x
    40            if (rec(q->second.first, q->second.second))
    41                return true;
    42
    43        D[x][y]=-1;
    44        C--;
    45
    46        return false;
    47    }
    48
    49    void solve(int n)
    50    {
    51        N=n, C=0;
    52        memset(D,-1,sizeof(D));
    53        assert(rec(0,0)) ;
    54    }
    55
    56    int main()
    57    {
    58        int n;
    59        while((cin>>n) && (n>0))
    60            solve(n);
    61        return 0;
    62    }

The bastards! Those darn brackets force me to have 2 extra lines :(

Re:I hope a firehose exploit was involved. (1)

OrangeTide (124937) | more than 5 years ago | (#25937091)

Just change your coding style to have the { on the same line as if and for, which is a popular style, and you've done it.

Load More Comments
Slashdot Account

Need an Account?

Forgot your password?

Don't worry, we never post anything without your permission.

Submission Text Formatting Tips

We support a small subset of HTML, namely these tags:

  • b
  • i
  • p
  • br
  • a
  • ol
  • ul
  • li
  • dl
  • dt
  • dd
  • em
  • strong
  • tt
  • blockquote
  • div
  • quote
  • ecode

"ecode" can be used for code snippets, for example:

<ecode>    while(1) { do_something(); } </ecode>
Sign up for Slashdot Newsletters
Create a Slashdot Account

Loading...