Slashdot Mirror
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!"
too bad that your code will break with the next python version.
C-x C-m KnightsPuzzle
"rm -rf knights"
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
He'd hop into KITT and go anywhere he damn well pleases.
... here: http://www.tri.org.au/tourcode.html
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.
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.
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).
Please... Why do we need slashvertisements for programming languages on Slashdot?
#!/usr/bin/perl
use Chess;
$knight = Chess::Piece::Knight->new();
$board = Chess::Board->new(100, 100, setup => {
$knight => "a1";
});
$knight->tour()->show();
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.
Is submitter really thinking he is special because he implemented a trivial backtracking algorithm that every first semester CS student has done?
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!
did you add the heuristic to first try and visit the (harder to reach) edge fields? Gives a nice speedup if I remember correctly...
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.
I am putting myself to the fullest possible use, which is all I can think that any conscious entity can ever hope to do.
It's even less readable that PERL. Shit, I didn't think it's possible. And I used to "program" in PERL...
"an experienced, industrious, ambitious, and often, quite often, picturesque liar" - Mark Twain
Yawn.
Another claim that Perl is "in its last throes".
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]; := KnightMoves[lis] = Complement[
\t
\tendMoves = If[end != {}, If[IntegerQ[end[[1]]],{end},end], {}];
\t
\t area = (rows*columns) - Length[endMoves];
\t
KnightMoves[lis_List]
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];
"Not an actor, but he plays one on TV."
Here's a solution in 14 lines of APL. 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".
-- "At Microsoft, quality is job 1.1" -- PC Magazine, Nov. 1994
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.
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.
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.
[
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.
The society for a thought-free internet welcomes you.
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.
Can't you replace the call to reduce(lambda x,y: x+y, ...) with sum(...)?
Not cool.
ClearAll[solve, jump]; := (ClearAll[board]; Catch[jump[1, 1, 1, n]]; Array[board, {n, n}]); /; 1 <= x <= n && 1 <= y <= n && ! ValueQ[board[x, y]] := ( // MatrixForm]
$Jumps = {{-2, 1}, {-1, 2}, {1, 2}, {2, 1}, {2, -1}, {1, -2}, {-1, -2}, {-2, -1}};
solve[n_]
jump[x_, y_, z_, n_]
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]
seriously, is this "article" some bad joke?
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
Just by-the-by, there is no such thing as PERL. All acronyms for the language Perl's name are backronyms, and were created after the fact. Perl is the language, perl is the interpreter. Please refer to http://abelew.web.wesleyan.edu/perl_flame.html
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.
I take the point of the blog plug was that I shouldn't be able to do it in C++ with 60 lines....
//hence the reason I am waiting for c++0x ;
:(
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++)
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
Copyright infringement is "piracy" in the same way DRM is "consumer rape"
TFA has basically stumbled upon Warnsdorff's algorithm. 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).
He's preached against premature optimization for years.
Timed with Debian on EEE 901 in HT mode (1.6 GHz Atom)
/* The size of the thing, is set in main */ :) */
/* set our stamp here */ /* Were done */ /* for each type of jump */ /* set new position */ /* outch. been there or outside*/ /* were finished, just return*/ /* we could not walk anywhere, reset and ... */ /* move back indicating failure */
/* Draw the board */
/* get size */ /* Alloc space for board */ /* clear space */ /* Start at defined start position */ /* Draw board that is done */ /* Yay, done */
real 0m0.726s
user 0m0.724s
sys 0m0.004s
K&R (more or less), with tab-space=8 inside 79 cols. But commenting as original pyton (end of line commenting).
-----
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int startx = 0, starty=0, size=0;
/* How knights walk, changing this changes the time outcome
int jumps[][2] = {{-2,1},{-1,2},{1,2},{2,1},{2,-1},{1,-2},{-1,-2},{-2,-1}};
int walk(int *board, const int x, const int y, const int step)
{
board[x*size+y] = step;
if (step == size*size)
return 1;
for (int i=0;i<8;++i) {
int xx = x + jumps[i][0], yy = y + jumps[i][1];
if (xx < 0 || yy < 0 || xx >= size || yy >= size || board[xx*size+yy])
continue;
if (walk(board, xx, yy, step + 1))
return 1;
}
board[x*size+y] = 0;
return 0;
}
void draw(const int *board, int x, int y)
{
for (int i=0;i<size*size;++i) {
printf(" %4d", board[i]);
if (((i+1) % size) == 0)
printf("\n");
}
}
int main(int argc, char *argv[])
{
if (argc != 2 || ((size = atoi(argv[1])) == 0))
return printf("use: %s <size>\n", argv[0]) + 1;
printf("Board of size %dx%d\n", size, size);
unsigned int board[size*size];
memset(board, 0, sizeof(int) * size * size);
walk(board, startx, starty, 1);
draw(board, -1, -1);
return 0;
}
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.
Memo to OP: Never, never, brag how short your code is, especially if you're using something as bloated as Python.
There's always a more concise way. And a faster way.
You're just asking for a beating, and well-deserved.
you had me at #!
> Try beating this, fellow coders!
.<set board=.size.<for_each combiner=insert> .size.<for_each combiner=insert> false </for_each> </for_each> /> .<fill/> .board.<has y/> .board.<get y/>.<has x/> .board.<get y/>.<get x/>.<not/> /> .board.<get y/>.<set <do x/>=counter/> .size.<times .size/> /> />.<for_each> /> .<in_range_and_empty x=new_x y=new_y/> .<fill x=new_x y=new_y counter=counter.<plus 1/> /> </if> /> .board.<for_each>
Here it is in 30 lines of Water. Oh, and it outputs in HTML.
<class knights_tour size=8 board=opt >
<method make>
_subject
</method>
<method in_range_and_empty x=req y=req>
<and
</method>
<method fill x=0 y=0 counter=0>
<if>
counter.<is_not
<v <v -2 1/> <v -1 2/> <v 1 2/> <v 2 1/> <v 2 -1/> <v 1 -2/> <v -1 -2/> <v -2 -1/>
<set new_y=y.<plus value.0/> new_x=x.<plus value.1/>
<if>
</for_each>
</if>
</method>
<method htm_inst>
<set a_table=<table border=1/>
<set a_row=<tr/>/>
value.<for_each> a_row.<insert <td value/>/> </for_each>
a_table.<insert a_row/>
</for_each>
a_table
</method>
</class>
<knights_tour/>
(My formatting is getting messed up. Should be 30. It's merging a few lines in the preview, but not in a way that would break anything.)
No idea how to do it but I'm seeing a pattern in these arguments.
i wish i could stop
It's a pretty poor language, if if makes its users confuse code that calls external modules with actual implementations.
The site is down, but here are some links from Google's cache: http://74.125.95.132/search?q=cache%3Attsiodras.googlepages.com%2Fknightstour.html http://74.125.95.132/search?q=cache%3Ahttp%3A%2F%2Fttsiodras.googlepages.com%2Fyield.html That's all I could get, I'm sorry. Apparently Google doesn't cache Python documents.
http://rubyquiz.com/quiz27.html
quite a nice solution in ruby - if you took the commenting out, it'd be pretty short...
full credit to the owner of the page for the solution, i just figured someone would have a nice solution in ruby, and this came up through google.
See http://www.haskell.org/haskellwiki/99_questions/90_to_94 for the really obvious solution.
object[] finalBoard = System.Math.KnightsTour(64);
But does it work with 3 dimensional chess?
Can't copy n' paste the code here because I get the message: "Try not to use so many 'junky' words"! So, this is how Slashdot behaves to the language that brought it to life. Anyway,you can find the Perl script here.
This is the question techies never want to talk about though it's often more relevant than how quickly it runs. Here's a solution in J in fewer than 20 lines: http://www.jsoftware.com/jwiki/Essays/Knight's_Tour .
Here's a working (although somewhat messy) implementation in Lua. I could probably optimise performance and/or LoC, but that's another exercise. :)
It accepts an optional size parameter (defaults to 8), prints out the running time, and the solution if it's <= 16x16.
http://pastebin.ca/1272049
Running times on Ubuntu Feisty 32-bit on a P4 2.8: ...still going :)
8x8 = 0.000s, or thereabouts...
100x100 = 0.400s
200x200 = 1.740s
300x300 = 3.950s
400x400 = 7.040s
500x500 = 10.080s
600x600 = 15.240s
700x700 = 20.180s
800x800 = 33.670s
900x900 = 42.580s
1000x1000 = 53.480s
10000x10000 =
Homonyms are fun!
You're driving your car, but they're riding their bikes there.
Nwide = 5
def check_path(board,i1,i2,x,y,n):
if board[x+i1][y+i2]<n: return False
board[x+i1][y+i2] = n
for j1,j2 in [ (1,2),(1,-2),(2,1),(2,-1),(-2,1),(-2,-1),(-1,2),(-1,-2) ]
if n==Nwide*Nwide-1 or check_path(board,j1,j2,x+i1,y+i2,n+1): return True
board[x+i1][y+i2] = Nwide*Nwide+1
return False
for ii,jj in [ (i,j) for i in xrange((Nwide+1)/2) for j in xrange(i,(Nwide+1)/2) ]:
board0 = [[ Nwide*Nwide+1 if i >1 and i< Nwide+2 and j >1 and j<Nwide+2 else 0 for i in xrange(Nwide+4)] for j in xrange(Nwide+4) ]
if check_path(board0,0,0,ii+2,jj+2,0) : print [ j[2:-2] for j in board0[2:-2] ]
This is not speedy however. It also does not take advantage of any symmetry assumptions other than the initial placement of the first move is restricted.
Of course, the unmaintability of Perl's program has nothing to do with the ~#~#*#\@ design of the language itself, it must be the developpers.
Same thing for APL surely?
Face it: the language design have some consequence in maintainability.
Nice, thanks! Wish I had mod points to bump this up a notch or two.
``Tension, apprehension & dissension have begun!'' - Duffy Wyg&, in Alfred Bester's _The Demolished Man_
[...]Every time I try to do something in C++ now, I feel like I'm spending more time on defining types than on solving the problem.
That's actually the point of OOP. You shouldn't be 'forcing' anything to happen the way you would with a functional language. The point of OOP (pure object oriented programming... we're talking ivory tower for the moment) is that you define your objects and then define how they should interact with each other and then put the 'glue' in to interface them to each other on events.
You pay more time up front to define the model and interactions for increased development speed as you move 'up' your interface stack. Done correctly, you should also have less edge cases and a more flexible framework because you've broken down your problem in to many, many smaller generic problems which have an encapsulated object that deals with them and other objects that can interface with first said object.
The vast majority of single use code/quick fixes don't really need to be programmed in an OO language; but it pays off exponentially once you start getting over a few thousand lines of code. Like everything else in software development, there is no silver bullet, every project is unique, there usually isn't a single correct way to do something, but if you find yourself trying to screw in a lightbulb with a hammer, you're doing it the wrong way. Use whatever works for you that doesn't leave you muttering "... there must be a better way to do this!"
If I mod you up, it doesn't necessarily mean I agree with what you've said, sorry.
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. Written by Tim Peters (a.k.a. timbot).
Stop worrying about the risks of nuclear power and start worrying about the risks of not using nuclear power.
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.
Yes, like this smallish application
Get free bitcoins: http://freebitco.in
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.
I actually prefer Ruby for that sort of stuff, but maybe that's just me. ;)
Being bitter is drinking poison and hoping someone else will die
pretty cool, off topic but it made me think of peter norvig's sudoku solver which is about 100 lines of python code and can solve even the hardest puzzles in <.02 seconds. btw, brute force approaches to diabolical sudoku puzzles are not physically possible, follow link to find out why.
python is fantastic for writing concise, functional, and simple solutions to many search problems.
You do know this is how Skynet starts, don't you.
Expect a visit from the Conner's and River Tam any day now.
Don't rush me, Sonny. You rush a miracle man, you get rotten miracles.
xdim,ydim = map(int,__import__("sys").argv[1:])
def recurse((position, visited)):
map(recurse,[(t,visited+[t]) for t in (lambda t: [ (t[0]+2, t[1]+1), (t[0]+2, t[1]-1), (t[0]-2, t[1]+1), (t[0]-2, t[1]-1), (t[0]-1, t[1]+2), (t[0]-1, t[1]-2),(t[0]+1, t[1]+2),(t[0]+1, t[1]-2)])(position) if 0<=t[0]<xdim and 0<=t[1]<ydim and t not in visited])
if len(visited) == xdim*ydim:
print "success: %s"%str(visited).strip("[]")
__import__("sys").exit()
recurse(((0,0),[(0,0)]))
example:
python chess.py 5 5
success: (0, 0), (2, 1), (4, 2), (3, 4), (1, 3), (0, 1), (2, 2), (3, 0), (1, 1), (0, 3), (2, 4), (4, 3), (3, 1), (1, 0), (0, 2), (1, 4), (3, 3), (4, 1), (2, 0), (1, 2), (0, 4), (2, 3), (4, 4), (3, 2), (4, 0)
comment out line 6 to make it 6 lines of python that find all possible tours from (0,0)
def recurse((position, visited),xdim= int(__import__("sys").argv[1]),ydim= int(__import__("sys").argv[2])):
map(recurse,[(t,visited+[t]) for t in (lambda t: [ (t[0]+2, t[1]+1), (t[0]+2, t[1]-1), (t[0]-2, t[1]+1), (t[0]-2, t[1]-1), (t[0]-1, t[1]+2), (t[0]-1, t[1]-2),(t[0]+1, t[1]+2),(t[0]+1, t[1]-2)])(position) if 0<=t[0]<xdim and 0<=t[1]<ydim and t not in visited])
if len(visited) == xdim*ydim: print "success: %s"%str(visited).strip("[]"),__import__("sys").exit()
for ii,jj in [ (i,j) for i in xrange((int(__import__("sys").argv[1])+1)/2) for j in xrange( (int(__import__("sys").argv[2])+1)/2) ]: recurse(((ii,jj),[(ii,jj)]))
This version also adds back the feature deleted in the 7 line version which tries all possible (non-redundant) starting positions.
Sinclair BASIC bitches:
5 REM program to use weighted grid memoir by Geoff Wearmouth.
10 PRINT TAB 8;"Knight's Tour 4": GO TO 9000: REM initialize and run
1000 REM recursive subroutine
1010 IF x>8 OR x<1 OR y>8 OR y<1 THEN RETURN
1020 IF b$(s,1)<>a$(y,x) THEN RETURN
1030 IF SCREEN$ (20-y*2,2+x*3)<>" " THEN RETURN
1040 PRINT AT 20-y*2,1+x*3; PAPER 5+((y+x)=INT ((y+x)/2)*2);(" " AND s<10); s
1050 IF s=64 THEN PRINT AT 21,8;"SOLVED IN ";m; " MOVES" : STOP
1060 LET s=s+1: LET b$(s)="23456789": LET m=m+1
1070 LET x=x+x2: LET y=y+y1: GO SUB 1000: LET y=y-y1: LET x=x-x2
1080 LET x=x+x2: LET y=y-y1: GO SUB 1000: LET y=y+y1: LET x=x-x2
1090 LET x=x+x1: LET y=y+y2: GO SUB 1000: LET y=y-y2: LET x=x-x1
1100 LET x=x+x1: LET y=y-y2: GO SUB 1000: LET y=y+y2: LET x=x-x1
1110 LET x=x-x1: LET y=y+y2: GO SUB 1000: LET y=y-y2: LET x=x+x1
1120 LET x=x-x1: LET y=y-y2: GO SUB 1000: LET y=y+y2: LET x=x+x1
1130 LET x=x-x2: LET y=y+y1: GO SUB 1000: LET y=y-y1: LET x=x+x2
1140 LET x=x-x2: LET y=y-y1: GO SUB 1000: LET y=y+y1: LET x=x+x2
1150 IF b$(s)>="0" THEN LET b$(s)=b$(s,2 TO ): GO TO 1070
1155 LET s=s-1 : REM obsolete backtracking path
1160 PRINT AT 20-y*2,1+x*3; PAPER 8;" "
1170 RETURN
9000 INPUT "x(1-8): ";x, "y(1-8): ";y : REM starting square
9005 IF x>8 OR x<1 OR y>8 OR y<1 THEN GO TO 9000
9010 LET x1=1-(2 AND (x>4)) : LET x2=x1*2
9020 LET y1=1-(2 AND (y>4)) : LET y2=y1*2
9030 BORDER 4: CLS : LET s=1: LET m=1
9040 FOR i=19 TO 162 STEP 16: PLOT 28,i: DRAW INK 1;192,0: NEXT i
9050 FOR j=28 TO 230 STEP 24: PLOT j,19: DRAW INK 1;0,127: NEXT j
9060 DIM a$(8,8): DIM b$(65,8)
9070 FOR i=1 TO 8: READ a$(i): NEXT i
9075 GO SUB 1040
9100 REM perfect weighted grid discovered by James Weatherley.
9110 DATA "22433422"
9120 DATA "35644653"
9130 DATA "56788765"
9140 DATA "36899863"
9150 DATA "36899863"
9160 DATA "56788765"
9170 DATA "35644653"
9180 DATA "22433422"
From http://www.wearmouth.demon.co.uk/gw03/ktour.htm
--
Reverse outsourcing: it's the future
Yeah, a web templating system is indeed a small application. You don't actually think Amazon uses large Perl applications to run their business systems, do you?
That's exactly my point. Perl was developed for specific purposes. It's extremely effective when used for those purposes. When used beyond its scope it is far less effective. This is because of the language design - it's not meant to be maintainable in large systems.
Conversely, it _can_ be maintainable. It's just that most "perl hackers" have no concept of this, and tend to want to use every obscure syntax of the language to make the program more terse. A good programmer (who may or may _not_ be a good perl hacker) can write reasonably maintainable programs in perl.
this now includes the optimization of sorting the order that squares are checked by their number of neighbors. the so-called lonely squares first the original 60 line code had. For sanity this is implemented as an extra line of code defining a function. But python-golfers could cut a stroke by unrolling that function definition into the two places it gets called.
def neigh(p,visited,xdim,ydim): return len( [1 for u in [ (p[0][0]+t[0],p[0][1]+t[1]) for t in [ (-1,-1),(-1,0),(-1,1),(0,-1),(0,1),(1,-1),(1,0),(1,1)] ] if 0<=u[0]<xdim and 0<=u[1]<ydim and u not in visited ] )
def recurse((position, visited),xdim= int(__import__("sys").argv[1]),ydim=
int(__import__("sys").argv[2])):
map(recurse,sorted([(t,visited+[t]) for t in (lambda t: [ (t[0]+2, t[1]+1), (t[0]+2, t[1]-1), (t[0]-2, t[1]+1), (t[0]-2, t[1]-1), (t[0]-1, t[1]+2), (t[0]-1, t[1]-2),(t[0]+1, t[1]+2),(t[0]+1, t[1]-2)])(position) if 0<=t[0]<xdim and 0<=t[1]<ydim and t not in visited],lambda x,y:cmp(neigh(x,visited,xdim,ydim),neigh(y,visited,xdim,ydim) )) )
if len(visited) == xdim*ydim: print "success: %s"%str(visited).strip("[]"),__import__("sys").exit()
for ii,jj in [ (i,j) for i in xrange((int(__import__("sys").argv[1])+1)/2) for j in xrange( (int(__import__("sys").argv[2])+1)/2) ]: recurse(((ii,jj),[(ii,jj)]))
Curious about duck-typing, I asked Google define:duck-typing. No results were found in English, but it did return a hit in the German Wikipedia. I had bookmarked Yahoo as my translation service page back before Google offered one, so I used that link to translate the webpage into English. The Wikipedia article opens with an English quote "When I see a bird that walks like a duck and swims like a duck and Quack like a duck, I call that bird a duck", which is then followed by the German translation of the phrase retranslated back into English. Ok, so far so good, duck-typing obviously enough is seems to follow some notion if an object has the property Quacks like a Duck then it is somehow treated as a Duck type or somesuch. So I'm reading the translation and fighting hard to follow the broken translation example they are using to illustrate how it works and what it means, and I crash head on into the striking phrase "also frogs can quaken". Okaaaaay. Quaken is cute, and frogs quacking is funny. I'm thinking they are deliberately making a Frog type that Quacks-like-a-Duck to make some special point about duck-typing. Completely by chance I then also happened to pull up the Google translation of the page. There I happen find "even frogs can croak" in the same spot. Whoah, waitaminute. So I go look at the original German text and find that it actually does use the word "quaken" there. The German text uses "quak" in the duck section and "quak" in the phrase with frog.
So I've learned a few things.
(1) Apparently Germans use the same word for the noise-a-duck-makes and for the noise-a-frog-makes.
(2) Apparently Yahoo is not smart enough to translate "quak" as "croak" when a frog does it, and that that would have left me completely confused trying to understand the point being made by giving a frog a "Quacks like a Duck" property.
(3) Apparently Google silently has the "smarts" to translate the single word "quak" as either quak for birds or croak for frogs, and that that would have also left me completely confused by how duck-typing is handling a croaking frog and why the frog is gaining the ability to croak.
(4) I never would have figured out any of this if I hadn't randomly happened to pull up BOTH the Google and Yahoo translations.
(5) Now that I have learned that German frogs also quack, I've learned that my brain is bent over the example they are using. What the fuck is the Frog supposed to represent in the duck-typing illustration? Does/doesn't the Frog quack like a Duck? Is/isn't/should/shouldn't the Frog be accepted as a Duck type, and what the fuck is that supposed mean? What the fuck relationship is Frog supposed/not-supposed to have with the Bird and Duck types?
(6) The measure of information I have gained on duck-typing has actually been a negative number due to all of this. My brain now contains scar tissue on what was once pristine blank neurological storage space.
And finally number (6) I learned:
I
QUIT
Adventures in duck-typing.
-
- - You can't take something off the Internet! That's like trying to take pee out of a swimming pool.
fixed logic bug. now 4 lines.
This essentially proves that badly written python is almost as unitelligible as badly written perl. Interestingly badly written python is easier to debug than badly written perl. But then again perl-golf is played for characters not lines! for example, bzip2 is done in 55 perl characters.
def recurse((position, visited),xdim= int(__import__("sys").argv[1]),ydim=
int(__import__("sys").argv[2])):
map(recurse,sorted([(t,visited+[t]) for t in (lambda t: [ (t[0]+2, t[1]+1), (t[0]+2, t[1]-1), (t[0]-2, t[1]+1), (t[0]-2, t[1]-1), (t[0]-1, t[1]+2), (t[0]-1, t[1]-2),(t[0]+1, t[1]+2),(t[0]+1, t[1]-2)])(position) if 0<=t[0]<xdim and 0<=t[1]<ydim and t not in visited],lambda x,y:cmp(len( [1 for t in [ (-1,-1),(-1,0),(-1,1),(0,-1),(0,1),(1,-1),(1,0),(1,1)] if (x[0][0]+t[0],x[0][1]+t[1]) in visited ] ),len( [1 for t in [ (-1,-1),(-1,0),(-1,1),(0,-1),(0,1),(1,-1),(1,0),(1,1)] if (y[0][0]+t[0],y[0][1]+t[1]) in visited ] ))))
if len(visited) == xdim*ydim: print "success: %s"%str(visited).strip("[]"),__import__("sys").exit()
for ii,jj in [ (i,j) for i in xrange((int(__import__("sys").argv[1])+1)/2) for j in xrange( (int(__import__("sys").argv[2])+1)/2) ]: recurse(((ii,jj),[(ii,jj)]))
My Java solution can solve the 100x100 board in 5.5ms (on my 2.5GHz Intel Core 2 Duo laptop). (Actually, it can solve the the 100x100 board 10,000 times in 55 seconds.) I actually provide two solutions: a very small heuristic-less solution, and a longer one based on Warnsdorff's heuristic.
// Simple Heuristic-less solution
// Perform more iterators for more accurate benchmarks
/**
* Knight.java
* author: Kevin Greer
* date: Dec 1, 2008
Gives the following output for SIZE = 8
1 50 15 32 61 28 13 30
16 33 64 55 14 31 60 27
51 2 49 44 57 62 29 12
34 17 56 63 54 47 26 59
3 52 45 48 43 58 11 40
18 35 20 53 46 41 8 25
21 4 37 42 23 6 39 10
36 19 22 5 38 9 24 7
**/
public class Knight {
static final int SIZE = 100;
static final int[][] b = new int[SIZE][SIZE];
static final int[][] M = { {1,2},{-1,2},{1,-2},{-1,-2},{2,1},{-2,1},{2,-1},{-2,-1} };
static void displayBoard() {
for ( int c = 0 ; c < SIZE ; c++ ) {
for ( int r = 0 ; r < SIZE ; r++ ) System.out.print(String.format(" %4d", b[r][c]));
System.out.println("\n");
}
}
static boolean s(int x,int y, int i) {
if ( x < 0 || y < 0 || x >= SIZE || y >= SIZE || b[x][y] != 0 ) return false;
if ( ( b[x][y] = i++ ) == SIZE * SIZE ) { displayBoard(); return true; }
return s(x+2,y+1,i) || s(x+2,y-1,i) || s(x-2,y+1,i) || s(x-2,y-1,i) || s(x+1,y+2,i) || s(x+1,y-2,i) || s(x-1,y+2,i) || s(x-1,y-2,i) || ( b[x][y] = 0 ) == 1;
}
// Solution using Warnsdorff's Heuristic
static boolean isGood(int x, int y) { return x >= 0 && y >= 0 && x < SIZE && y < SIZE && b[x][y] == 0; }
static boolean solve(int x, int y, int i) {
if ( ! isGood(x, y) ) return false;
try {
if ( ( b[x][y] = i++ ) == SIZE * SIZE ) { displayBoard(); return true; }
int[] friends = new int[M.length];
for ( int m = 0 ; m < M.length ; m++ ) if ( isGood(x+M[m][0], y+M[m][1]) ) for ( int m2 = 0 ; m2 < M.length ; m2++ ) if ( isGood(x+M[m][0]+M[m2][0], y+M[m][1]+M[m2][1]) ) friends[m]++;
for ( int n = 0 ; n < M.length ; n++ ) for ( int m = 0 ; m < M.length ; m++ ) if ( friends[m] == n && solve(x+M[m][0], y+M[m][1], i) ) return true;
return false;
} finally { b[x][y] = 0; }
}
public static void main(String[] argv) {
for ( int i = 0 ; i < 1 ; i++ ) {
solve(0,0,1);
}
}
}
Did anyone else think this had something to do with a Monty Python sketch? (We are the Knights Who Write Unintelligible Code?)
Ok wrote a C++ version in less then two hours. It's currently 78 lines, could make it shorter but it would decrease readability. However it is fast... 100x100 starting in upper left in about 10 msec (Core 2 Duo 2.4 single threaded). Even 10000x10000 in less then a second. Which probably means that of that 10 ms for a 100x100 most is actually startup time and print time.
Times are cpu time measured with time command.
It's not A*, A* deals with finding a path to the goal while minimizing the cost. There's no "cost" inherent to the Knight's Tour - all solutions are equal. It makes much more sense to model it as a constraint satisfaction problem (CSP).
Also, "prioritizing the search" doesn't make anything breadth-first, it makes it some kind of priority search. Generally, these graph searches tend to depend only on the underlying structure: stack for depth-first, queue for bread-first, and priority queue for priority searches. Changing the priority function yields different types of priority searches (Dijkstra, greedy best-first, A*, etc).
Harumph.
Did it in less lines, in VAX Pascal no less, in 1985.
Thanks for finding it. I just knew generators would be the best way to solve the problem, but I was too lazy to try it. That code runs fast as all hell too; a 30x30 board is almost instantaneous. Plus it doesn't just find one solution; it finds all of them.
Generators are a wonderful python feature. They're a cousin to Scheme's "continuations"; a similarly powerful feature.
PS: I had mod points too, but they expired this morning. Sorry :-)
I've worked on both good and bad Perl. Perl's sigils are not an issue; neither are Lisp's parentheses or Python's whitespace. These things cease to annoy once you spend some time with the language.
The reason there's a lot of bad Perl is the reason there's a lot of bad PHP: both languages enable beginning programmers to get things done.
$ time python -c "import sys; sys.stdout.write((lambda size, sizesq, allp, openclose: ((lambda mkbrd, brd, mv, av, d, finished: ((lambda h: h(h, mkbrd(), 0, 0, 0)) (lambda h, b, r, c, v: [ lambda: ([ lambda:'', lambda: ((lambda nb, nv: d([lambda:h(h, nb, r-2, c-1, nv), lambda:h(h, nb, r-1, c-2, nv), lambda:h(h, nb, r-2, c+1, nv), lambda:h(h, nb, r-1, c+2, nv), lambda:h(h, nb, r+1, c-2, nv), lambda:h(h, nb, r+2, c-1, nv), lambda:h(h, nb, r+1, c+2, nv), lambda:h(h, nb, r+2, c+1, nv)]) ) (mv(b,r,c,v), v+1))] [av(b,r,c)]()), lambda: brd(b)][finished(v,r,c)]()) )) (lambda: [-1] * sizesq, lambda b: '\n'.join((''.join('%4d' % v for v in b[i:i+size])) for i in range(0,sizesq,size)) + '\n\n', lambda b, r, c, v: b[:r*size+c] + [v] + b[r*size+c+1:], lambda b, r, c: int(r >=0 and r = 0 and c 0)]())), lambda fl: ''.join(f() for f in fl)][allp], [lambda v,r,c: int(v==sizesq), lambda v,r,c: int(v==sizesq and r==0 and c==0)][openclose] ))) (int(sys.argv[1]), int(sys.argv[1])*int(sys.argv[1]), int(sys.argv[2]), int(sys.argv[3])))" 6 0 1
0 7 4 13 2 29
5 12 1 30 23 14
8 35 6 3 28 31
11 18 9 24 15 22
34 25 20 17 32 27
19 10 33 26 21 16
real 0m43.784s
user 0m36.254s
sys 0m0.052s
$
arguments: the 6 is the size of the board, 0 means to print the first found rather than all, and the 1 means to look for a closed path rather than an open path.
beware syntactic cavities