In this article, I describe the greedy algorithm for solving the Fractional Knapsack Problem and give an implementation in C.

The Problem

The Fractional Knapsack Problem usually sounds like this:

Ted Thief has just broken into the Fort Knox! He sees himself in a room with n piles of gold dust. Because the each pile has a different purity, each pile also has a different value (v[i]) and a different weight (c[i]). Ted has a knapsack that can only hold W kilograms.

Given n, v, c and W, calculate which piles Ted should completely put into his knapsack and which he should put only a fraction of.

So, for this input:
n = 5
c = {12, 1, 2, 1, 4}
v = {4, 2, 2, 1, 10}
W = 15

Ted should take piles 2, 3, 4 and 5 completely and about 58% of pile 1.

You’re usually dealling with a knapsack problem when you’re give the cost and the benefits of certain objects and asked to obtain the maximum benefit so that the sum of the costs is smaller than a given value. You’ve got the fractional knapsack problem when you can take fractions (as opposed to all or nothing) of the objects.

The Algorithm

This is a standard greedy algorithm. In fact, it’s one of the classic examples.

The idea is to calculate for each object the ratio of value/cost, and sort them according to this ratio. Then you take the objects with the highest ratios and add them until you can’t add the next object as whole. Finally add as much as you can of the next object.

So, for our example:
v = {4, 2, 2, 1, 10}
c = {12, 1, 2, 1, 4}
r = {1/3, 2, 1, 1, 5/2}

From this it’s obvious that you should add the objects: 5, 2, 3, 4 and then as much as possible of 1.
The output of my programme is this:
Added object 5 (10$, 4Kg) completly in the bag. Space left: 11.
Added object 2 (2$, 1Kg) completly in the bag. Space left: 10.
Added object 3 (2$, 2Kg) completly in the bag. Space left: 8.
Added object 4 (1$, 1Kg) completly in the bag. Space left: 7.
Added 58% (4$, 12Kg) of object 1 in the bag.
Filled the bag with objects worth 15.48$.

The Programme

Now, you could implement the algorithm as stated, but for practical reasons you may wish to trade speed for simplicity. That’s what I’ve done here: instead of sorting the objects, I simply go through them every time searching for the best ratio. This modification turns an O(n*lg(n)) algorithm into an O(n2) one. For small values of n, this doesn’t matter and n is usually small.

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

#include <stdio.h>

int n = 5; /* The number of objects */
int c[10] = {12, 1, 2, 1, 4}; /* c[i] is the *COST* of the ith object; i.e. what
				YOU PAY to take the object */
int v[10] = {4, 2, 2, 1, 10}; /* v[i] is the *VALUE* of the ith object; i.e.
				what YOU GET for taking the object */
int W = 15; /* The maximum weight you can take */

void simple_fill() {
	int cur_w;
	float tot_v;
	int i, maxi;
	int used[10];

	for (i = 0; i < n; ++i)
		used&#91;i&#93; = 0; /* I have not used the ith object yet */

	cur_w = W;
	while (cur_w > 0) { /* while there's still room*/
		/* Find the best object */
		maxi = -1;
		for (i = 0; i < n; ++i)
			if ((used&#91;i&#93; == 0) &&
				((maxi == -1) || ((float)v&#91;i&#93;/c&#91;i&#93; > (float)v[maxi]/c[maxi])))
				maxi = i;

		used[maxi] = 1; /* mark the maxi-th object as used */
		cur_w -= c[maxi]; /* with the object in the bag, I can carry less */
		tot_v += v[maxi];
		if (cur_w >= 0)
			printf("Added object %d (%d$, %dKg) completly in the bag. Space left: %d.\n", maxi + 1, v[maxi], c[maxi], cur_w);
		else {
			printf("Added %d%% (%d$, %dKg) of object %d in the bag.\n", (int)((1 + (float)cur_w/c[maxi]) * 100), v[maxi], c[maxi], maxi + 1);
			tot_v -= v[maxi];
			tot_v += (1 + (float)cur_w/c[maxi]) * v[maxi];
		}
	}

	printf("Filled the bag with objects worth %.2f$.\n", tot_v);
}

int main(int argc, char *argv[]) {
	simple_fill();

	return 0;
}

That’s it. Good luck.

Always open to comments.

Update: The next article in this series is The 0-1 Knapsack Problem.

Advertisements

In this article I describe the Floyd-Warshall algorithm for finding the shortest path between all nodes in a graph. I give an informal proof and provide an implementation in C.

Shortest paths

The shortest path between two nodes of a graph is a sequence of connected nodes so that the sum of the edges that inter-connect them is minimal.

Take this graph,
p2.png

There are several paths between A and E:
Path 1: A -> B -> E 20
Path 2: A -> D -> E 25
Path 3: A -> B -> D -> E 35
Path 4: A -> D -> B -> E 20

There are several things to notice here:

  1. There can be more then one route between two nodes
  2. The number of nodes in the route isn’t important (Path 4 has 4 nodes but is shorter than Path 2, which has 3 nodes)
  3. There can be more than one path of minimal length

Something else that should be obvious from the graph is that any path worth considering is simple. That is, you only go through each node once.

Unfortunately, this is not always the case. The problem appears when you allow negative weight edges. This isn’t by itself bad. But if a loop of negative weight appears, then there is no shortest path. Look at this example:
A graph containing a negative weight loop

Look at the path B -> E -> D -> B. This is a loop, because the starting node is the also the end. What’s the cost? It’s 10 – 20 + 5 = -5. This means that adding this loop to a path once lowers the cost of the path by 5. Adding it twice would lower the cost by 2 * 5 = 10. So, whatever shortest path you may have come up with, you can make it smaller by going through the loop one more time. BTW there’s no problem with a negative cost path.

The Floyd-Warshall Algorithm

This algorithm calculates the length of the shortest path between all nodes of a graph in O(V3) time. Note that it doesn’t actually find the paths, only their lengths.

Let’s say you have the adjacency matrix of a graph. Assuming no loop of negative values, at this point you have the minimum distance between any two nodes which are connected by an edge.
A B C D E
A 0 10 0 5 0
B 10 0 5 5 10
C 0 5 0 0 0
D 5 5 0 0 20
E 0 10 0 20 0

The graph is the one shown above (the first one).

The idea is to try to interspace A between any two nodes in hopes of finding a shorter path.
A B C D E
A 0 10 0 5 0
B 10 0 5 5 10
C 0 5 0 0 0
D 5 5 0 0 20
E 0 10 0 20 0

Then try to interspace B between any two nodes:
A B C D E
A 0 10 15 5 20
B 10 0 5 5 10
C 15 5 0 10 15
D 5 5 10 0 15
E 20 10 15 15 0

Do the same for C:
A B C D E
A 0 10 15 5 20
B 10 0 5 5 10
C 15 5 0 10 15
D 5 5 10 0 15
E 20 10 15 15 0

Do the same for D:
A B C D E
A 0 10 15 5 20
B 10 0 5 5 10
C 15 5 0 10 15
D 5 5 10 0 15
E 20 10 15 15 0

And for E:
A B C D E
A 0 10 15 5 20
B 10 0 5 5 10
C 15 5 0 10 15
D 5 5 10 0 15
E 20 10 15 15 0

This is the actual algorithm:

# dist(i,j) is "best" distance so far from vertex i to vertex j 

# Start with all single edge paths.
 For i = 1 to n do
     For j = 1 to n do
         dist(i,j) = weight(i,j) 

 For k = 1 to n do # k is the `intermediate' vertex
     For i = 1 to n do
         For j = 1 to n do
             if (dist(i,k) + dist(k,j) < dist(i,j)) then # shorter path?
                 dist(i,j) = dist(i,k) + dist(k,j)

The Programme

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

#include

int n; /* Then number of nodes */
int dist[16][16]; /* dist[i][j] is the length of the edge between i and j if
it exists, or 0 if it does not */

void printDist() {
int i, j;
printf(” “);
for (i = 0; i < n; ++i) printf("%4c", 'A' + i); printf("\n"); for (i = 0; i < n; ++i) { printf("%4c", 'A' + i); for (j = 0; j < n; ++j) printf("%4d", dist[i][j]); printf("\n"); } printf("\n"); } /* floyd_warshall() after calling this function dist[i][j] will the the minimum distance between i and j if it exists (i.e. if there's a path between i and j) or 0, otherwise */ void floyd_warshall() { int i, j, k; for (k = 0; k < n; ++k) { printDist(); for (i = 0; i < n; ++i) for (j = 0; j < n; ++j) /* If i and j are different nodes and if the paths between i and k and between k and j exist, do */ if ((dist[i][k] * dist[k][j] != 0) && (i != j)) /* See if you can't get a shorter path between i and j by interspacing k somewhere along the current path */ if ((dist[i][k] + dist[k][j] < dist[i][j]) || (dist[i][j] == 0)) dist[i][j] = dist[i][k] + dist[k][j]; } printDist(); } int main(int argc, char *argv[]) { FILE *fin = fopen("dist.txt", "r"); fscanf(fin, "%d", &n); int i, j; for (i = 0; i < n; ++i) for (j = 0; j < n; ++j) fscanf(fin, "%d", &dist[i][j]); fclose(fin); floyd_warshall(); return 0; } [/sourcecode] Note that of the above programme, all the work is done by only five lines (30-48). That's it. Good luck. 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.

In a previous article, I described the basics of binary arithmetic and gave a function to display the binary representation of a number. Here, we’ll look at several ways to count the set (1) bits in a number.

First of all, why would you want to count bits? Bitsets. If you use bitsets as a fast set implementation, you might want to find out how many elements there are in the set. I used this in a sudoku programme to memorise which digits can’t be placed in a particular cell. Bit counting functions are also used extensively in graphics (bitmap manipulations).

Here’s 22 in binary:
00010110

From the binary representation, it’s obvious that there are 3 set bits and 5 unset bits. How do you count them? I’ll give three methods.

Classic, let’s iterate through every bit, solution

The idea behind this is simple: take every bit in the number (n) and check if it’s 1. To do this, you can simply use a variable (i):

  1. initialise i with 1
  2. check if n AND i is greater than zero and if so, increment a counter
  3. multiply i by 2
  4. if i < n, go to 2

Here’s the code:

/* Count the ON bits in n using an iterative algorithm */
int bitcount(int n) {
	int tot = 0;

	int i;
	for (i = 1; i <= n; i = i<<1)
		if (n & i)
			++tot;

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

This isn't bad and works in <strong>O(lg(n))</strong> time, but if you know (you probably will) if the number is made up mostly of ones or zeros, use one of the following algorithms.

<h5>Sparse ones algorithm</h5>
This solution relies on the following observation:
<code>22<sub>10</sub> = 00010110<sub>2</sub>
22 - 1 = 21<sub>10</sub> = 00010101<sub>2</sub>
22 AND 21 = 00010100
</code>

Notice what happened: by logically ANDing <em>22</em> and <em>21</em>, you get a number whose binary representation is the same as <em>22</em> but with the last <em>1</em> flipped to <em>0</em>.

The idea behind this algorithm is to logically AND <em>n</em> and <em>n - 1</em> until <em>n</em> is <em>0</em>. The number of times necessary to do this will the the number of <em>1</em> bits.

Here's the code:

/* Counts the ON bits in n. Use this if you know n is mostly 0s */
int bitcount_sparse_ones(int n) {
	int tot = 0;

	while (n) {
		++tot;
		n &= n - 1;
	}

	return tot;
}

Why call it sparse ones? Look at the algorithm, and apply it to a few numbers on a piece of paper. You’ll notice that you go through the inner loop the x times, where x is the number of 1s in the number. So the time is O(x), and it’s best to use it if there are few ones in the number.

Dense ones algorithm

But what if your number is mostly 1? The solution is obvious: flip every bit in n, then apply the sparse ones algorithm:

/* Counts the ON bits in n. Use this if you know n is mostly 1s */
int bitcount_dense_ones(int n) {
	int tot = 0;

	n ^= (unsigned int)-1;

	while (n) {
		++tot;
		n &= n - 1;
	}

	return sizeof(int) * 8 - tot;
}
Full source

Here’s the full C source to the programme (bit.c):
NOTE: Source is mangled by WordPress. Don’t copy-paste; download the file.

#include

/* Print n as a binary number */
void printbits(int n) {
unsigned int i, step;

if (0 == n) { /* For simplicity’s sake, I treat 0 as a special case*/
printf(“0000”);
return;
}

i = 1<>= 4; /* In groups of 4 */
while (step >= n) {
i >>= 4;
step >>= 4;
}

/* At this point, i is the smallest power of two larger or equal to n */
while (i > 0) {
if (n & i)
printf(“1”);
else
printf(“0”);
i >>= 1;
}
}

/* Count the ON bits in n using an iterative algorithm */
int bitcount(int n) {
int tot = 0;

int i;
for (i = 1; i <= n; i = i<<1) if (n & i) ++tot; return tot; } /* Counts the ON bits in n. Use this if you know n is mostly 0s */ int bitcount_sparse_ones(int n) { int tot = 0; while (n) { ++tot; n &= n - 1; } return tot; } /* Counts the ON bits in n. Use this if you know n is mostly 1s */ int bitcount_dense_ones(int n) { int tot = 0; n ^= (unsigned int)-1; while (n) { ++tot; n &= n - 1; } return sizeof(int) * 8 - tot; } int main(int argc, char *argv[]) { int i; for (i = 0; i < 23; ++i) { printf("%d = ", i); printbits(i); printf("\tON bits: %d %d %d", bitcount(i), bitcount_sparse_ones(i), bitcount_dense_ones(i)); printf("\n"); } return 0; } [/sourcecode] That's it. If you're intrested in a few more (slightly esoteric) algorithms, see this article.

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.

In this article I’ll begin by defining binary numbers and describe the basic operations. Afterwords, I’ll show you several of the most common uses of binary numbers.

Humans work with digits in base 10, and we’re quite good at it. Computers, on the other hand, use base 2 and it shouldn’t come as a surprise that they’re extremely good at it. Today’s high level languages do a lot to hide this fact from us, but, still, a fairly good grasp of binary numbers is essential to working with computers, especially programming them.

Binary numbers

Mathworld defines binary as:

The base 2 method of counting in which only the digits 0 and 1 are used.

Basically, the binary representation of a number is the way of writing that number, uniquely, using only the digits 0 and 1. These are the binary representations of the first 16 natural numbers:
0 = 0000
1 = 0001
2 = 0010
3 = 0011
4 = 0100
5 = 0101
6 = 0110
7 = 0111
8 = 1000
9 = 1001
10 = 1010
11 = 1011
12 = 1100
13 = 1101
14 = 1110
15 = 1111

Given a number in base 10, how do you find the representation in base 2? You take the number and divide it repeatedly by 2 taking note of the remainder. After you’ve reached 0, write the remainders in reverse order. That’s the binary number! Here’s an example for 13:
Converting_13_to_binary

So,
13_in_binary

Now, how do you get a decimal form a binary? This is even easier. Take the number in binary form and start from the right side. Multiply the first digit (from the right side) with 20. Multiply the second digit with 21 and add it to the result from the first multiplication. Multiply the third digit with 22 and add it to what you have so far. … Do this for all the digits and you’ll get the decimal representation of the binary number.
13_binary_to_decimal

Logical operations

All of the following operations work in the same way. Take every bit form the first number and the corresponding bit from the second number (if it exists) and compute the resulting bit using the operation’s truth table.

NOT

NOT truth table

So, take each bit and reverse it.
0000 becomes 1111
0101 becomes 1010
1111 becomes 0000

It’s worthwhile to note that applying NOT twice, you get the original number unaltered.

AND

AND truth table

So, if both digits are 1 then the result is 1, otherwise it is 0.

OR

OR truth table

So, if either digit is 1, then the result is 1, otherwise it is 0.

XOR (eXclusive OR)

XOR truth table

So, if one of the digits it 1, but not both, then the result is 1, otherwise, the result is 0.

SHL (SHift Left) and SHR (SHift Right)

These aren’t like the other operations in that they don’t rely on truth tables. To apply them, simply drop the left-most (right-most) digit and add a 0 digit to the right (left).
After successive SHL operations,
0011 becomes 0110,
0110 becomes 1100,
1100 becomes 1000,
1000 becomes 0000

After successive SHR operations,
1100 becomes 0110,
0110 becomes 0011,
0011 becomes 0001,
0001 becomes 0000

Common use: Fast multiplication/division by 2

To quickly multiply an integer by 2, simply shift left the number.

To quickly divide an integer by 2, simply shift right the number.

In C, this would be:
a = a <> 1; /* Divide by 2 */
a = a >> 1; /* Multiply by 2*/

Setting/Checking a certain bit

To check whether the (n + 1)th bit is set (1) or not (0), use this:
a & 1<<n = 0 if the bit is NOT set
a & 1< 0 if the bit is set

To set the (n + 1)th bit, use this:
a = a | 1<<n;

What am I doing here? In both cases I first compute 1<<n. This is a binary number in which all digits are 0 but the nth digit is 1. Then, to check, I logically AND the two numbers. If the bit is set, then the result should be anything but 0. On the other hand, to set the bit, I logically OR the two numbers. If the bit was set, than this will have no effect. But if the bit was not set, it will be at the end.

Common use: bitsets

Chances are, at one time or another, you’ve had to use an array of boolean values. You’ve probably used something like this:
char foo[100];
foo[42] = 0; /* Equivalent of false */
foo[42] = 1; /* Equivalent of true*/

OR

bool bar[100];
bar[23] = false;
bar[23] = true;

This isn’t bad. Actually, in most cases it’s quite good. But if the number of elements is relatively small (less than 64), there’s a better way, that is using bitsets.

Instead of an array use an int, then use the methods described above to set and check the bits.
int a;
a = 0; /* The entire ``array" is set to false */
a |= 1<<3; /* The fourth bit is set */
if (a & 1<<3) /* Is the fourth bit set? */
a ^= 1<<3; /* If it is, flip it. */

Flipping bits

To flip a bit, XOR it by 1.
a ^= 1<<5; /* Flip the sixth bit */

Putting it all together: Printing a binary number

This small C programme prints out the binary representation of 0, 1, …, 16. (bit.c)

#include

/* Print n as a binary number */
void printbitssimple(int n) {
unsigned int i;
i = 1<<(sizeof(n) * 8 - 1); while (i > 0) {
if (n & i)
printf(“1”);
else
printf(“0”);
i >>= 1;
}
}

/* Print n as a binary number */
void printbits(int n) {
unsigned int i, step;

if (0 == n) { /* For simplicity’s sake, I treat 0 as a special case*/
printf(“0000”);
return;
}

i = 1<<(sizeof(n) * 8 - 1); step = -1; /* Only print the relevant digits */ step >>= 4; /* In groups of 4 */
while (step >= n) {
i >>= 4;
step >>= 4;
}

/* At this point, i is the smallest power of two larger or equal to n */
while (i > 0) {
if (n & i)
printf(“1”);
else
printf(“0”);
i >>= 1;
}
}

int main(int argc, char *argv[]) {
int i;
for (i = 0; i < 16; ++i) { printf("%d = ", i); printbits(i); printf("\n"); } return 0; } [/sourcecode] Code should be fairly easy to understand. Good luck. Always open to comments. Update: The next article in this series is Counting Bits.

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.