Comment On Automating the Knight’s Tour

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!

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.

If the example ignores rules it does not like, I shall do the same (Using C64 Basic):

10 ? "I WIN"

20 GOTO 10

gjutras:

By Starting square, I don't think he's referring to a closed tour, but the upper left square.

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.

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.

Someone You Know:

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.

As I recall, any board where both dimensions are odd can't be used to complete a closed tour.

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

Anonymous:

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.

Okay, here's your new, unique Praxis:

Make up something unique or modify an existing problem enough to make us break into a sweat.

Anonymous: Congrats on successfully quoting the Wikipedia article: http://en.wikipedia.org/wiki/Knight's_tour

Anybody know what it would take to brute-force this?

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.

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.

hikari:

Someone You Know:

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.

As I recall, any board where both dimensions are odd can't be used to complete a closed tour.

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.

Anonymous:

In pseudocode it would be something like:
-- snip wikipedia copy/paste --

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.

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!

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]));

}

Perfect coder:

Anonymous: Congrats on successfully quoting the Wikipedia article: http://en.wikipedia.org/wiki/Knight's_tour

Aww, you rumbled me... so you must have also noticed that Wikipedia is exactly where this problem came from, right down to the animated GIF that's included with the article. This is exactly the point I was trying to make - by copying a well-known problem off Wikipedia there is absolutely no challenge posed here; why even bother to work out an answer when thousands of people have beat you to it? A cornerstone of good software development practice is that you don't reinvent the wheel and you don't waste time rewriting code that has been written before.

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...

Alex Papadimoulis:

Anonymous:

In pseudocode it would be something like:
-- snip wikipedia copy/paste --

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.

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!

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.

Alex Papadimoulis:

Anonymous:

In pseudocode it would be something like:
-- snip wikipedia copy/paste --

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.

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.

As per my above post, re-inventing the wheel is not a challenge, it is a waste of time. But also as per my above post, I understand that you can't spend all day working out coding challenges and I'm working on a couple of submissions myself. And for the record, you can't blame me for copying off Wikipedia - after all, where the hell did you get that animated GIF from?!

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.

Anonymous:

Alex Papadimoulis:

Anonymous:

In pseudocode it would be something like:
-- snip wikipedia copy/paste --

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.

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.

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.

As per my above post, re-inventing the wheel is not a challenge, it is a waste of time. But also as per my above post, I understand that you can't spend all day working out coding challenges and I'm working on a couple of submissions myself. And for the record, you can't blame me for copying off Wikipedia - after all, where the hell did you get that animated GIF from?!

Kev B:

Anonymous:

Alex Papadimoulis:

Anonymous:

In pseudocode it would be something like:
-- snip wikipedia copy/paste --

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.

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.

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.

As per my above post, re-inventing the wheel is not a challenge, it is a waste of time. But also as per my above post, I understand that you can't spend all day working out coding challenges and I'm working on a couple of submissions myself. And for the record, you can't blame me for copying off Wikipedia - after all, where the hell did you get that animated GIF from?!

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.

Anonymous:

This is exactly the point I was trying to make - by copying a well-known problem off Wikipedia there is absolutely no challenge posed here; why even bother to work out an answer when thousands of people have beat you to it?

So, once somebody's solved a problem, nobody else should bother? Aw, man, the Puzzles and Logic Problems books are gonna hate this.

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...

hikari:

Someone You Know:

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.

As I recall, any board where both dimensions are odd can't be used to complete a closed tour.

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.

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.

Actually The Turk was fake.

ther was a meatworld chess player under the table

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;

    }

Nuno Milheiro:

Actually The Turk was fake.

ther was a meatworld chess player under the table

You were in a big hurry to show that you knew that, huh. A real big hurry...

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.

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?

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)

Anonymous:

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.

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.

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.

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();

	}

Someone You Know:

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.

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.

Can we have a challenge that involves creating doubly linked lists? Like, today? Because my homework is due Friday.

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

	}



}

I have discovered a truly marvelous 1-line APL solution of this, which this comment is too narrow to contain.

Plz Send Me The Code:

Can we have a challenge that involves creating doubly linked lists? Like, today? Because my homework is due Friday.

When that one is done, can we please get a challenge to do one of the following:

1) 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,

2) 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?*

Nuno Milheiro:

Actually The Turk was fake.

ther was a meatworld chess player under the table

Congratz on not reading the article.

In Python, the Black Knight's tour is like this:

What are you going to do bleed on me?
Its just a flesh wound!

nitehawk:

In Python, the Black Knight's tour is like this:

What are you going to do bleed on me?
Its just a flesh wound!

Zing!

The solution in ghetto VB (6), as performed by the Turk:

Sub Main()

  MsgBox "Pitiful human!  I order you to perform a Knight's Tour, or I shall cease providing you with food."

End Sub

Ken B:

I have discovered a truly marvelous 1-line APL solution of this, which this comment is too narrow to contain.

Is it based on this?

Ken B:

I have discovered a truly marvelous 1-line APL solution of this, which this comment is too narrow to contain.

Made me smile. :)
Bit on the mathgeeky side tbh.

Ken B:

I have discovered a truly marvelous 1-line APL solution of this, which this comment is too narrow to contain.

WINNER!

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.

You want problems that haven't already been solved? Okay, let me offer these suggestions:

1. 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.

2. 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.

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.

1) Provide an example of a pair of mosaics satisfying these rules.
2) What is the smallest pair of mosaics (of any shape) that satisfies the rules?
3) What is the smallest pair of square mosaics that satisfies the rules.
4) What is the fewest number of colors necessary to form such a pair?
5) Provide an example of the smallest pair using the fewest number of colors?


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.

I want to see these problems solved with Piet. Any takers?

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.

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.