 Feature Articles
 CodeSOD
 Error'd
 Forums

Other Articles
 Random Article
 Other Series
 Alex's Soapbox
 Announcements
 Best of…
 Best of Email
 Best of the Sidebar
 Bring Your Own Code
 Coded Smorgasbord
 Mandatory Fun Day
 Off Topic
 Representative Line
 News Roundup
 Editor's Soapbox
 Software on the Rocks
 Souvenir Potpourri
 Sponsor Post
 Tales from the Interview
 The Daily WTF: Live
 Virtudyne
Admin
Shouldn't the knight in your illustration also obey rule 3, bullet 2)?
Note from Alex: It should... but I somehow missed that and thought I could get away with just borrowing the one from Wikipedia. Lesson learned!
Admin
The traditional Knight's Tour problem does not require that the knight end on the same square from which it began, merely that it visit each of the squares once.
On some board sizes it is possible to do a Knight's Tour that ends where it started (a "closed tour") but on others it is not.
Admin
If the example ignores rules it does not like, I shall do the same (Using C64 Basic):
Admin
Which really isn't a starting square so much as an arbitrary spot on the board. You cannot reach the real starting square from there, so you can't say that it started in the upper left and that move wasn't animated.
I like the idea of these programming challenges, but I wish there were some more space between them. I think people kind of lose interest when they are this close, so you don't get the same creativity as the initial offering.
Admin
As I recall, any board where both dimensions are odd can't be used to complete a closed tour.
Admin
I agree with the last Anonymous. Maybe a real world example would be a better challenge These problems are more of a math game. I'm not complaining, merely suggesting
Admin
Make up something unique or modify an existing problem enough to make us break into a sweat.
Admin
Anybody know what it would take to bruteforce this?
Admin
Oh, this one's too long for me to do during my lunchbreak, too data structure reliant to try to implement in a strange language, and too well known to get my loins stirring.
I guess what I should do is think up some good problems and submit them.
Admin
To bruteforce it it would take programming every possible knight's tour for every possible board size into the program, and set it up to say 'invalid input' when one out of the range is selected.
Admin
Indeed!
Quick proof: On an odd x odd board there are an odd number of squares.
To complete a closed tour we must move the knight once for every square there is on the board (as he lands on each square exactly once, including the starting square which he lands on at the end of the tour).
Finally, the colour of the square the knight lands on changes with every move (just look at the allowed moves). So, with an odd number of total moves the knight finishes the tour on the opposite colour to which he started. But to be a closed tour he must start and end on the same square, which is clearly the same colour as itself. Contradiction.
Admin
Suggestions are always welcome. But keep in mind... I don't think the goal should be to spend a week solving a crazyhard puzzle; perhaps a lunch break or a long coffee break... maybe in a language you're not all too familiar with.
In the case of the Knight's Tour... so long as you don't copy/paste the wikipedia solution, it's actually a bit of a challenge.
Or, you could just whine. That's easier than coding, anyway!
Admin
The textbook brute force method:
Admin
Yeah I enjoy these, and they are meant as a mental exercise, it may be something you know, but you can approach it in a different way, or a language you want to learn. Just letting you know there are people that aren't trolls that do appreciate what you are doing.
Admin
Admin
There are several sorts of brute force:
You generate every single possible sequence of board tiles, and only filter out valid sequences of knight's jumps afterward: In an n*n board, there'll be (n^2)! such sequences.
You generate every single possible sequence of knight's jumps. Since you know there are 8 possible moves, and n*n jumps, you need 8^(n^2) tests (you'll just discard the outofbounds moves later).
If you test for boundedness a priori, then: ~ The first row in each edge cuts out 4 moves. This accounts for (n  4) * 4 tiles. ~ The second row cuts out 2 moves. Another (n  4) * 4 tiles. ~ The corner positions cut out 6 moves. 4 tiles ~ The (1,2) and symmetrical points cut out 5 points. 8 tiles. ~ The (2, 2) and symmetrical points cut out 4 moves. There are 4 such tiles. ~the rest of the board ((n  4)^2 tiles) has the full 8 movements available.
This leads to a naive upper bound of (2 ^4 ) * (4 ^ 4) * (4 ^((n 4) * 4)) * (6 ^ ((n 4) * 4)) * (8 ^ ((n4)^2))) sequences.
You can go progressively less brute forceish from here on.
Admin
Admin
oops, my response is here
I dont't think you can keep spitting out this reinventing the wheel argument. The fact is these a programming challenges, not meant to fit into robust or scalable apis. They are meant to be a bit of fun. And I think they would be fun to anyone who didn't just straight away head to google for the answer. Try figure it out, and remember the solutions to these problems aren't going to make it into any enterprise applications, so you shouldn't worry too much about your programming design principles.
Admin
Besides, they have the answers in the back. Everybody's going to go straight there without trying first, right, man?
But wait: there's this new thing the psychologists have discovered, called selfdiscipline...
Admin
Correct. There are other situations where closed tours are impossible as well, but I can't recall all the rules at the moment. Obviously there are some boards where it is trivially impossible due to the knight not being able to physically reach all the squares.
Admin
My little optimization is to make the board larger all around, and premark extra squares as already visited. Runs faster as you get rid of some if statements.
Admin
Actually The Turk was fake.
ther was a meatworld chess player under the table
Admin
Java brute force:
Admin
Admin
In my old Deitel & Deitel C++ book they recommend developing an accessibility heuristic, so that for each move you move the knight to the least accessible square.
Accessibility for any given square is the number of squares that can reach that square. It should be recalculated to keep the board up to date for each move.
Admin
If this is a solved problem, pick it up in a new language and codegolf that sucker! This one is too long for me to do on a coffee break, but I'm gonna break out NetBeans and Groovy when I get home to see if I can implement the Warnsdorff algorithm.
If you want more of a challenge, try using nonsquare boards. If there a way to mathematically determine if a given rectangular board is winnable?
Admin
I have to admit, I liked thinking about the previous ones and seeing some of the very inventive solutions, but this one is just too famous to spark enough interest.
How about a variation? It's proven that you can't do a closed tour on an odd x odd board. So, try he following on an odd x odd board: start from any square except the center and visit every square except the center!
(Caveat: it's possible on the minimal 3x3 board but I don't know about bigger ones)
Admin
I must agree with the others. When you have to solve a well known problem, it's fun to reinvent the wheel if it takes 3 minutes, but in case the problem is bigger and takes longer to code then programmer's instinct screams "check if there is a solution on the interweb first".
P.S. Unless the idea is to look up the solution and then convert it to XML and SQL.
Admin
Ah whatever  while you guys were whining I wrote this JS solution. Warning  it's a bit slow, for board sizes > 5x5
Admin
To be more specific, on (odd x odd) board sizes it is never possible to do a closed Knight's tour (proof is easy) and (conjecture) on all other board sizes (odd x even, even x even, even x odd) it is possible to do a closed Knight's tour provided that both dimensions are large enough.
Admin
Can we have a challenge that involves creating doubly linked lists? Like, today? Because my homework is due Friday.
Admin
My ghetto version using Warnsdorff's algorithm:
Admin
I have discovered a truly marvelous 1line APL solution of this, which this comment is too narrow to contain.
Admin
When that one is done, can we please get a challenge to do one of the following:
Replace the deprecated xserverxgl module for Ubuntu Intrepid and later? I am stuck using Hardy because xserverxgl is required for me to get compiz/beryl running on 3 monitors w/ xinerama and 3d hardware accels. OR,
Modify the (propritary) nvidia gpu linux driver to support more than two monitors? (using twinview with 2 + a third monitor leads to all sorts of crappy behavior)
bats eyes, smiles big, says pppplease?
Admin
Admin
In Python, the Black Knight's tour is like this:
What are you going to do bleed on me? Its just a flesh wound!
Admin
Zing!
Admin
The solution in ghetto VB (6), as performed by the Turk:
Admin
Made me smile. :) Bit on the mathgeeky side tbh.
Admin
But I got a bone to pick with you, matey, so I has. Yer not bustin' yer boots hard enough. Yer needs a new fermat, so yer does ... arrrrr!
And to all those of you who think that wellknown problems in simple math are a suitable excuse for an irritating spewfest of hastilyconstructed implementations (forgiving those who post in Haskell, OCamL, Befunge or Whitespace):
Talk to the parrot, 'cause the hook ain't listening.
Admin
You want problems that haven't already been solved? Okay, let me offer these suggestions:
Write a program that can pass the Turing Test. (I'm sure you can find a description of it with Google if you don't know what it is.) The program must be written in Javascript and may not use the Date object.
Read as input a bill introduced into Congress. Using a linked list and Fermat's Last Theorem, determine exactly how much the final cost will be over the projected cost, how much harm it will do to the American and the global economy, and how many people in third world countries will die of hunger or starvation as a direct result. Note: It is not necessary to consider arms production in France.
Admin
I have an original programming praxis if you want:
NoTouch Mosaics
Form a rectangular mosaic from square, colored pieces. Any number of pieces and any number of colors are allowed.
Form another rectangular mosaic from the same set of pieces. But this time, don't allow any pieces that touched before to touch again. Pieces of a common color are considered interchangeable, so if a red piece touched a blue piece in the first mosaic then no red pieces can touch any blue pieces in the second mosaic. Furthermore, if two blue pieces touched in the first mosaic then no blue pieces can touch in the second mosaic.
Addendum (20090812 20:37): One more rule I forgot to mention: Consider any piece on an outer edge to be in contact with all other pieces on an outer edge in the same mosaic. So if both a red piece and a blue piece are on the outer edge in the first mosaic, neither a red piece nor a blue piece can be on the outer edge in the second mosaic, nor can they touch each other in the second mosaic.
Admin
I want to see these problems solved with Piet. Any takers?
Admin
This is The Daily WTF, and we clearly haven't had a bad enough solution here yet. I'd like to dedicate this one to all the O(8^n) algorithms out there. You're special in your own way.
It doesn't generate closed tours, although this would be a pretty easy modification. Because of how it prints the solution, the specified starting point is actually the ending point. This is really disappointing, I know  almost as disappointing as when you get your PB&J sandwich and the peanut butter is on top of the jelly. I mean, seriously.