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.
ha!
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).
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
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.
Yawn.
A good language needs to occasionally shed unneeded features, or it will ossify into an unusable mess. (This is why Perl is dying.)
"Not an actor, but he plays one on TV."
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."
...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?
/var/run/twitter.sock is a twitter socket puppet.
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
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.
Haskell solution, faster, shorter, uses less space.
http://hpaste.org/12546
Hooray for compilers.
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.
object[] finalBoard = System.Math.KnightsTour(64);
But does it work with 3 dimensional chess?
Here's a C++ soution, coded in 25 minutes, using a much faster algorithm. It solves all sizes NxN 5<=N<=100 under a second, all sizes up to 1000x1000 in 12 seconds, a single 5000x5000 in 3 secs, and a 10,000x10,000 board in 12 seconds (all on my decent PC). I'd like to see the python version do that. Not only does this solve the original posters problem of doing the problem in less than 3 times the number of lines he used, it does it in less code than the original poster entirely and executes in drastically less time with no stack overflows.
:)
// makes move // next move // Solve
It's on
// Chris Lomont, 2008, Knight Tour using Roth extension of Warnsdorff Algorithm
// Solves NxN for 5<=N<=1000, N=5000, N=10000 (and others - check solutions)
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
void Solve(int n, bool show)
{
vector<int> board(n*n);
for (int i = 0; i < n*n; ++i) board[i] = 8;
for (int i = 2; i < n-2; ++i) {
board[i] = board[n*n-i-1] = board[n*i] = board[n*i+n-1] = 4;
board[i+n] = board[n*n-i-1-n] = board[n*i+1] = board[n*i+n-2] = 6; }
board[0] = board[n-1] = board[n*n-1] = board[n*n-n] = 2;
board[1] = board[n-2] = board[n] = board[2*n-1] = 3;
board[n*n-2] = board[n*n-n+1] = board[n*n-n-1] = board[n*n-2*n] = 3;
board[n+1] = board[2*n-2] = board[n*n-n-2] = board[n*n-2*n+1] = 4;
int moves1[] = {2,-1,1,-2,-1,-2,-2,-1,-2,1,-1,2,1,2,2,1, 2,-1,1,-2};
int * moves = moves1;
int bad[] = {11,261,352,379,526,744,753,983,10000};
if (find(bad,bad+9,n) != bad+9)
moves+=2;
int xpos = 0, ypos = 0, depth = 0;
while (depth++ < n*n) {
board[xpos*n+ypos] = -depth;
int best = n*n, fx = xpos, fy = ypos;
double dist = -1;
for (int m = 0; m < 16; m += 2) {
int nx = xpos + moves[m], ny = ypos + moves[m+1];
if ((0 <= nx) && (nx < n) && (0 <= ny) && (ny < n) && (board[nx*n+ny]>=0)) {
--board[nx*n+ny];
double dx = nx-(n-1)/2.0, dy = ny - (n-1)/2.0;
if (((board[nx*n+ny] <= best) && (dx*dx + dy*dy >= dist)) || (board[nx*n+ny] < best)) {
best = board[nx*n+ny];
dist = dx*dx+dy*dy;
fx = nx, fy = ny; } } }
xpos = fx; ypos = fy; }
if (show)
for (int j = 0; j < n; ++j) {
for (int i = 0; i < n; ++i) {
cout.width(3);
cout << -board[i+j*n] << ' '; }
cout << endl; }
}
int main(void)
{
Solve(8,true);
for (int n = 5; n <= 1000; ++n)
Solve(n,false);
}
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.
[...]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.
Problems of this kind (search problems) are generally all about the big-Oh complexity of the solution. The "naive" approach described in the OP's link is a depth-first or brute-force search; prioritizing the search (in any way) makes it a breadth-first search. Usually the problem is all about finding the correct priority function.
So for the most part, one's choice of language is arbitrary. Most of the work is done with pen and paper. Choice of language? Go with what you know - but also make an effort to know a little more every day, please! These "C++ vs Python" or "Java vs C#" arguments are at best amusing and at worst painful to watch.
program start
new knigth;
knigth.movearound();
program end
only 4 lines you are a pgrogramer and need 60....
Actually your code could be anywhere from 53 lines if you remove the blank lines, or 56 if you just write out show and solve in the places that they are used. But then you would sacrifice good coding practices. So the moral of this story:
Lines of code are not what makes good code.
And bandwidth limits will pwn you for free.
(Silly OP use a real hosting server.I hear blogger is pretty good.)
Also don't brag with conditions. It's quite lame.
Not to be paternalistic, but allow me to suggest writing this sorting code in C (using qsort?), or in C++ using STL's sort algorithm.
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.
2 lines of javascript to print out the fibonacci series:
for(b=(a=0)+1;;b+=(a+=b))
document.write(a+'
'+b+'
');
and only 1 line taking out the line breaks.
funny how most languages you can make programs in one line - this whole "no semi-colon" smuggery of python has removed that feature
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.
Am I the only AC that read the slashy blurb and could only think of Flying Circus references? I clicked "Read More" expecting a litany of hilarious references to comedy of old, but instead I get nothing. NOTHING! Bah!
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
Number of lines of code is absolutely a new type of complexity which is left out in "The art of programming".
HAI
CAN I HAZ A PONIE?
CAN I HAZ A CHEKERBORED?
IM IN YR LOOP
WIT TEH CHEKERBORED
OMG PONIE! POOP!
OMG PONIE! JUMP!
IF PONIE FALL OR STEP IN POOP GO BACK PONIE
IF POOP EVERYWARE KTHXBYE
JUMP DIFFERENT PONIE
IM OUTTA YR LOOP
SHOW CHEKERBORED
KTHXBYE
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)]))
For those interested in playing the game, there is an iPhone version called Knight's Run available. (Currently $.99 US).
Here's a link to it in the app store:
http://itunes.apple.com/WebObjects/MZStore.woa/wa/viewSoftware?id=287816855&mt=8
I bought it, it's a nice workout for the neurons.
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.
I wrote this game for the iPhone...it's called Knight's Run.
iTunes Link: http://itunes.apple.com/WebObjects/MZStore.woa/wa/viewSoftware?id=287816855&mt=8
--Andrew Borland
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 :-)
$ 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