Combinatorial explosion and Project Euler 393

Last week I found a nice video about algorithmic combinatorial explosion. It was very interesting but it's a bit sad to see the big sister throwing away her life in order to teach her little students the perils of trying to compute combinatorial problems that grow very fast. The problem they studied didn't seem to be hard, just enumerate all the ways you can go from one corner to the opposite corner in a rectangular grid without passing the same node twice. Deceptively simple, for a 1x1 grid there are only 2 ways, for a 2x2 grid there are 12 ways:

However things get ugly as long as we start increasing the size, for 5x5 grids she needs to use a computer to find the 1'262,816 ways. For grids greater that 6x6, she uses a supercomputer to get the answer without waiting so much and even with that the 8x8 grid takes 4.5 hours to be solved. The 9x9 grid takes 6.5 years to be solved. When she goes to compute the 10x10 grid she must be prepared to await almost 250,000 years to obtain the answer! Enumerating this way the solutions for the 11x11 grid would take the double of the estimated age of the universe. Here is the video:

Coincidentally, last week Project Euler problem 393 was somehow similar:

An nxn grid of squares contains n² ants, one ant per square.
All ants decide to move simultaneously to an adjacent square (usually 4 possibilities, except for ants on the edge of the grid or at the corners). We define f(n) to be the number of ways this can happen without any ants ending on the same square and without any two ants crossing the same edge between two squares.
You are given that f(4) = 88. Find f(10). 

So I decided to give it a shot enumerating the solutions for small numbers. consider for simplicity the case where (n = 2), the initial grid would be:

where we have enumerated the ants from 1 to 4 in their starting cell. The ants can move only one cell to any adjacent cell. If we obviate the condition of two ants never crossing the same edge, the number of different positions we can obtain are the ones shown below:

If we take in account the constraint condition we'll need to discard the positions shown below because to obtain these positions two ants have needed to cross the same edge:

So the problem for the case (n = 2) has only two final positions:

In order to enumerate the solutions for (n = 4) I implemented a DFS algorithm. Here is the code in Killa (my programming language):

	var count // number of final positions
	var N // total cells in the board
	var n // grid partition
	function dfs(now, next) {
	for (var k = 0; k < N; k += 1) {
	// Find an ant to move.
	if (now[k] > 0) {
	// Try to move it to the right.
	if ((k % n < n - 1) && (next[k + 1] == 0)
	&& ((next[k] == 0) || (next[k] != now[k] + 1))) {
	next[k + 1] = now[k]
	now[k] = 0
	dfs(now, next)
	now[k] = next[k + 1]
	next[k + 1] = 0
	}
	// Try to move it to the left.
	if ((k % n > 0) && (next[k - 1] == 0)
	&& ((next[k] == 0) || (next[k] != now[k] - 1))) {
	next[k - 1] = now[k]
	now[k] = 0
	dfs(now, next)
	now[k] = next[k - 1]
	next[k - 1] = 0
	}
	// Try to move it up.
	if ((k >= n) && (next[k - n] == 0)
	&& ((next[k] == 0) || (next[k] != now[k] - n))) {
	next[k - n] = now[k]
	now[k] = 0
	dfs(now, next)
	now[k] = next[k - n]
	next[k - n] = 0
	}
	// Try to move it down.
	if ((k < N - n) && (next[k + n] == 0)
	&& ((next[k] == 0) || (next[k] != now[k] + n))) {
	next[k + n] = now[k]
	now[k] = 0
	dfs(now, next)
	now[k] = next[k + n]
	next[k + n] = 0
	}
	// We don't need to consider the other ants. The above exploration
	// has already found all the other possibilities.
	break
	}
	}
	// Check if the position is valid.
	for (var i = 0; i < N; i += 1) {
	if (next[i] == 0) {
	return
	}
	}
	// We implemented the DFS exploration in such a way that if we got here
	// we must have a valid final position. So we increase the counter.
	count += 1
	}
	function euler_393(size) {
	count = 0
	n = size
	N = n * n
	// This array holds the ants that need to be moved.
	var now = []
	// This array holds the ants that have already been moved.
	var next = []
	// Initialize positions, 0 is empty.
	for (var k = 0; k < N; k += 1) {
	now[k] = k + 1
	next[k] = 0
	}
	// Use Depth First Search to compute the number of possible ways.
	dfs(now, next)
	return count
	}
	// Warning: this is very slow for n > 4
	print(euler_393(4))

view raw gistfile1.js hosted with ❤ by GitHub

I tried to minimize the memory usage and the condition of two ants not crossing the same edge imposed some additional conditionals that need more explaining but I hope you can follow the code. The answer for (n = 4) is 88, I used the HTML5 canvas element to make a collage with all the different possible final positions. The original board position is:

in which every ant is represented with a different cell color and the different ways that they can move are arranged in the 8x11 matrix below:

Observe that the JavaScript code is almost identical to the code in Killa, if we ignore the drawing routines:

	<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN"
	"http://www.w3.org/TR/html4/loose.dtd">
	<html xmlns="http://www.w3.org/1999/xhtml">
	<head>
	<meta http-equiv="Content-Type" content="text/html; charset=utf-8" />
	<title>Euler 393</title>
	</head>
	<body>
	<div style="text-align: center;">
	<canvas height="902" id="canvas" width="660"></canvas></div>
	<script type="application/javascript">
	var count; // number of final positions
	var N; // total cells in the board
	var n; // grid partition
	var canvas;
	var ctx;
	function dfs(now, next) {
	for (var k = 0; k < N; k += 1) {
	// Find an ant to move.
	if (now[k] > 0) {
	// Try to move it to the right.
	if ((k % n < n - 1) && (next[k + 1] == 0)
	&& ((next[k] == 0) || (next[k] != now[k] + 1))) {
	next[k + 1] = now[k];
	now[k] = 0;
	dfs(now, next);
	now[k] = next[k + 1];
	next[k + 1] = 0;
	}
	// Try to move it to the left.
	if ((k % n > 0) && (next[k - 1] == 0)
	&& ((next[k] == 0) || (next[k] != now[k] - 1))) {
	next[k - 1] = now[k];
	now[k] = 0;
	dfs(now, next);
	now[k] = next[k - 1];
	next[k - 1] = 0;
	}
	// Try to move it up.
	if ((k >= n) && (next[k - n] == 0)
	&& ((next[k] == 0) || (next[k] != now[k] - n))) {
	next[k - n] = now[k];
	now[k] = 0;
	dfs(now, next);
	now[k] = next[k - n];
	next[k - n] = 0;
	}
	// Try to move it down.
	if ((k < N - n) && (next[k + n] == 0)
	&& ((next[k] == 0) || (next[k] != now[k] + n))) {
	next[k + n] = now[k];
	now[k] = 0;
	dfs(now, next);
	now[k] = next[k + n];
	next[k + n] = 0;
	}
	// We don't need to consider the other ants. The above exploration
	// has already found all the other possibilities.
	break;
	}
	}
	// Check if the position is valid.
	for (var i = 0; i < N; i += 1) {
	if (next[i] == 0) {
	return;
	}
	}
	// Draw position.
	drawBoard(82 * (count % 8), 82 * Math.floor(count / 8), 18, 18, 1, next);
	// We implemented the DFS exploration in such a way that if we got here
	// we must have a valid final position. So we increase the counter.
	count += 1;
	}
	function euler_393(size) {
	count = 0;
	n = size;
	N = n * n;
	// This array holds the ants that need to be moved.
	var now = [];
	// This array holds the ants that have already been moved.
	var next = [];
	// Initialize positions, 0 is empty.
	for (var k = 0; k < N; k += 1) {
	now[k] = k + 1;
	next[k] = 0;
	}
	// Use Depth First Search to compute the number of possible ways.
	dfs(now, next)
	}
	function drawCell(x, y, w, h, c) {
	switch(c) {
	case 0: ctx.fillStyle = "rgb(66, 46, 71)"; break;
	case 1: ctx.fillStyle = "rgb(77, 87, 117)"; break;
	case 2: ctx.fillStyle = "rgb(181, 120, 9)"; break;
	case 3: ctx.fillStyle = "rgb(128, 106, 42)"; break;
	case 4: ctx.fillStyle = "rgb(0, 255, 221)"; break;
	case 5: ctx.fillStyle = "rgb(77, 170, 189)"; break;
	case 6: ctx.fillStyle = "rgb(250, 155, 0)"; break;
	case 7: ctx.fillStyle = "rgb(255, 204, 51)"; break;
	case 8: ctx.fillStyle = "rgb(250, 181, 135)"; break;
	case 9: ctx.fillStyle = "rgb(247, 139, 106)"; break;
	case 10: ctx.fillStyle = "rgb(171, 217, 4)"; break;
	case 11: ctx.fillStyle = "rgb(234, 242, 5)"; break;
	case 12: ctx.fillStyle = "rgb(235, 42, 55)"; break;
	case 13: ctx.fillStyle = "rgb(242, 90, 73)"; break;
	case 14: ctx.fillStyle = "rgb(114, 166, 3)"; break;
	default: ctx.fillStyle = "rgb(70, 115, 2)"; break;
	}
	ctx.fillRect(x, y, w, h);
	}
	function drawBoard(x, y, w, h, d, board) {
	for (var k = 0; k < 16; ++k) {
	drawCell(x + (k % 4) * (w + d), y + Math.floor(k / 4) * (h + d),
	w, h, board[k] - 1);
	}
	}
	canvas = document.getElementById("canvas");
	if (canvas.getContext) {
	ctx = canvas.getContext("2d");
	euler_393(4);
	console.log("TOTAL:" + count);
	}
	</script>
	</body>
	</html>

view raw euler393.html hosted with ❤ by GitHub

Be aware that this problem is also a combinatorial problem and it suffers from the same problem in the video, so the DFS algorithm is not going to end for (n = 10). In C++, the above algorithm took some time to calculate even the modest 6x6 board, I got bored awaiting the answer for the 8x8 board and killed the process. So how can we solve this for (n = 10)? Take in account that the problem doesn't require from you to generate all the different positions (like we did here for showing them graphically), we need only the final number of positions and that could be done using (spoiler): dynamic programming.

So have fun coding, and check your heart.