- Feature Articles
- CodeSOD
- Error'd
-
Forums
-
Other Articles
- Random Article
- 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
In pseudocode it would be something like:
-- snipped Knight's tour - In Pseudocode from Wikipedia --
So this Python code should do the trick:
-- snipped Knight's tour - In Python also from Wikipedia --
Unfortunately, this praxis suffers from the same problem as all the rest - these are extremely well known problems that have been solved a thousand times before. Please, make up something unique or modify an existing problem enough to make us break into a sweat.
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
Anonymous: Congrats on successfully quoting the Wikipedia article: http://en.wikipedia.org/wiki/Knight's_tour
Admin
Anybody know what it would take to brute-force 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 brute-force 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 crazy-hard 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:
#include <assert.h> #include <stdio.h> #include <malloc.h> void print_board(unsigned w, unsigned h, int *board) { int r,c; printf("--\n"); for (r=0;r<h;r++) { for (c=0;c<w;c++) printf("%2d ",board[r*w+c]); printf("\n"); } } void try_move(int n, unsigned x, unsigned y, unsigned w, unsigned h, int *board) { if (x>=w || y>=h || board[x+w*y]!=-1) return; board[x+w*y]=n++; if (n==w*h) print_board(w,h,board); else { try_move(n,x+2,y+1,w,h,board); try_move(n,x-2,y+1,w,h,board); try_move(n,x+2,y-1,w,h,board); try_move(n,x-2,y-1,w,h,board); try_move(n,x+1,y+2,w,h,board); try_move(n,x-1,y+2,w,h,board); try_move(n,x+1,y-2,w,h,board); try_move(n,x-1,y-2,w,h,board); } board[x+w*y]=-1; } void knight(unsigned x, unsigned y, unsigned w, unsigned h) { int i; assert(x<w && y<h); int *board=malloc(w*h*sizeof(int)); for (i=0;i<w*h;i++) board[i]=-1; try_move(0,x,y,w,h,board); } int main(int argc,char **argv) { assert(argc==5); knight(atoi(argv[1]),atoi(argv[2]),atoi(argv[3]),atoi(argv[4])); } </pre>Admin
I'm not having a rant, I like the principle of Programming Praxis, but we need some reader submissions so Alex doesn't have all the hard work of figuring out the challenges (or rather, so Wikipedia doesn't have all the hard work of figuring out the challenges).
And yes, as it happens, I'm working on it...
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 out-of-bounds 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 ^ ((n-4)^2))) sequences.
You can go progressively less brute force-ish 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 self-discipline...
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 pre-mark 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:
public static void main(String args[]) { knightsTour(6, 0, 0); } static int[][] possibleMovements = {{2, 1}, {1, 2}, {2, -1}, {1, -2}, {-2, 1}, {-1, 2}, {-2, -1}, {-1, -2}}; public static void knightsTour(int size, int startX, int startY) { boolean[][] board = new boolean[size][size]; int[][] movements = new int[size * size][2]; movements[0][0] = startX; movements[0][1] = startY; board[0][0]=true; int indice = 0; movements = knightsTour(board, movements, indice); if (movements != null) { for (int i = movements.length-1; i >=0; i--) { System.out.println("(" + movements[i][0] + "," + movements[i][1] + ")"); } } } public static int[][] knightsTour(boolean[][] board, int[][] movements, int index) { int x, y; if (index == movements.length -1) { return movements; } for (int i = 0; i < possibleMovements.length; i++) { x = movements[index][0] + possibleMovements[i][0]; y = movements[index][1] + possibleMovements[i][1]; if (x >= 0 && x < board.length && y >= 0 && y < board.length && board[x][y] == false) { boolean[][] board2 = clone(board); board2[x][y] = true; movements[index+1][0] = x; movements[index+1][1] = y; int[][] retorno = knightsTour(board2, movements, index + 1); if (retorno != null) { return retorno; } } } return null; } public static boolean[][] clone(boolean[][] board) { boolean[][] retorno = new boolean[board.length][board[0].length]; for (int i = 0; i < board.length; i++) { for (int j = 0; j < board[0].length; j++) { retorno[i][j] = board[i][j]; } } return retorno; }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 code-golf 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 non-square 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 thought that's what a programming praxis was--a fancy word for "practice", taking a problem that's already been solved, and implementing the solution as a programming exercise. Not to be confused with a programming puzzle, where the focus is on coming up with a way to solve the problem.
At least that's what I've gathered from context.
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
function knightsTour(size,s_pos) { var board = []; for ( var i = 0; i<size; i++ ) { board[i] = []; for ( var j = 0; j<size; j++ ) { if (s_pos.x == i && s_pos.y == j) { board[i][j] = 1; } else { board[i][j] = 0; } } } var nextPossibleMoves = function(board,currentPos) { countNext = countNext || true; function isValidMove(board,move) { if (move.x < 0 || move.x >= board.length || move.y < 0 || move.y >= board.length) { return false; } if ( board[move.x][move.y] ) { return false; } return true; } var moves = [ {x:currentPos.x - 1,y:currentPos.y-2}, {x:currentPos.x - 2,y:currentPos.y-1}, {x:currentPos.x - 1,y:currentPos.y+2}, {x:currentPos.x - 2,y:currentPos.y+1}, {x:currentPos.x + 1,y:currentPos.y-2}, {x:currentPos.x + 1,y:currentPos.y+2}, {x:currentPos.x + 2,y:currentPos.y-1}, {x:currentPos.x + 2,y:currentPos.y+1} ]; var ret = []; for ( var i = 0; i< moves.length; i++ ) { if (isValidMove(board,moves[i])) { ret[ret.length] = moves[i]; } } return ret; } var moves = []; var max_moves = size*size; var nextMove = function(board,pos,cur_move) { if ( cur_move == max_moves ) { return true; } var posMoves = nextPossibleMoves(board,pos); if ( posMoves.length == 0 ) { return false; } //var tboard = arrayCopy(board); for ( var i = 0; i<posMoves.length; i++ ) { board[posMoves[i].x][posMoves[i].y] = 1; if ( nextMove(board,posMoves[i],cur_move+1) ) { moves.push(posMoves[i]); return true; } board[posMoves[i].x][posMoves[i].y] = 0; } return false; } nextMove(board,s_pos,1); return moves.reverse(); } </pre>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:
import java.util.Random; import java.util.Stack; class Move { private int x; private int y; private int count; public Move(int x, int y) { this.x = x; this.y = y; } public int getX() { return this.x; } public int getY() { return this.y; } public void setCount(int x) { this.count = x; } public int getCount() { return this.count; } } public class KnightsTour { private final Random r = new Random(); private int board[][] = null; private int curX; private int curY; private int currentMove = 1; private int finishedMoves; private int tries = 0; private Stack<Move> moves = new Stack<Move>(); private int xStart; private int yStart; private int[][] mods = { {2,1} , {1,2} , {-1,2} , {-2,1} , {-2,-1} , {-1,-2} , {1,-2} , {2,-1} }; private boolean isValidMove(Move m) { try { int val = board[m.getX()][m.getY()]; if(val == 0) return true; } catch (ArrayIndexOutOfBoundsException e) { return false; } return false; } private void setUpBoard(int x, int y) { board = new int[x][y]; for(int i = 0; i < board.length;i++) { for(int j = 0 ; j < board[0].length ; j++) { board[i][j] = 0; } } } private void setValidStart(int x, int y) { xStart = r.nextInt(board.length); yStart = r.nextInt(board[0].length); if(xStart%2 == 0 && yStart%2==0) setValidStart(x,y); if((yStart==4 || yStart==6 || yStart==8) && xStart==3) setValidStart(x,y); } private void start(int x, int y) { currentMove = 1; setUpBoard(x,y); finishedMoves = x*y; setValidStart(x,y); curX = xStart; curY = yStart; board[xStart][yStart] = currentMove++; runSimulation(); if(this.currentMove==this.finishedMoves) printBoard("End"); else if(this.tries >= 100) printBoard("Failure at 100 tries"); else start(6,6); } private void runSimulation() { while(currentMove < finishedMoves) { Move m = getMove(); if(m == null) break; board[m.getX()][m.getY()] = currentMove++; curX = m.getX(); curY = m.getY(); } board[this.curX][this.curY] = currentMove; this.tries++; } private Move getMove() { Move m = null; Move ret = null; this.moves = getMoves(this.curX, this.curY); Stack<Move> temp = null; while(!moves.isEmpty()) { m = this.moves.pop(); temp = getMoves(m.getX(),m.getY()); if(ret == null) { ret = m; ret.setCount(temp.size()); } else { if(ret.getCount() > temp.size()) { ret = m; ret.setCount(temp.size()); } } } return ret; } private Stack<Move> getMoves(int x, int y) { Stack<Move> temp = new Stack<Move>(); for(int i = 0; i < mods.length;i++) { for(int j = 0 ; j < mods[0].length ; j++) { Move m = new Move(mods[i][j++] + x,mods[i][j] + y); if(isValidMove(m)) { temp.push(m); } } } return temp; } private void printBoard(String str) { System.out.println("\n**************** Board "+str+" ****************\n"); for(int i = 0; i < board.length;i++) { for(int j = 0 ; j < board[0].length ; j++) { if(board[i][j] < 10) System.out.print(board[i][j] + " "); else System.out.print(board[i][j] + " "); } System.out.println(); } System.out.println("\n***************** Moves = " + this.currentMove + ", in " + this.tries + " tries *****************\n"); } public static void main(String[] args) { KnightsTour kt = new KnightsTour(); kt.start(6,6); } }Admin
I have discovered a truly marvelous 1-line 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 xserver-xgl module for Ubuntu Intrepid and later? I am stuck using Hardy because xserver-xgl 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 p-p-p-please?
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
Is it based on this?
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 well-known problems in simple math are a suitable excuse for an irritating spew-fest of hastily-constructed 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:
No-Touch 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 (2009-08-12 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.
#!/usr/bin/perl # Knight's tour solution # using depth-first search # also recursion sub knightsTour { my $s = shift; my $n = shift; my $x = shift; my $y = shift; my @b = @_; return 0 if ($x < 0 || $x >= $s || $y < 0 || $y >= $s); if ($b[$x + $y*$s]) {return 0} else {$b[$x + $y*$s] = 1} if ($n == $s*$s) { print "$x,$y\n"; return 1; } if (&knightsTour($s, $n+1, $x+2, $y+1, @b)) { print "$x,$y\n"; return 1; } if (&knightsTour($s, $n+1, $x-2, $y+1, @b)) { print "$x,$y\n"; return 1; } if (&knightsTour($s, $n+1, $x+2, $y-1, @b)) { print "$x,$y\n"; return 1; } if (&knightsTour($s, $n+1, $x-2, $y-1, @b)) { print "$x,$y\n"; return 1; } if (&knightsTour($s, $n+1, $x+1, $y+2, @b)) { print "$x,$y\n"; return 1; } if (&knightsTour($s, $n+1, $x-1, $y+2, @b)) { print "$x,$y\n"; return 1; } if (&knightsTour($s, $n+1, $x+1, $y-2, @b)) { print "$x,$y\n"; return 1; } if (&knightsTour($s, $n+1, $x-1, $y-2, @b)) { print "$x,$y\n"; return 1; } return 0; } my ($s, $x, $y) = @ARGV; my @b = (); for ($i = 0; $i < $s*$s; $i++) {push @b, 0} &knightsTour($s,1,$x,$y,@b);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.
Admin
My perl solution
use strict; use warnings; my $size = 6; my $startx = 3; my $starty = 3; my @b; sub initboard { for(my $i=0; $i<$size+4; $i++) { for(my $j=0; $j<$size+4; $j++) { if ($i>1 && $i<$size+2 && $j>1 && $j<$size+2) { $b[$i][$j] = 0; } else { $b[$i][$j] = -1; } } } } sub printboard { for(my $i=0; $i<$size+4; $i++) { for(my $j=0; $j<$size+4; $j++) { if ($i>1 && $i<$size+2 && $j>1 && $j<$size+2) { printf("%02d ",$b[$i][$j]); } } print "\n\n"; } } sub printmoves { my @m; for(my $i=0; $i<$size+4; $i++) { for(my $j=0; $j<$size+4; $j++) { if ($i>1 && $i<$size+2 && $j>1 && $j<$size+2) { $m[$b[$i][$j]-1] = [$i-2,$j-2]; } } } for my $m (@m) { print "$$m[0],$$m[1]\n"; } } sub tour { my ($x,$y,$d) = @_; if ($b[$x][$y] < 0) { return; } if ($d == $size*$size) { if($x==$startx && $y==$starty) { printboard(); printmoves(); exit; } return; } if ($b[$x][$y] > 0) { return; } $b[$x][$y] = $d+1; tour($x+1,$y+2,$d+1); tour($x+1,$y-2,$d+1); tour($x-1,$y+2,$d+1); tour($x-1,$y-2,$d+1); tour($x+2,$y+1,$d+1); tour($x+2,$y-1,$d+1); tour($x-2,$y+1,$d+1); tour($x-2,$y-1,$d+1); $b[$x][$y] = 0; } initboard(); tour($startx,$starty,0);I used Old Timer's suggestion to add a border of already visited squares.