In this article I describe a way of modifying Dijkstra’s Alogrithm in order to find all the shortest path from a source to a node.

This article assumes you know how Dijkstra’s Algorithm works. If you don’t, see my previous post or the Wikipedia article.

The Problem

You know how to use Dijkstra’s algorithm to find the length of the shortest path to a node. You’ve even figured out how to record the path to each node. But you what you really need are all the shortest paths leading to a node.

The Idea

I can help, but to be honest, this is obvious.

In order to record the path to each node, I used an array to record which node comes before each other node in the shortest path. That is to say: prev[i] was the node that comes just before node i in the shortest path from the source to node i.

To record all the shortest paths that lead to a node, I just turned prev into a matrix with the following meaning: prev[i][0] is the number of nodes that could come before node i on a path of minimum length; prev[i][1..] are the nodes that could come before node i on path of minimum length.

The Programme

Here’s the code in C (dijkstraAll.c):

#include

#define GRAPHSIZE 2048
#define INFINITY GRAPHSIZE*GRAPHSIZE
#define MAX(a, b) ((a > b) ? (a) : (b))

int e; /* The number of nonzero edges in the graph */
int n; /* The number of nodes in the graph */
long dist[GRAPHSIZE][GRAPHSIZE]; /* dist[i][j] is the distance between node i and j; or 0 if there is no direct connection */
long d[GRAPHSIZE]; /* d[i] is the length of the shortest path between the source (s) and node i */
int prev[GRAPHSIZE][GRAPHSIZE + 1]; /* prev[i] holds the nodes that could comes right before i in the shortest path from the source to i;
prev[i][0] is the number of nodes and prev[i][1..] are the nodes */

void printD() {
int i;

printf(“Distances:\n”);
for (i = 1; i <= n; ++i) printf("%10d", i); printf("\n"); for (i = 1; i <= n; ++i) { printf("%10ld", d[i]); } printf("\n"); } /* * Prints the shortest path from the source to dest. * * dijkstra(int) MUST be run at least once BEFORE * this is called */ void printPath(int dest, int depth) { int i, j; printf("-%d\n", dest); for (i = 1; i <= prev[dest][0]; ++i) { for (j = 0; j <= depth; ++j) printf(" |"); printPath(prev[dest][i], depth + 1); } } void dijkstra(int s) { int i, k, mini; int visited[GRAPHSIZE]; for (i = 1; i <= n; ++i) { d[i] = INFINITY; prev[i][0] = 0; /* no path has yet been found to i */ visited[i] = 0; /* the i-th element has not yet been visited */ } d[s] = 0; for (k = 1; k <= n; ++k) { mini = -1; for (i = 1; i <= n; ++i) if (!visited[i] && ((mini == -1) || (d[i] < d[mini]))) mini = i; visited[mini] = 1; for (i = 1; i <= n; ++i) if (dist[mini][i]) { if (d[mini] + dist[mini][i] < d[i]) { /* a shorter path has been found */ d[i] = d[mini] + dist[mini][i]; prev[i][0] = 1; prev[i][1] = mini; } else if (d[mini] + dist[mini][i] == d[i]) { /* a path of the same length has been found */ ++prev[i][0]; prev[i][prev[i][0]] = mini; } } } } int main(int argc, char *argv[]) { int i, j; int u, v, w; FILE *fin = fopen("dist.txt", "r"); fscanf(fin, "%d", &e); for (i = 0; i < e; ++i) for (j = 0; j < e; ++j) dist[i][j] = 0; n = -1; for (i = 0; i < e; ++i) { fscanf(fin, "%d%d%d", &u, &v, &w); dist[u][v] = w; n = MAX(u, MAX(v, n)); } fclose(fin); dijkstra(1); printD(); printf("\n"); for (i = 1; i <= n; ++i) { printf("Path to %d:\n", i); printPath(i, 0); printf("\n"); } return 0; } [/sourcecode] And here's an input file: dist.txt.
10
1 2 5
1 4 3
2 3 1
2 4 3
3 5 6
4 2 2
4 3 9
4 5 2
5 1 7
5 3 4

The input file describes this graph:
djAll.png

As you can see, there are two paths from node 1 to node 3: 1 -> 2 -> 3 and 1 -> 4 -> 2 -> 3 both of length 6.

Now, what does the programme output?
Distances:
1 2 3 4 5
0 5 6 3 5

Path to 1:
-1

Path to 2:
-2
|-1
|-4
| |-1

Path to 3:
-3
|-2
| |-1
| |-4
| | |-1

Path to 4:
-4
|-1

Path to 5:
-5
|-4
| |-1

It first outputs the distances, and… yes! They’re correct.

Next, it prints those ASCII art drawings. They not drawings. They’re trees with the destination as root and the leafs as the source. To read a path from such a tree, start at a leaf (always 1) and go left, reading the first numbers you can see above.

Let’s find the paths to node 3. There are two leafs, so there are two paths of minimal length. The first one is 1 -> 4 -> 2 -> 3. The second one is 1 -> 2 -> 3. Check on the graph.

That’s it. If you’re up to a challenge, implement prev as an array of linked lists.

Good luck. Always open to comments.

In this article, I describe a simple (adds less than 1min of work) way to speed up Dijkstra’s Algorithm for finding the single source shortest path to every node in a graph.

In a previous post I described the simple O(n2) implementation of the algorithm. Here, I focus on a method that will probably speed up the algorithm.

Why Bother

The previous implementation of the algorithm ran in O(n2) time, where n is the number of nodes in the graph. This means that for a graph of, say 100 nodes, it would do about 100 * 100 = 100000 calculations. Considering that computers nowadays are said to be able to do about 100000000 (a hundred million) calculations per second, we’re fine, and the programme will finish in well under a second. But what if we have a graph with 100000 nodes? This might take 100 seconds to run. Now we’re in trouble. We need a faster algorithm.

The two most common ways to speed up Dijkstra’s Algorithm are to implement the finding of the closest node not yet visited as priority queues. Usually heaps or Fibonacci Heaps are used for this purpose (Fibonacci Heaps were actually invented for this).

Heaps are somewhat difficult to implement and Fibonacci Heaps are horror to implement. Incidentally, there’s a very easy of speeding it up.

Just Use Queues

The idea is to simply use queues instead of priority queues. This way provides nowhere near the same level of speedup (the algorithm is still O(n2)), but it makes it run faster, on average, by a factor of 4.

Some bad news: a carefully crafted graph could slow this algorithm down to O(n3). As a rule, graphs in real life are never like this, and, as the method isn’t widely known, test sets for contests are not written to catch this optimisation.

Now for the good news: it’s shockingly easy to write. Compare the old dijkstra1() with the new dijkstra2().

void dijkstra1(int s) {
	int i, k, mini;
	int visited[GRAPHSIZE];

	for (i = 1; i <= n; ++i) {
		d1&#91;i&#93; = INFINITY;
		visited&#91;i&#93; = 0; /* the i-th element has not yet been visited */
	}

	d1&#91;s&#93; = 0;

	for (k = 1; k <= n; ++k) {
		mini = -1;
		for (i = 1; i <= n; ++i)
			if (!visited&#91;i&#93; && ((mini == -1) || (d1&#91;i&#93; < d1&#91;mini&#93;)))
				mini = i;

		visited&#91;mini&#93; = 1;

		for (i = 1; i <= n; ++i)
			if (dist&#91;mini&#93;&#91;i&#93;)
				if (d1&#91;mini&#93; + dist&#91;mini&#93;&#91;i&#93; < d1&#91;i&#93;) 
					d1&#91;i&#93; = d1&#91;mini&#93; + dist&#91;mini&#93;&#91;i&#93;;
	}
}

void dijkstra2(int s) {
	int queue&#91;GRAPHSIZE&#93;;
	char inQueue&#91;GRAPHSIZE&#93;;
	int begq = 0,
	    endq = 0;
	int i, mini;
	int visited&#91;GRAPHSIZE&#93;;

	for (i = 1; i <= n; ++i) {
		d2&#91;i&#93; = INFINITY;
		visited&#91;i&#93; = 0; /* the i-th element has not yet been visited */
		inQueue&#91;i&#93; = 0;
	}

	d2&#91;s&#93; = 0;
	queue&#91;endq&#93; = s;
	endq = (endq + 1) % GRAPHSIZE;


	while (begq != endq) {
		mini = queue&#91;begq&#93;;
		begq = (begq + 1) % GRAPHSIZE;
		inQueue&#91;mini&#93; = 0;

		visited&#91;mini&#93; = 1;

		for (i = 1; i <= n; ++i)
			if (dist&#91;mini&#93;&#91;i&#93;)
				if (d2&#91;mini&#93; + dist&#91;mini&#93;&#91;i&#93; < d2&#91;i&#93;) { 
					d2&#91;i&#93; = d2&#91;mini&#93; + dist&#91;mini&#93;&#91;i&#93;;
					if (!inQueue&#91;i&#93;) {
						queue&#91;endq&#93; = i;
						endq = (endq + 1) % GRAPHSIZE;
						inQueue&#91;i&#93; = 1;
					}
				}
	}
}
&#91;/sourcecode&#93;

What's changed? First, we <strong>define several new variables</strong>. These, together, make up the queue:

int queue[GRAPHSIZE];
char inQueue[GRAPHSIZE];
int begq = 0,
    endq = 0;

Next, during the initialisation part of the function, we mark all nodes as not being in the queue.

for (i = 1; i <= n; ++i) {
	/* OTHER INITIALISATIONS (look at the programme) */
	inQueue&#91;i&#93; = 0;
}
&#91;/sourcecode&#93;

Now, add the source node to the queue.
&#91;sourcecode language='cpp'&#93;
queue&#91;endq&#93; = s;
endq = (endq + 1) % GRAPHSIZE;
&#91;/sourcecode&#93;

What does this do? The first line add <strong>s</strong> to the end of the queue. The second line moves the end of the queue one step to the right (I'll explain a few paragraphs down). The modulo operation here is not really necessary, but I like to be consistent.

At this point we'll start looping. When do we stop? The idea here is that a node is in the queue when its neighbours need to be updated (i.e. when a new shortest path might be found leading to them). So, we stop when the queue is empty. Note that this occurs when <strong>begq == endq</strong> and <strong>not</strong> when <strong>!(begq &lt; endq)</strong>. So, <strong>while (begq &lt; endq)</strong> is incorrect because, in one case, <strong>begq</strong> will be greater then <strong>endq</strong>.

What was the first thing we did in the loop? We were supposed to find the closest node not yet visited. Now, we merely take the first node from the queue.

mini = queue[begq];
begq = (begq + 1) % GRAPHSIZE;
inQueue[mini] = 0;

Here, the first element is pop’d out of the queue, the head of the queue is moved one step to the right and the element is marked as not being in the queue. The problem with queues in general, and this one in particular is that the part of them that actually hold the elements tends to move around. Here, every insert moves the tail one step to the right and every pop moves the head one step to the right. Consider the following sequence of operations:

queue.png

Moves 1 through 8 clearly show that, while the size of the information content of the queue changes erratically, it constantly moves to the right. What happened at 9? The queue got to the end of available memory and wrapped around to the beginning. This is the purpose of (begq + 1) % GRAPHSIZE and (endq + 1) % GRAPHSIZE. It turns 7, 8, 9, etc. into 1, 2, 3, etc. But won’t endq overrun begq? No, the use of inQueue guarantees that no element will be inserted in the queue more than once. And as the queue is of size GRAPHSIZE, no overrun is possible.

So far, so good. One last modification: when we update the distance to a node, we add it to the queue (if it’s not already in it).

for (i = 1; i <= n; ++i) if (dist[mini][i]) if (d2[mini] + dist[mini][i] < d2[i]) { d2[i] = d2[mini] + dist[mini][i]; if (!inQueue[i]) { queue[endq] = i; endq = (endq + 1) % GRAPHSIZE; inQueue[i] = 1; } } [/sourcecode]

Comparing the speed

When I first wrote this, I wanted to be able to check that it outputs correct results and I wanted to see how much faster it is. The following programme does both. The function cmpd() checks the output against that given by the simple implementation and the various clock() calls littered through the code time the two functions.

Here’s the code in C (dijkstra2.c):
Note: Source might be mangled by WordPress, consider downloading the file.

#include
#include

#define GRAPHSIZE 2048
#define INFINITY GRAPHSIZE*GRAPHSIZE
#define MAX(a, b) ((a > b) ? (a) : (b))

int e; /* The number of nonzero edges in the graph */
int n; /* The number of nodes in the graph */
long dist[GRAPHSIZE][GRAPHSIZE]; /* dist[i][j] is the distance between node i and j; or 0 if there is no direct connection */
long d1[GRAPHSIZE], d2[GRAPHSIZE]; /* d[i] is the length of the shortest path between the source (s) and node i */

void dijkstra1(int s) {
int i, k, mini;
int visited[GRAPHSIZE];

for (i = 1; i <= n; ++i) { d1[i] = INFINITY; visited[i] = 0; /* the i-th element has not yet been visited */ } d1[s] = 0; for (k = 1; k <= n; ++k) { mini = -1; for (i = 1; i <= n; ++i) if (!visited[i] && ((mini == -1) || (d1[i] < d1[mini]))) mini = i; visited[mini] = 1; for (i = 1; i <= n; ++i) if (dist[mini][i]) if (d1[mini] + dist[mini][i] < d1[i]) d1[i] = d1[mini] + dist[mini][i]; } } void dijkstra2(int s) { int queue[GRAPHSIZE]; char inQueue[GRAPHSIZE]; int begq = 0, endq = 0; int i, mini; int visited[GRAPHSIZE]; for (i = 1; i <= n; ++i) { d2[i] = INFINITY; visited[i] = 0; /* the i-th element has not yet been visited */ inQueue[i] = 0; } d2[s] = 0; queue[endq] = s; endq = (endq + 1) % GRAPHSIZE; while (begq != endq) { mini = queue[begq]; begq = (begq + 1) % GRAPHSIZE; inQueue[mini] = 0; visited[mini] = 1; for (i = 1; i <= n; ++i) if (dist[mini][i]) if (d2[mini] + dist[mini][i] < d2[i]) { d2[i] = d2[mini] + dist[mini][i]; if (!inQueue[i]) { queue[endq] = i; endq = (endq + 1) % GRAPHSIZE; inQueue[i] = 1; } } } } int cmpd() { int i; for (i = 0; i < n; ++i) if (d1[i] != d2[i]) return 0; return 1; } int main(int argc, char *argv[]) { int i, j; int u, v, w; long t1 = 0, t2 = 0; FILE *fin = fopen("dist2.txt", "r"); fscanf(fin, "%d", &e); for (i = 0; i < e; ++i) for (j = 0; j < e; ++j) dist[i][j] = 0; n = -1; for (i = 0; i < e; ++i) { fscanf(fin, "%d%d%d", &u, &v, &w); dist[u][v] = w; n = MAX(u, MAX(v, n)); } fclose(fin); for (i = 1; i <= n; ++i) { long aux = clock(); dijkstra1(i); t1 += clock() - aux; aux = clock(); dijkstra2(i); t2 += clock() - aux; if (i % 10 == 0) { printf("%d / %d\n", i, n); fflush(stdout); } if (!cmpd()) { printf("\nResults for %d do NOT match\n", i); break; } } printf("\n"); printf("Dijkstra O(N^2):\t\t%ld\n", t1); printf("Dijkstra unstable:\t\t%ld\n", t2); printf("Ratio:\t\t\t\t%.2f\n", (float)t1/t2); /* printD(); */ return 0; } [/sourcecode] And here's a big 1200 node graph: dist2.txt.

Have fun and good luck. Always open to comments.

In this article I describe Dijkstra’s algorithm for finding the shortest path from one source to all the other vertexes in a graph. Afterwards, I provide the source code in C of a simple implementation.

To understand this you should know what a graph is, and how to store one in memory. If in doubt check this and this.

Another solution for this problem is the Bellman-Ford algorithm.

The Problem

Given the following graph calculate the length of the shortest path from node 1 to every other node.
dj1.png

Lets take the nodes 1 and 3. There are several paths (1 -> 4 -> 3, 1 -> 2 -> 3, etc.), but the shortest of them is 1 -> 4 -> 2 -> 3 of length 9. Our job is to find it.

The Algorithm

Dijkstra’s algorithm is one of the most common solutions to this problem. Even so, it only works on graphs which have no edges of negative weight, and the actual speed of the algorithm can vary from O(n*lg(lg(n))) to O(n2).

The idea is somewhat simple:

Take the length of the shortest path to all nodes to be infinity. Mark the length of the shortest path to the source as 0.

dj2.png

Now, we already know that the graph has no edges of negative weight so the a path of length 0 is the best we can come up with. The path to the source is 0, so it’s optimal.

This algorithm works by making the paths to one more node optimal at each step. So, at the kth step, you know for sure that there are at least k nodes to which you know the shortest path.

At each step, choose the node, which is not yet optimal, but which is closest to the source; i.e. the node to which the current calculated shortest path is smallest. Then, from it, try to optimise the path to every node connected to it. Finally, mark the said node as optimal (visited, if you prefer). In the previous example, the node which is closest to the source and is not yet optimal is the source. From it, you can optimise the path to nodes 2 and 4.
dj3_1.png

At this point, the only visited/optimal node is 0. Now we have to redo this step 4 more times (to ensure that all nodes are optimal).

The next node to consider is 4:
dj4.png

It’s worthwhile to note that at this step, we’ve also found a better path to node 2.
Next is node 2:
dj5.png

Finally, we look at nodes 5 and 3 (none of which offer any optimisations):
dj5.png

dj5.png

The actual code in C looks something like this:

void dijkstra(int s) {
        int i, k, mini;
        int visited[GRAPHSIZE];

        for (i = 1; i <= n; ++i) {
                d&#91;i&#93; = INFINITY;
                visited&#91;i&#93; = 0; /* the i-th element has not yet been visited */
        }

        d&#91;s&#93; = 0;

        for (k = 1; k <= n; ++k) {
                mini = -1;
                for (i = 1; i <= n; ++i)
                        if (!visited&#91;i&#93; && ((mini == -1) || (d&#91;i&#93; < d&#91;mini&#93;)))
                                mini = i;

                visited&#91;mini&#93; = 1;

                for (i = 1; i <= n; ++i)
                        if (dist&#91;mini&#93;&#91;i&#93;)
                                if (d&#91;mini&#93; + dist&#91;mini&#93;&#91;i&#93; < d&#91;i&#93;)
                                        d&#91;i&#93; = d&#91;mini&#93; + dist&#91;mini&#93;&#91;i&#93;;
        }
}
&#91;/sourcecode&#93;

<h4>The Programme</h4>
Putting the above into context, we get the <strong>O(n<sup>2</sup>)</strong> implementation. This works well for most graphs (it will <strong>not</strong> work for graphs with negative weight edges), and it's quite fast.

Here's the source code in C (<a href='https://compprog.files.wordpress.com/2007/12/dijkstra.c' title='dijkstra.c'>dijkstra.c</a>):

#include <stdio.h>

#define GRAPHSIZE 2048
#define INFINITY GRAPHSIZE*GRAPHSIZE
#define MAX(a, b) ((a > b) ? (a) : (b))

int e; /* The number of nonzero edges in the graph */
int n; /* The number of nodes in the graph */
long dist[GRAPHSIZE][GRAPHSIZE]; /* dist[i][j] is the distance between node i and j; or 0 if there is no direct connection */
long d[GRAPHSIZE]; /* d[i] is the length of the shortest path between the source (s) and node i */

void printD() {
	int i;
	for (i = 1; i <= n; ++i)
		printf("%10d", i);
	printf("\n");
	for (i = 1; i <= n; ++i) {
		printf("%10ld", d&#91;i&#93;);
	}
	printf("\n");
}

void dijkstra(int s) {
	int i, k, mini;
	int visited&#91;GRAPHSIZE&#93;;

	for (i = 1; i <= n; ++i) {
		d&#91;i&#93; = INFINITY;
		visited&#91;i&#93; = 0; /* the i-th element has not yet been visited */
	}

	d&#91;s&#93; = 0;

	for (k = 1; k <= n; ++k) {
		mini = -1;
		for (i = 1; i <= n; ++i)
			if (!visited&#91;i&#93; && ((mini == -1) || (d&#91;i&#93; < d&#91;mini&#93;)))
				mini = i;

		visited&#91;mini&#93; = 1;

		for (i = 1; i <= n; ++i)
			if (dist&#91;mini&#93;&#91;i&#93;)
				if (d&#91;mini&#93; + dist&#91;mini&#93;&#91;i&#93; < d&#91;i&#93;) 
					d&#91;i&#93; = d&#91;mini&#93; + dist&#91;mini&#93;&#91;i&#93;;
	}
}

int main(int argc, char *argv&#91;&#93;) {
	int i, j;
	int u, v, w;

	FILE *fin = fopen("dist.txt", "r");
	fscanf(fin, "%d", &e);
	for (i = 0; i < e; ++i)
		for (j = 0; j < e; ++j)
			dist&#91;i&#93;&#91;j&#93; = 0;
	n = -1;
	for (i = 0; i < e; ++i) {
		fscanf(fin, "%d%d%d", &u, &v, &w);
		dist&#91;u&#93;&#91;v&#93; = w;
		n = MAX(u, MAX(v, n));
	}
	fclose(fin);

	dijkstra(1);

	printD();

	return 0;
}
&#91;/sourcecode&#93;

And here's a sample input file(<a href='https://compprog.files.wordpress.com/2007/12/dist.txt' title='dist.txt'>dist.txt</a>):

<code>10
1 2 10
1 4 5
2 3 1
2 4 3
3 5 6
4 2 2
4 3 9
4 5 2
5 1 7
5 3 4
</code>

The graph is given as an edge list:
<ul>
	<li>the first line contains <em>e</em>, the number of edges</li>
	<li>the following <em>e</em> lines contain <em>3</em> numbers: <em>u</em>, <em>v</em> and <em>w</em> signifying that there's an edge from <em>u</em> to <em>v</em> of weight <em>w</em></li>
</ul>

That's it. Good luck and have fun. Always open to comments.

<h4>Finding the shortest path</h4>
<strong>UPDATE</strong> In response to <strong>campOs</strong>' comment.

Now we know the distance between the source node and any other node (the distance to the ith node is remembered in <strong>d[i]</strong>). But suppose we also need the path (which nodes make up the path).

Look at the above code. Where is <strong>d</strong> modified? Where is the recorded distance between the source and a node modified? In two places:

Firstly, <strong>d[s]</strong> is initialised to be <em>0</em>.

d[s] = 0;

And then, when a new shortest path is found, d[i] is updated accordingly:

for (i = 1; i <= n; ++i)
	if (dist&#91;mini&#93;&#91;i&#93;)
		if (d&#91;mini&#93; + dist&#91;mini&#93;&#91;i&#93; < d&#91;i&#93;) 
			d&#91;i&#93; = d&#91;mini&#93; + dist&#91;mini&#93;&#91;i&#93;;
&#91;/sourcecode&#93;

The important thing to notice here is that <strong>when you update the shortest distance to node i, you know the previous node in the path to i</strong>. This is, of course, <strong>mini</strong>. This suggests the solution to our problem.

For every node <strong>i</strong> other than the source, remember not only the distance to it, but also the previous node in the path to it. Thus we have a new array, <strong>prev</strong>.

Now, we need to make to modifications.
First, we initialise the value of <strong>prev[i]</strong> to something impossible (say <em>-1</em>) at the start of <strong>dijkstra()</strong>.

for (i = 1; i <= n; ++i) {
	d&#91;i&#93; = INFINITY;
	prev&#91;i&#93; = -1; /* no path has yet been found to i */
	visited&#91;i&#93; = 0; /* the i-th element has not yet been visited */
}
&#91;/sourcecode&#93;

Secondly, we update the value of <strong>prev[i]</strong> every time a new shortest path is found to i.

for (i = 1; i <= n; ++i)
	if (dist&#91;mini&#93;&#91;i&#93;)
		if (d&#91;mini&#93; + dist&#91;mini&#93;&#91;i&#93; < d&#91;i&#93;) {
			d&#91;i&#93; = d&#91;mini&#93; + dist&#91;mini&#93;&#91;i&#93;;
			prev&#91;i&#93; = mini;
		}
&#91;/sourcecode&#93;

Good. For every node reachable from the source we know which node is just before it in the shortest path. For the above example, we would have the following array:
<code>i - prev[i]
1 - -1
2 - 4
3 - 2
4 - 1
5 - 4
</code>

Using this, how do you get the path? Let's say you want to get to <em>3</em>. Which node comes right before <em>3</em>? Node <em>2</em>. Which node comes right before node <em>2</em>? Node <em>4</em>. Which node comes before <em>4</em>? Node <em>1</em>. We've reached the source, so we're done. Go through this list backwards and you get the path: <em>1 -&gt; 4 -&gt; 2 -&gt; 3</em>. This is easily implemented with <a href="http://en.wikipedia.org/wiki/Recursion">recursion</a>.


void printPath(int dest) {
	if (prev[dest] != -1)
		printPath(prev[dest]);
	printf("%d ", dest);
}

Here is the updated source: dijkstraWithPath.c.

Good luck.

In this article, I describe the Bellman-Ford algorithm for finding the one-source shortest paths in a graph, give an informal proof and provide the source code in C for a simple implementation.

To understand this you should know what a graph is, and how to store one in memory. If in doubt check this and this.

Another solution to this problem is Dijkstra’s algorithm.

The Problem

Given the following graph, calculate the length of the shortest path from node 1 to node 2.
bf1.png

It’s obvious that there’s a direct route of length 6, but take a look at path: 1 -> 4 -> 3 -> 2. The length of the path is 7 – 3 – 2 = 2, which is less than 6. BTW, you don’t need negative edge weights to get such a situation, but they do clarify the problem.

This also suggests a property of shortest path algorithms: to find the shortest path form x to y, you need to know, beforehand, the shortest paths to y‘s neighbours. For this, you need to know the paths to y‘s neighbours’ neighbours… In the end, you must calculate the shortest path to the connected component of the graph in which x and y are found.

That said, you usually calculate the shortest path to all nodes and then pick the ones you’re intrested in.

The Algorithm

The Bellman-Ford algorithm is one of the classic solutions to this problem. It calculates the shortest path to all nodes in the graph from a single source.

The basic idea is simple:
Start by considering that the shortest path to all nodes, less the source, is infinity. Mark the length of the path to the source as 0:
bf2.png

Take every edge and try to relax it:
bf3.png

Relaxing an edge means checking to see if the path to the node the edge is pointing to can’t be shortened, and if so, doing it. In the above graph, by checking the edge 1 -> 2 of length 6, you find that the length of the shortest path to node 1 plus the length of the edge 1 -> 2 is less then infinity. So, you replace infinity in node 2 with 6. The same can be said for edge 1 -> 4 of length 7. It’s also worth noting that, practically, you can’t relax the edges whose start has the shortest path of length infinity to it.

Now, you apply the previous step n – 1 times, where n is the number of nodes in the graph. In this example, you have to apply it 4 times (that’s 3 more times).
bf4.png

bf5.png

bf6.png

That’s it, here’s the algorithm in a condensed form:

void bellman_ford(int s) {
int i, j;

for (i = 0; i < n; ++i) d[i] = INFINITY; d[s] = 0; for (i = 0; i < n - 1; ++i) for (j = 0; j < e; ++j) if (d[edges[j].u] + edges[j].w < d[edges[j].v]) d[edges[j].v] = d[edges[j].u] + edges[j].w; } [/sourcecode] Here, d[i] is the shortest path to node i, e is the number of edges and edges[i] is the i-th edge.

It may not be obvious why this works, but take a look at what is certain after each step. After the first step, any path made up of at most 2 nodes will be optimal. After the step 2, any path made up of at most 3 nodes will be optimal… After the (n – 1)-th step, any path made up of at most n nodes will be optimal.

The Programme

The following programme just puts the bellman_ford function into context. It runs in O(VE) time, so for the example graph it will do something on the lines of 5 * 9 = 45 relaxations. Keep in mind that this algorithm works quite well on graphs with few edges, but is very slow for dense graphs (graphs with almost n2 edges). For graphs with lots of edges, you’re better off with Dijkstra’s algorithm.

Here’s the source code in C (bellmanford.c):

#include

typedef struct {
int u, v, w;
} Edge;

int n; /* the number of nodes */
int e; /* the number of edges */
Edge edges[1024]; /* large enough for n <= 2^5=32 */ int d[32]; /* d[i] is the minimum distance from node s to node i */ #define INFINITY 10000 void printDist() { int i; printf("Distances:\n"); for (i = 0; i < n; ++i) printf("to %d\t", i + 1); printf("\n"); for (i = 0; i < n; ++i) printf("%d\t", d[i]); printf("\n\n"); } void bellman_ford(int s) { int i, j; for (i = 0; i < n; ++i) d[i] = INFINITY; d[s] = 0; for (i = 0; i < n - 1; ++i) for (j = 0; j < e; ++j) if (d[edges[j].u] + edges[j].w < d[edges[j].v]) d[edges[j].v] = d[edges[j].u] + edges[j].w; } int main(int argc, char *argv[]) { int i, j; int w; FILE *fin = fopen("dist.txt", "r"); fscanf(fin, "%d", &n); e = 0; for (i = 0; i < n; ++i) for (j = 0; j < n; ++j) { fscanf(fin, "%d", &w); if (w != 0) { edges[e].u = i; edges[e].v = j; edges[e].w = w; ++e; } } fclose(fin); /* printDist(); */ bellman_ford(0); printDist(); return 0; } [/sourcecode] And here's the input file used in the example (dist.txt):
5
0 6 0 7 0
0 0 5 8 -4
0 -2 0 0 0
0 0 -3 9 0
2 0 7 0 0

That’s an adjacency matrix.

That’s it. Have fun. Always open to comments.

In this article I give an informal definition of a graph and of the minimum spanning tree. Afterwards I describe Prim’s algorithm and then follow its execution on an example. Finally, the code in C is provided.

Graphs

Wikipedia gives one of the common definitions of a graph:

In computer science, a graph is a kind of data structure, specifically an abstract data type (ADT), that consists of a set of nodes and a set of edges that establish relationships (connections) between the nodes. The graph ADT follows directly from the graph concept from mathematics.
Informally, G=(V,E) consists of vertices, the elements of V, which are connected by edges, the elements of E. Formally, a graph, G, is defined as an ordered pair, G=(V,E), where V is a finite set and E is a set consisting of two element subsets of V.

This is a graph:
p1.png

It’s a set of nodes (A, B, C, D and E) and the edges (lines) that interconnect them.

An important thing to note about this graph is that the edges are bidirectional, i.e. if A is connected to B, then B is connected to A. This makes it an undirected graph.

A common extension is to attribute weights to the edges. This is what I’ve done with the previous graph:
p2

Minimum spanning trees

Basically a minimum spanning tree is a subset of the edges of the graph, so that there’s a path form any node to any other node and that the sum of the weights of the edges is minimum.

Here’s the minimum spanning tree of the example:
g3.png

Look at the above image closely. It contains all of the initial nodes and some of the initial edges. Actually it contains exactly n – 1 edges, where n is the number of nodes. It’s called a tree because there are no cycles.

You can think of the graph as a map, with the nodes being cities, the edges passable terrain, and the weights the distance between the cities.

It’s worth mentioning that a graph can have several minimum spanning trees. Think of the above example, but replace all the weight with 1. The resulting graph will have 6 minimum spanning trees.

Given a graph, find one of its minimum spanning trees.

Prim’s Algorithm

One of the classic algorithms for this problem is that found by Robert C. Prim. It’s a greedy style algorithm and it’s guaranteed to produce a correct result.

In the following discussion, let the distance from each node not in the tree to the tree be the edge of minimal weight between that node and some node in the tree. If there is no such edge, assume the distance is infinity (this shouldn’t happen).

The algorithm (greedily) builds the minimal spanning tree by iteratively adding nodes into a working tree:

  1. Start with a tree which contains only one node.
  2. Identify a node (outside the tree) which is closest to the tree and add the minimum weight edge from that node to some node in the tree and incorporate the additional node as a part of the tree.
  3. If there are less then n – 1 edges in the tree, go to 2

For the example graph, here’s how it would run:

Start with only node A in the tree.
g4.png

Find the closest node to the tree, and add it.
g5.png

Repeat until there are n – 1 edges in the tree.
g6.png

g7.png

g8.png

The Programme

The following programme just follows the algorithm. It runs in O(n2) time.

Here’s the code in C (prim.c):

#include <stdio.h>

/*
	The input file (weight.txt) look something like this
		4
		0 0 0 21
		0 0 8 17
		0 8 0 16
		21 17 16 0

	The first line contains n, the number of nodes.
	Next is an nxn matrix containg the distances between the nodes
	NOTE: The distance between a node and itself should be 0
*/

int n; /* The number of nodes in the graph */

int weight[100][100]; /* weight[i][j] is the distance between node i and node j;
			if there is no path between i and j, weight[i][j] should
			be 0 */

char inTree[100]; /* inTree[i] is 1 if the node i is already in the minimum
			spanning tree; 0 otherwise*/

int d[100]; /* d[i] is the distance between node i and the minimum spanning
		tree; this is initially infinity (100000); if i is already in
		the tree, then d[i] is undefined;
		this is just a temporary variable. It's not necessary but speeds
		up execution considerably (by a factor of n) */

int whoTo[100]; /* whoTo[i] holds the index of the node i would have to be
			linked to in order to get a distance of d[i] */

/* updateDistances(int target)
	should be called immediately after target is added to the tree;
	updates d so that the values are correct (goes through target's
	neighbours making sure that the distances between them and the tree
	are indeed minimum)
*/
void updateDistances(int target) {
	int i;
	for (i = 0; i < n; ++i)
		if ((weight&#91;target&#93;&#91;i&#93; != 0) && (d&#91;i&#93; > weight[target][i])) {
			d[i] = weight[target][i];
			whoTo[i] = target;
		}
}

int main(int argc, char *argv[]) {
	FILE *f = fopen("dist.txt", "r");
	fscanf(f, "%d", &n);
	int i, j;
	for (i = 0; i < n; ++i)
		for (j = 0; j < n; ++j)
			fscanf(f, "%d", &weight&#91;i&#93;&#91;j&#93;);
	fclose(f);

	/* Initialise d with infinity */
	for (i = 0; i < n; ++i)
		d&#91;i&#93; = 100000;

	/* Mark all nodes as NOT beeing in the minimum spanning tree */
	for (i = 0; i < n; ++i)
		inTree&#91;i&#93; = 0;

	/* Add the first node to the tree */
	printf("Adding node %c\n", 0 + 'A');
	inTree&#91;0&#93; = 1;
	updateDistances(0);

	int total = 0;
	int treeSize;
	for (treeSize = 1; treeSize < n; ++treeSize) {
		/* Find the node with the smallest distance to the tree */
		int min = -1;
		for (i = 0; i < n; ++i)
			if (!inTree&#91;i&#93;)
				if ((min == -1) || (d&#91;min&#93; > d[i]))
					min = i;

		/* And add it */
		printf("Adding edge %c-%c\n", whoTo[min] + 'A', min + 'A');
		inTree[min] = 1;
		total += d[min];

		updateDistances(min);
	}

	printf("Total distance: %d\n", total);

	return 0;
}

And here’s a sample input file (dist.txt). It’s the example graph:
5
0 10 0 5 0
10 0 5 5 10
0 5 0 0 0
5 5 0 0 20
0 10 0 20 0

The code’s commented and there shouldn’t be any problems.

Good luck. Always open to comments.

Sudoku is that Japanese puzzle that requires you to fill in a grid of numbers. Here, I describe a general algorithm to solve these puzzles. Also provided is the source code in C++.

You can see a Sudoku board below. The goal is to fill in every empty cell with a number between 1 and 9 so that no number repeats itself on any line, column of zone (three-by-three marked square).

A sudokuĀ board

If you’ve never solved a Sudoku before, now would be the time to do it. Wikipedia describes some useful strategies.

How do you approach a problem like this? The simplest way is from input to output. What’s your input? It’s a 9×9 matrix of numbers like this one:
5 3 0 0 7 0 0 0 0
6 0 0 1 9 5 0 0 0
0 9 8 0 0 0 0 6 0
8 0 0 0 6 0 0 0 3
4 0 0 8 0 3 0 0 1
7 0 0 0 2 0 0 0 6
0 6 0 0 0 0 2 8 0
0 0 0 4 1 9 0 0 5
0 0 0 0 8 0 0 7 9

How do you store it in the programme? If you said as a matrix, you were close. A matrix is obvious, it’s easy to understand, but it’s a pain to code. Believe me when I say, it’s a lot easier to store it as an array of 9*9 elements. What else do you need? A variable to keep track of how many cells have been filled in (0 means empty board; 81 means full board). An array of bitsets to keep track of what digits can’t be used in each cell (I’ll explain a little later), and the setter and getter functions. As it happens, it’s also easier if you encapsulate it in a C++ class. Here’s the full code to the programme (sudoku.cpp). I’ll explain it all in a bit.

#include <iostream>
#include <fstream>

using namespace std;

class SudokuBoard;
void printB(SudokuBoard sb);

typedef unsigned int uint;

const uint MAXVAL = 9;
const uint L = 9;
const uint C = 9;
const uint S = L * C;
const uint ZONEL = 3;
const uint ZONEC = 3;
const uint ZONES = ZONEL * ZONEC;

const uint lineElements[L][C] = {
    { 0,  1,  2,  3,  4,  5,  6,  7,  8},
    { 9, 10, 11, 12, 13, 14, 15, 16, 17},
    {18, 19, 20, 21, 22, 23, 24, 25, 26},
    {27, 28, 29, 30, 31, 32, 33, 34, 35},
    {36, 37, 38, 39, 40, 41, 42, 43, 44},
    {45, 46, 47, 48, 49, 50, 51, 52, 53},
    {54, 55, 56, 57, 58, 59, 60, 61, 62},
    {63, 64, 65, 66, 67, 68, 68, 70, 71},
    {72, 73, 74, 75, 76, 77, 78, 79, 80}
};

const uint columnElements[C][L] = {
    { 0,  9, 18, 27, 36, 45, 54, 63, 72},
    { 1, 10, 19, 28, 37, 46, 55, 64, 73},
    { 2, 11, 20, 29, 38, 47, 56, 65, 74},
    { 3, 12, 21, 30, 39, 48, 57, 66, 75},
    { 4, 13, 22, 31, 40, 49, 58, 67, 76},
    { 5, 14, 23, 32, 41, 50, 59, 68, 77},
    { 6, 15, 24, 33, 42, 51, 60, 69, 78},
    { 7, 16, 25, 34, 43, 52, 61, 70, 79},
    { 8, 17, 26, 35, 44, 53, 62, 71, 80}
};

const uint zoneElements[S / ZONES][ZONES] = {
    { 0,  1,  2,  9, 10, 11, 18, 19, 20},
    { 3,  4,  5, 12, 13, 14, 21, 22, 23},
    { 6,  7,  8, 15, 16, 17, 24, 25, 26},
    {27, 28, 29, 36, 37, 38, 45, 46, 47},
    {30, 31, 32, 39, 40, 41, 48, 49, 50},
    {33, 34, 35, 42, 43, 44, 51, 52, 53},
    {54, 55, 56, 63, 64, 65, 72, 73, 74},
    {57, 58, 59, 66, 67, 68, 75, 76, 77},
    {60, 61, 62, 68, 70, 71, 78, 79, 80}
};

class SudokuBoard {
public:
    SudokuBoard() :
        filledIn(0)
    {
        for (uint i(0); i < S; ++i)
            table&#91;i&#93; = usedDigits&#91;i&#93; = 0;
    }

    virtual ~SudokuBoard() {
    }

    int const at(uint l, uint c) { // Returns the value at line l and row c
        if (isValidPos(l, c))
            return table&#91;l * L + c&#93;;
        else
            return -1;
    }

    void set(uint l, uint c, uint val) { // Sets the cell at line l and row c to hold the value val
        if (isValidPos(l, c) && ((0 < val) && (val <= MAXVAL))) {
            if (table&#91;l * C + c&#93; == 0)
                ++filledIn;
            table&#91;l * C + c&#93; = val;
            for (uint i = 0; i < C; ++i) // Update lines
                usedDigits&#91;lineElements&#91;l&#93;&#91;i&#93;&#93; |= 1<<val;
            for (uint i = 0; i < L; ++i) // Update columns
                usedDigits&#91;columnElements&#91;c&#93;&#91;i&#93;&#93; |= 1<<val;
            int z = findZone(l * C + c);
            for (uint i = 0; i < ZONES; ++i) // Update columns
                usedDigits&#91;zoneElements&#91;z&#93;&#91;i&#93;&#93; |= 1<<val;
        }
    }

    void solve() {
        try { // This is just a speed boost
            scanAndSet(); // Logic approach
            goBruteForce(); // Brute force approach
        } catch (int e) { // This is just a speed boost
        }
    }

    void scanAndSet() {
        int b;
        bool changed(true);
        while (changed) {
            changed = false;
            for (uint i(0); i < S; ++i)
                if (0 == table&#91;i&#93;) // Is there a digit already written?
                    if ((b = bitcount(usedDigits&#91;i&#93;)) == MAXVAL - 1) { // If there's only one digit I can place in this cell, do
                        int d(1); // Find the digit
                        while ((usedDigits&#91;i&#93; & 1<<d) > 0)
                            ++d;
                        set(i / C, i % C, d); // Fill it in
                        changed = true; // The board has been changed so this step must be rerun
                    } else if (bitcount(usedDigits[i]) == MAXVAL)
                        throw 666; // Speed boost
        }
    }

    void goBruteForce() {
        int max(-1); // Find the cell with the _minimum_ number of posibilities (i.e. the one with the largest number of /used/ digits)
        for (uint i(0); i < S; ++i)
            if (table&#91;i&#93; == 0) // Is there a digit already written?
                if ((max == -1) || (bitcount(usedDigits&#91;i&#93;) > bitcount(usedDigits[max])))
                    max = i;

        if (max != -1) {
            for (uint i(1); i <= MAXVAL; ++i) // Go through each possible digit
                if ((usedDigits&#91;max&#93; & 1<<i) == 0) { // If it can be placed in this cell, do
                    SudokuBoard temp(*this); // Create a new board
                    temp.set(max / C, max % C, i); // Complete the attempt
                    temp.solve(); // Solve it
                    if (temp.getFilledIn() == S) { // If the board was completely solved (i.e. the number of filled in cells is S)
                        for (uint j(0); j < S; ++j) // Copy the board into this one
                            set(j / C, j % C, temp.at(j / C, j % C));
                        return; // Break the recursive cascade
                    }
                }
        }
    }

    uint getFilledIn() {
        return filledIn;
    }

private:
    uint table&#91;S&#93;;
    uint usedDigits&#91;S&#93;;
    uint filledIn;

    bool const inline isValidPos(int l, int c) {
        return ((0 <= l) && (l < (int)L) && (0 <= c) && (c < (int)C));
    }

    uint const inline findZone(uint off) {
        return ((off / C / ZONEL) * (C / ZONEC) + (off % C / ZONEC));
    }

    uint const inline bitcount(uint x) {
        uint count(0);
        for (; x; ++count, x &= (x - 1));
        return count;
    }
};

void printB(SudokuBoard sb) {
    cout << "  |  -------------------------------  |" << endl;
    for (uint i(0); i < S; ++i) {
        if (i % 3 == 0)
            cout << "  |";
        cout << "  " << sb.at(i / L, i % L);
        if (i % C == C - 1) {
            if (i / C % 3 == 2)
                cout << "  |" << endl << "  |  -------------------------------";
            cout << "  |" << endl;
        }
    }
    cout << endl;
}

int main(int argc, char *argv&#91;&#93;) {
    SudokuBoard sb;

    ifstream fin("sudoku4.in");
    int aux;
    for (uint i(0); i < S; ++i) {
        fin >> aux;
        sb.set(i / L, i % L, aux);
    }
    fin.close();

    printB(sb);
    sb.solve();
    printB(sb);

    return 0;
}

Look at the main function. It first opens a file and then reads S ints from it. S is just the number of columns (C) multiplied by the number of lines (L). It reads the value into an auxiliary variable and then sets it in the SudokuBoard.

How does it set a cell? The relevant code is in set. The first line just checks if the parameters are valid (if the value’s not too large, if the specified cell does not exist, etc.). Then it checks if there’s a value already in the cell (there shouldn’t be). If not, it increments the number of filled-in cells.

Now things get intresting. If a certain cell contains the number n, it should be obvious that none of the cells on the same line, column or zone as the cell can contain n. Look at the board above: because there’s a 5 in cell 1,1, there can’t be any more fives in any of the cells on the first line, on the first column or in the upper-left zone. This is what the remainder of set does. It sets the nth bit in every bitset in whose corresponding cell the number n cannot appear.

Note: For a given cell, it’s trivial to find the line, column and zone in which it happens to be. What’s hard is to find the other cells in the same line, column or zone. To keep things simple, use three arrays of arrays that contain the number of the cells on a certain line, column or zone.

The next function of intrest is solve. If you’ll look at it, you’ll notice that it contains a tryexcept statement. As the comments clearly note, it’s just a speed boost. If you comment it out, the programme will still work (but in some cases a lot slower).

Solve calls two other functions: scanAndSet and goBruteForce. These are both algorithms to determine or guess what value should be placed in which cell.

scanAndSet
void scanAndSet() {
    int b;
    bool changed(true);
    while (changed) {
        changed = false;
        for (uint i(0); i < S; ++i)
            if (0 == table&#91;i&#93;) // Is there a digit already written?
                if ((b = bitcount(usedDigits&#91;i&#93;)) == MAXVAL - 1) { // If there's only one digit I can place in this cell, do
                    int d(1); // Find the digit
                    while ((usedDigits&#91;i&#93; & 1<<d) > 0)
                         ++d;
                    set(i / C, i % C, d); // Fill it in
                    changed = true; // The board has been changed so this step must be rerun
                } else if (bitcount(usedDigits[i]) == MAXVAL)
                    throw 666; // Speed boost
    }
}

The basic idea is this: we have a list of cells that need to be completed (those whose value is 0) and list of digits that cannot be placed in each cell. Go through the list of used digits, searching for a cell in which 8 digits cannot be placed (i.e. there’s only one digit that can be placed), and place it.

Now, every time you place a digit, you change the board a bit, restricting the digits that can be placed in other cells. So, you have to do the previous step until you don’t change anything any more.

There’s also a check in there if the number of used digits for any cell is 9 (i.e. no digit can be placed in the cell). If such a cell exists then the board is clearly wrong, so throw an exception (which is caught in the solve routine).

goBruteForce

void goBruteForce() {
int max(-1); // Find the cell with the _minimum_ number of posibilities (i.e. the one with the largest number of /used/ digits)
for (uint i(0); i < S; ++i) if (table[i] == 0) // Is there a digit already written? if ((max == -1) || (bitcount(usedDigits[i]) > bitcount(usedDigits[max])))
max = i;
if (max != -1) {
for (uint i(1); i <= MAXVAL; ++i) // Go through each possible digit if ((usedDigits[max] & 1<solve you’ll notice that there are some boards that are not completed by scanAndSet. Why? Because there are some boards that can’t be completed through logic alone (and ours isn’t particularly thorough either).

To get over this, you have to use a brute-force algorithm. The idea is simple enough: given the list of which digits cannot be placed in each cell, find the cell in which the minimum number of digits can be placed. For this cell, for every possible digit, write it down and try to solve the board.

This is where it becomes apparent why a C++ object-oriented approach is a smart move. Instead of writing the try in the current board and then having to keep track of what changes are made, simply clone the current board, fill in a cell and let it solve itself.

That’s it. You might want to try some of the other algorithms suggested on the Net. Good luck. Always open to comments.

Checker Challenge is a very famous programming problem. It’s one of the first examples of backtracking anyone learns and variations of it frequently appare in contests.

In this article, I’ll present the classic algorithm for solving it and then a few optimisations to make it run less like a geriatric turtle.

First the problem:

Given a checker table of n lines and n columns, find all the ways of placing n checker pieces so that no two are on the same line, column or diagonal.

If n is greater or equal to 6 there is always at least one way to arrange the pieces. Usually there are a lot of ways (there are 73712 for n = 13).

For n = 6, this is one of the possible four arrangements:

| | O | | | | |
| | | | O | | |
| | | | | | O |
| O | | | | | |
| | | O | | | |
| | | | | O | |

First of all, you need a way to memorise the board. A matrix of n x n is the obvious solution, but it’s not really necessary. Notice that there can be at most one piece on any column, so it’s enough to use an array of n, each element containing the number of the row on which the corresponding element in the matrix is located. e.g. For the board above, the array would be {4, 1, 5, 2, 6, 3}.

Now, how do you approach such a problem? The simplest way (and, as it happens, the fastest) is to solve it recursively: first take the first column and attempt to place a piece on each of the n rows; for each of these, attempt to place a piece on each row of the second column; for every valid such arrangement, try to place a piece on each row of the third column; …; and so on until you place a piece on the nth column, at which point, you have a valid arrangement.

The key point in this algorithm is to know that when you’re working on the kth column, all the pieces on the first k – 1 columns form a valid arrangement.

As it happens, this is way to slow. For n = 10, I got tired of waiting and stopped the programme. If you do the math, you’ll see that for n, this algorithm does about nn recursive calls. This is bad, but if you write the checking routines inefficiently, you can easily make it slower by a factor of n.

There are three ways I know of to check if a position is valid (i.e. if a piece can be placed there). The first checks for validity after the piece has been placed, while the other two work by marking positions as invalid:

  1. The first is simple: let’s say you’ve reached column c and are wondering whether or not you can place a piece of row r. First take all the columns before c and check whether a piece is already on row r; afterwards, for every column c’ before c, and for every row r’ on that column check if abs(r – r’) = c – c’. If any of there conditions are true, than you can’t place a piece on row r.
  2. The second is just a way of trading memory for speed. Instead of doing as above, keep three vectors of boolean values (1 for the lines (usedRows) and 2 for the two types of diagonals (d1 and d2)), and for every piece you place on the board mark the corresponding elements in the three vectors as used. That is, mark rth element in rows, the n – c – 1 + r th element in d1 and the r + c th element in d2. If any of the corresponding elements for any position are marked, than that position is invalid.
  3. The third way is just combining the first two. For every row column c’ before c, supposing the piece is on row r’, mark the rows r’, r’ – (c – c’) and r’ + (c – c’) as invalid.

That’s it. For another speed boost, I use bitsets instead of vectors. Anyway, here’s the code in C (checker.c):

#include <stdio.h>
#include <string.h>

int q[14];

int sol[3][14];

int r = 0,
	d1 = 0,
	d2 = 0;

int solP = 0;

int n;

void gen_sol(int col) {
	if (col == n) {
		if (solP < 3)
			memcpy(sol&#91;solP&#93;, q, sizeof(int) * n);
		++solP;
		return;
	}

//NOTE Just calculating the non-admisible rows for this col every time is slightly faster than the "keep track of used rows and diagonals" solution
// 	int oc = 0;
// 	for (int i(0); i < col; ++i) {
// 		oc |= 1<<q&#91;i&#93;;
// 		oc |= 1<<(q&#91;i&#93; - (col - i));
// 		oc |= 1<<(q&#91;i&#93; + (col - i));
// 	}


	int i;
	for (i = 0; i < n; ++i) {
		if (!(r & 1<<i) && !(d1 & 1<<(n - col - 1 + i)) && !(d2 & 1<<(i + col))) {
			r |= 1<<i;
			d1 |= 1<<(n - col - 1 + i);
			d2 |= 1<<(i + col);
			
			q&#91;col&#93; = i;
			gen_sol(col + 1);

			r ^= 1<<i;
			d1 ^= 1<<(n - col - 1 + i);
			d2 ^= 1<<(i + col);
		}
	}
}

int main(int argc, char *argv&#91;&#93;) {
	n = 6;

	// Every solution's reflection is also a valid solution, so for the first
	// calculate only the first n/2 arrangements.
	int max = n;
	if (6 != n) {
		max = (n + 1) / 2;
	}
	
	// This complication appears because the odd values of n. Think about
	// it for a while and it will become obvious.
	int temp;
	int i;
	for (i = 0; i < max; ++i) {
		temp = solP;

		r |= 1<<i;
		d1 |= 1<<(n - 1 + i);
		d2 |= 1<<(i);

		q&#91;0&#93; = i;
		gen_sol(1);

		r ^= 1<<i;
		d1 ^= 1<<(n - 1 + i);
		d2 ^= 1<<(i);
	}

	int j;
	for (i = 0; i < 3; ++i) {
		for (j = 0; j < n; ++j)
			printf("%d ", sol&#91;i&#93;&#91;j&#93; + 1);
		printf("\n");
	}

	if ((n % 2 == 0) && (6 < n))
		solP *= 2;
	else if ((n % 2 == 1) && (n > 6))
		solP += temp;
	printf("%d\n", solP);

	return 0;
}

There are a few other optimisations littered throughout the code, but they’re not hard to understand. Good luck. Always open to comments.

P.S. This also is also called “The Queens Problem” or the like.