It performs the following steps:

1. Find the cell with the fewest number of possible digits.
   1. If there are no possibilities for any cell, we must be done.
2. Choose one of the possible digits for this cell.
3. Check if this creates a paradox (unchosen cell but no possibilities).
   1. If it's a paradox, return with an error.
   2. If no paradox, continue at step 1.

In the program, the solve_matrix function is the core routine. In it, the a[9][9] array contains the original matrix as passed to it. The h (hold) array is used to make the requested selection (passed to the function as row, column, and digit).

The p array contains bit-mapped "possibility" flags for each digit 1 through 9, set via the figure_possibles function.

Let me know if further details are needed.

// SOLVE.C
// Solve a Sudoku puzzle
// Last revised 7 October 2006

#include <stdio.h>
#include <stdlib.h>



#define E_OK			0
#define E_BAD_ROW		1
#define E_BAD_COLUMN		2
#define E_ALREADY_SET		3
#define E_DONE			4
#define E_LACKING_POSSIBILITIES	5



int	test_zero[9][9] = {	9, 0, 0, 0, 0, 0, 0, 0, 0,
				0, 0, 0, 0, 0, 0, 0, 0, 0,
				0, 0, 0, 0, 0, 0, 0, 0, 0,
				0, 0, 0, 0, 0, 0, 0, 0, 0,
				0, 0, 0, 0, 0, 0, 0, 0, 0,
				0, 0, 0, 0, 0, 0, 0, 0, 0,
				0, 0, 0, 0, 0, 0, 0, 0, 0,
				0, 0, 0, 0, 0, 0, 0, 0, 0 };

int	test_one[9][9] = {	4, 0, 0, 0, 6, 0, 0, 0, 9,
				0 ,0, 8, 7, 0, 5, 4, 0, 0,
				0, 1, 0, 0, 0, 0, 0, 8, 0,
				0, 7, 0, 0, 0, 0, 0, 4, 0,
				2, 0, 0, 0, 8, 0, 0, 0, 1,
				0, 8, 0, 0, 0, 0, 0, 3, 0,
				0, 3, 0, 0, 0, 0, 0, 1, 0,
				5, 0, 0, 0, 4, 0, 0, 0, 2 };

int	test_two[9][9] = { 	3, 0, 0, 0, 5, 0, 0, 0, 2,
				0, 0, 5, 3, 0, 6, 7, 0, 0,
				0, 8, 0, 0, 0, 0, 0, 3, 0,
				0, 3, 0, 0, 0, 0, 0, 8, 0,
				5, 0, 0, 0, 4, 0, 0, 0, 6,
				0, 7, 0, 0, 0, 0, 0, 9, 0,
				0, 9, 0, 0, 0, 0, 0, 2, 0,
				0, 0, 3, 4, 0, 7, 9, 0, 0,
				1, 0, 0, 0, 2, 0, 0, 0, 4 };


int	w[9][9];



void	zero_matrix( int a[9][9] )
{
	int	row, column;


	for ( row = 0; row < 9; row++ )
		for ( column = 0; column < 9; column++ )
			a[row][column] = 0;
}


void	set_possible( int p[9][9], int row, int column, int digit )
{
	int	mask;


	mask = 1 << ( digit - 1 );

	p[row][column] |= mask;
}


void	set_impossible( int p[9][9], int row, int column, int digit )
{
	int	mask;


	mask = 1 << ( digit - 1 );

	p[row][column] &= ~mask;
}


int	is_possible( int p[9][9], int row, int column, int digit )
{
	int	mask;


	mask = 1 << ( digit - 1 );

	if ( p[row][column] & mask )
		return( 1 );

	return ( 0 );
}



int	count_possible( int p[9][9], int row, int column )
{
	int	mask;
	int	count;


	count = 0;
	mask = 1 << 8;

	while( mask )
	{
		if ( mask & p[row][column] )
			count++;

		mask >>= 1;
	}

	return( count );
}



void	figure_possibles( int a[9][9], int p[9][9] )
{
	int	row, column;
	int	digit;
	int	i;
	int	box_row, box_column;
	int	box_row_start, box_column_start;


	for ( row = 0; row < 9; row++ )
		for ( column = 0; column < 9; column++ )
		{
			p[row][column] = 0;
			for ( digit = 1; digit <= 9; digit++ )
				set_possible( p, row, column, digit );
		}


	for ( row = 0; row < 9; row++ )
		for ( column = 0; column < 9; column++ )
		{
			digit = a[row][column];

			if ( 0 == digit )
				continue;

			for ( i = 1; i <= 9; i++ )
				set_impossible( p, row, column, i );

			for ( i = 0; i < 9; i++ )
				set_impossible( p, row, i, digit );

			for ( i = 0; i < 9; i++ )
				set_impossible( p, i, column, digit );

			box_row_start = (int)( row / 3 ) * 3;
			box_column_start = (int)( column / 3 ) * 3;

			for ( box_row = box_row_start; box_row < box_row_start + 3; box_row++ )
				for ( box_column = box_column_start; box_column < box_column_start + 3; box_column++ )
					set_impossible( p, box_row, box_column, digit );
		}
}


void	show_matrix( int a[9][9] )
{
	int	row, column;
	int	p[9][9];


	figure_possibles( a, p );

	for ( row = 0; row < 9; row++ )
	{
		for ( column = 0; column < 9; column++ )
			if ( a[row][column] )
				printf( " %d", a[row][column] );
			else
				printf( " _" );

		printf( "     " );

		for ( column = 0; column < 9; column++ )
			printf( " %03X", p[row][column] );

		printf( "     " );

		for ( column = 0; column < 9; column++ )
			printf( " %d", count_possible( p, row, column ));

		printf( "\n" );
	}

	printf( "\n" );
}




int	set_cell( int a[9][9], int row, int column, int digit )
{
	int	i;
	int	box_row, box_column;
	int	box_row_start, box_column_start;


	if (( row < 0 ) || ( row > 8 ))
		return( E_BAD_ROW );

	if (( column < 0 ) || ( column > 8 ))
		return( E_BAD_COLUMN );

	for ( i = 0; i < 9; i++ )
		if ( digit == a[row][i] )
			return( E_ALREADY_SET );

	for ( i = 0; i < 9; i++ )
		if ( digit == a[i][column] )
			return( E_ALREADY_SET );

	box_row_start = (int)( row / 3 ) * 3;
	box_column_start = (int)( column / 3 ) * 3;

	for ( box_row = box_row_start; box_row < box_row_start + 3; box_row++ )
		for ( box_column = box_column_start; box_column < box_column_start + 3; box_column++ )
			if ( digit == a[box_row][box_column] )
				return( E_ALREADY_SET );


	a[row][column] = digit;

	return( E_OK );
}



int	load_matrix( int a[9][9], int m[9][9] )
{
	int	row, column;
	int	result;


	zero_matrix( a );

	for ( row = 0; row < 9; row++ )
		for ( column = 0; column < 9; column++ )
			if ( m[row][column] )
			{
				result = set_cell( a, row, column, m[row][column] );
				if ( E_OK != result )
				{
					printf( "Set Cell( %d, %d, %d ) returned error %d.\n",
					row, column, m[row][column], result );

					return( result );
				}
			}

	return( E_OK );
}



int	find_lowest( int p[9][9], int *low_row, int *low_column )
{
	int	row, column;
	int	count;
	int	lowest_possible;


	lowest_possible = 10;
	for ( row = 0; row < 9; row++ )
		for ( column = 0; column < 9; column++ )
		{
			count = count_possible( p, row, column );
			if (( count ) && ( count < lowest_possible ))
			{
				lowest_possible = count;
				*low_row = row;
				*low_column = column;
			}
		}

	if ( lowest_possible > 9 )
		lowest_possible = 0;

	return( lowest_possible );
}


int	solve_matrix( int depth, int a[9][9], int set_row, int set_column, int set_digit )
{
	int	row, column;
	int	count;
	int	digit;
	int	turn_number;
	int	i;
	int	result;
	int	h[9][9];
	int	p[9][9];


	for ( row = 0; row < 9; row++ )
		for ( column = 0; column < 9; column++ )
			h[row][column] = a[row][column];

	if ( set_digit )
	{
		result = set_cell( h, set_row, set_column, set_digit );
		if ( E_OK != result )
			return( result );
	}

	printf( "Call to Solve_Matrix at depth %d with request to set (%d,%d) to %d:\n",
		depth, set_row, set_column, set_digit );
	show_matrix( h );


	figure_possibles( h, p );

	for ( row = 0; row < 9; row++ )
		for ( column = 0; column < 9; column++ )
			if (( 0 == h[row][column] ) && ( 0 == count_possible( p, row, column )))
				return( E_LACKING_POSSIBILITIES );

	count = find_lowest( p, &row, &column );

	if ( count < 1 )
	{
		for ( row = 0; row < 9; row++ )
			for ( column = 0; column < 9; column++ )
				w[row][column] = h[row][column];

		return( E_DONE );
	}

	printf( "Lowest is %d possibilit%s at (%d,%d).\n",
		count, ( count == 1 ) ? "y" : "ies", row, column );

	for ( digit = 1; digit <= 9; digit++ )
		if ( is_possible( p, row, column, digit ))
		{
			result = solve_matrix( depth + 1, h, row, column, digit );

			if ( E_DONE == result )
				break;
		}

	return( result );
}



int	do_test( int m[9][9] )
{
	int	result;
	int	a[9][9];


	load_matrix( a, m );

	printf( "MATRIX LOADED:\n" );
	show_matrix( a );


	result = solve_matrix( 0, a, 0, 0, 0 );

	if ( E_DONE == result )
		printf( "SOLVED:\n" );
	else
		printf( "ERROR %d:\n", result );

	show_matrix( w );

	return( result );
}


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


	result = do_test( test_zero );
	result = do_test( test_one );
	result = do_test( test_two );

	return( 0 );
}

The program produces a trace of each step, which can result in a rather lengthy output. Here's an edited example:

MATRIX LOADED:
 4 _ _ _ 6 _ _ _ 9      000 012 056 087 000 087 057 052 000      0 2 4 4 0 4 5 3 0
 _ _ 8 7 _ 5 4 _ _      124 122 000 000 107 000 000 022 024      3 3 0 0 4 0 0 2 2
 _ 1 _ _ _ _ _ 8 _      164 000 176 10E 106 10E 076 000 074      4 0 6 4 3 4 5 0 4
 _ 7 _ _ _ _ _ 4 _      125 000 135 137 117 127 1B2 000 0B0      4 0 5 6 5 5 5 0 3
 2 _ _ _ 8 _ _ _ 1      000 138 13C 13C 000 16C 170 170 000      0 4 5 5 0 5 4 4 0
 _ 8 _ _ _ _ _ 3 _      121 000 139 13B 153 16B 172 000 070      3 0 5 6 5 6 5 0 3
 _ 3 _ _ _ _ _ 1 _      1E0 000 16A 1B2 152 1E2 1F0 000 0F8      4 0 5 5 4 5 5 0 5
 5 _ _ _ 4 _ _ _ 2      000 120 161 1A5 000 1E5 1E4 160 000      0 2 4 5 0 6 5 3 0
 _ _ _ _ _ _ _ _ _      1E1 12A 16B 1B7 157 1E7 1F4 170 0FC      5 4 6 7 6 7 6 4 6

[...]

SOLVED:
 4 2 7 3 6 8 1 5 9      000 000 000 000 000 000 000 000 000      0 0 0 0 0 0 0 0 0
 9 6 8 7 1 5 4 2 3      000 000 000 000 000 000 000 000 000      0 0 0 0 0 0 0 0 0
 3 1 5 4 2 9 6 8 7      000 000 000 000 000 000 000 000 000      0 0 0 0 0 0 0 0 0
 1 7 3 6 5 2 9 4 8      000 000 000 000 000 000 000 000 000      0 0 0 0 0 0 0 0 0
 2 5 4 9 8 3 7 6 1      000 000 000 000 000 000 000 000 000      0 0 0 0 0 0 0 0 0
 6 8 9 1 7 4 2 3 5      000 000 000 000 000 000 000 000 000      0 0 0 0 0 0 0 0 0
 7 3 2 5 9 6 8 1 4      000 000 000 000 000 000 000 000 000      0 0 0 0 0 0 0 0 0
 5 9 6 8 4 1 3 7 2      000 000 000 000 000 000 000 000 000      0 0 0 0 0 0 0 0 0
 8 4 1 2 3 7 5 9 6      000 000 000 000 000 000 000 000 000      0 0 0 0 0 0 0 0 0