EmilHernvall/sudoku.c

## sudoku.c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct grid_t_ {
	unsigned int grid[81];
	struct grid_t_ *next;
} grid_t;

typedef struct sub_t_ {
	int row;
	int col;
	int v[10];
} sub_t;

int load_grids(grid_t **result, const char *path)
{
	FILE *fh;
	char buffer[1024];
	grid_t *current = NULL, *next = NULL;
	int gridcount = 0, line = 0, pos = 0, i = 0;

	fh = fopen(path, "r");
	if (!fh) {
		return -1;
	}

	while (fgets(buffer, sizeof(buffer), fh) != NULL) {
		line++;

		if (strncmp(buffer, "Grid", 4) == 0) {
			next = current;
			current = (grid_t*)malloc(sizeof(grid_t));
			current->next = next;

			pos = 0;
			gridcount++;

			continue;
		}

		if (strlen(buffer) != 11) {
			fprintf(stderr, "invalid line of length %d\n", (unsigned int)strlen(buffer));
			continue;
		}

		for (i = 0; i < 9; i++, pos++) {
			if (pos >= 81) {
				fprintf(stderr, "invalid grid format at line %d\n", line);
				return -1;
			}
			current->grid[pos] = buffer[i] - '0';
		}
	}

	fclose(fh);

	*result = current;
	return gridcount;
}

void print_grid(grid_t *grid)
{
	int i, j, sum;
	for (i = 0; i < 9; i++) {
		sum = 0;
		for (j = 0; j < 9; j++) {
			printf("%d ", grid->grid[9*i+j]);
			sum += grid->grid[9*i+j];
		}
		printf("- %d\n", sum);
	}
}

int solve_grid(grid_t *grid, int level)
{
	grid_t g; // local copy
	int i, j, k, m; // counters
	sub_t currentsub;
	int solved = 0;
	int unsolved = 0; // number of unsolved slots
	int lastpass = 0, subs = 0;

	// copy the passed grid to avoid propagating incorrect
	// solutions upwards
	memcpy(&g, grid, sizeof(grid_t));

	// make all simple substitutions
	for (;;) {
		subs = 0;
		unsolved = 0;

		// iterate over all rows
		for (i = 0; i < 9; i++) {
			// iterate over all columns
			for (j = 0; j < 9; j++) {
				int box, sol, solcount;
				int v[10] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };

				// skip slots that already have an assigned value
				if (g.grid[9*i+j] != 0) {
					continue;
				}

				// increment number of unsolved slots
				unsolved++;

				// eliminate all values occupied by other slots on this row
				for (k = 0; k < 9; k++) {
					v[g.grid[9*i+k]] = 0;
				}

				// eliminate values occupied by other slots in the same column
				for (k = 0; k < 9; k++) {
					v[g.grid[9*k+j]] = 0;
				}

				// finally, eliminate all slots occupied by values in the same 3x3 box
				box = 3*(i/3) + j/3;
				for (k = 3*(box/3); k < 3*(box/3)+3; k++) {
					for (m = 3*(box%3); m < 3*(box%3)+3; m++) {
						v[g.grid[9*k+m]] = 0;
					}
				}

				// count the number of possible values for this slot
				solcount = 0;
				sol = 0;
				for (k = 0; k < 10; k++) {
					if (v[k] != 0) {
						sol = v[k];
						solcount++;
					}
				}

				// if no possible values are found, there are no solutions
				if (solcount == 0) {
					return 0;
				}
				// if there is only one possible value, we substitute this value
				// into the grid
				else if (solcount == 1) {
					#ifdef DEBUG
						printf("unique substitution %d found at %d, %d\n", sol, i, j);
					#endif
					g.grid[i*9+j] = sol;
					subs++;
				}
				// otherwise just store a list of possible values until later
				// and try them until we find a solution.
				else {
					currentsub.row = i;
					currentsub.col = j;
					memcpy(&currentsub.v, v, sizeof(v));
				}
			}
		}

		// no possible substitutions remain, end loop
		if (subs == 0) {
			break;
		}
	}

	// permute solutions
	if (unsolved > 0) {
		for (i = 0; i < 10; i++) {
			if (currentsub.v[i] == 0) {
				continue;
			}

			g.grid[9*currentsub.row + currentsub.col] = currentsub.v[i];
			#ifdef DEBUG
				printf("%d: setting %d, %d to %d\n", level, currentsub.row, currentsub.col, currentsub.v[i]);
			#endif
			if (solve_grid(&g, level+1)) {
				solved = 1;
				break;
			}
		}
	} else {
		solved = 1;
	}


	if (!solved) {
		return 0;
	}

	// copy the final solution upwards the stack
	memcpy(grid, &g, sizeof(grid_t));

	return 1;
}

int main(int argc, char **argv)
{
	grid_t *grids, *current, *next;
	int gridcount;
	int i;

	if (argc != 2) {
		printf("usage: sudoku [gridfile]\n");
		return 0;
	}

	gridcount = load_grids(&grids, argv[1]);
	if (gridcount == -1) {
		fprintf(stderr, "failed to open grid file.\n");
		return 1;
	}

	i = 0;
	for (current = grids; current != NULL; ) {
		printf("grid %d\n", i);
		print_grid(current);
		printf("\n");

		if (solve_grid(current, 0)) {
			print_grid(current);
		} else {
			printf("solution not found!\n");
		}

		printf("\n");

		next = current->next;
		free(current);
		current = next;
		i++;
	}

	return 0;
}

## sudoku.txt
Grid 01
003020600
900305001
001806400
008102900
700000008
006708200
002609500
800203009
005010300
Grid 02
200080300
060070084
030500209
000105408
000000000
402706000
301007040
720040060
004010003
Grid 03
000000907
000420180
000705026
100904000
050000040
000507009
920108000
034059000
507000000
Grid 04
030050040
008010500
460000012
070502080
000603000
040109030
250000098
001020600
080060020
Grid 05
020810740
700003100
090002805
009040087
400208003
160030200
302700060
005600008
076051090
Grid 06
100920000
524010000
000000070
050008102
000000000
402700090
060000000
000030945
000071006
Grid 07
043080250
600000000
000001094
900004070
000608000
010200003
820500000
000000005
034090710
Grid 08
480006902
002008001
900370060
840010200
003704100
001060049
020085007
700900600
609200018
Grid 09
000900002
050123400
030000160
908000000
070000090
000000205
091000050
007439020
400007000
Grid 10
001900003
900700160
030005007
050000009
004302600
200000070
600100030
042007006
500006800
Grid 11
000125400
008400000
420800000
030000095
060902010
510000060
000003049
000007200
001298000
Grid 12
062340750
100005600
570000040
000094800
400000006
005830000
030000091
006400007
059083260
Grid 13
300000000
005009000
200504000
020000700
160000058
704310600
000890100
000067080
000005437
Grid 14
630000000
000500008
005674000
000020000
003401020
000000345
000007004
080300902
947100080
Grid 15
000020040
008035000
000070602
031046970
200000000
000501203
049000730
000000010
800004000
Grid 16
361025900
080960010
400000057
008000471
000603000
259000800
740000005
020018060
005470329
Grid 17
050807020
600010090
702540006
070020301
504000908
103080070
900076205
060090003
080103040
Grid 18
080005000
000003457
000070809
060400903
007010500
408007020
901020000
842300000
000100080
Grid 19
003502900
000040000
106000305
900251008
070408030
800763001
308000104
000020000
005104800
Grid 20
000000000
009805100
051907420
290401065
000000000
140508093
026709580
005103600
000000000
Grid 21
020030090
000907000
900208005
004806500
607000208
003102900
800605007
000309000
030020050
Grid 22
005000006
070009020
000500107
804150000
000803000
000092805
907006000
030400010
200000600
Grid 23
040000050
001943600
009000300
600050002
103000506
800020007
005000200
002436700
030000040
Grid 24
004000000
000030002
390700080
400009001
209801307
600200008
010008053
900040000
000000800
Grid 25
360020089
000361000
000000000
803000602
400603007
607000108
000000000
000418000
970030014
Grid 26
500400060
009000800
640020000
000001008
208000501
700500000
000090084
003000600
060003002
Grid 27
007256400
400000005
010030060
000508000
008060200
000107000
030070090
200000004
006312700
Grid 28
000000000
079050180
800000007
007306800
450708096
003502700
700000005
016030420
000000000
Grid 29
030000080
009000500
007509200
700105008
020090030
900402001
004207100
002000800
070000090
Grid 30
200170603
050000100
000006079
000040700
000801000
009050000
310400000
005000060
906037002
Grid 31
000000080
800701040
040020030
374000900
000030000
005000321
010060050
050802006
080000000
Grid 32
000000085
000210009
960080100
500800016
000000000
890006007
009070052
300054000
480000000
Grid 33
608070502
050608070
002000300
500090006
040302050
800050003
005000200
010704090
409060701
Grid 34
050010040
107000602
000905000
208030501
040070020
901080406
000401000
304000709
020060010
Grid 35
053000790
009753400
100000002
090080010
000907000
080030070
500000003
007641200
061000940
Grid 36
006080300
049070250
000405000
600317004
007000800
100826009
000702000
075040190
003090600
Grid 37
005080700
700204005
320000084
060105040
008000500
070803010
450000091
600508007
003010600
Grid 38
000900800
128006400
070800060
800430007
500000009
600079008
090004010
003600284
001007000
Grid 39
000080000
270000054
095000810
009806400
020403060
006905100
017000620
460000038
000090000
Grid 40
000602000
400050001
085010620
038206710
000000000
019407350
026040530
900020007
000809000
Grid 41
000900002
050123400
030000160
908000000
070000090
000000205
091000050
007439020
400007000
Grid 42
380000000
000400785
009020300
060090000
800302009
000040070
001070500
495006000
000000092
Grid 43
000158000
002060800
030000040
027030510
000000000
046080790
050000080
004070100
000325000
Grid 44
010500200
900001000
002008030
500030007
008000500
600080004
040100700
000700006
003004050
Grid 45
080000040
000469000
400000007
005904600
070608030
008502100
900000005
000781000
060000010
Grid 46
904200007
010000000
000706500
000800090
020904060
040002000
001607000
000000030
300005702
Grid 47
000700800
006000031
040002000
024070000
010030080
000060290
000800070
860000500
002006000
Grid 48
001007090
590080001
030000080
000005800
050060020
004100000
080000030
100020079
020700400
Grid 49
000003017
015009008
060000000
100007000
009000200
000500004
000000020
500600340
340200000
Grid 50
300200000
000107000
706030500
070009080
900020004
010800050
009040301
000702000
000008006
	#include <stdio.h>
	#include <stdlib.h>
	#include <string.h>

	typedef struct grid_t_ {
	unsigned int grid[81];
	struct grid_t_ *next;
	} grid_t;

	typedef struct sub_t_ {
	int row;
	int col;
	int v[10];
	} sub_t;

	int load_grids(grid_t *result, const char path)
	{
	FILE *fh;
	char buffer[1024];
	grid_t current = NULL, next = NULL;
	int gridcount = 0, line = 0, pos = 0, i = 0;

	fh = fopen(path, "r");
	if (!fh) {
	return -1;
	}

	while (fgets(buffer, sizeof(buffer), fh) != NULL) {
	line++;

	if (strncmp(buffer, "Grid", 4) == 0) {
	next = current;
	current = (grid_t*)malloc(sizeof(grid_t));
	current->next = next;

	pos = 0;
	gridcount++;

	continue;
	}

	if (strlen(buffer) != 11) {
	fprintf(stderr, "invalid line of length %d\n", (unsigned int)strlen(buffer));
	continue;
	}

	for (i = 0; i < 9; i++, pos++) {
	if (pos >= 81) {
	fprintf(stderr, "invalid grid format at line %d\n", line);
	return -1;
	}
	current->grid[pos] = buffer[i] - '0';
	}
	}

	fclose(fh);

	*result = current;
	return gridcount;
	}

	void print_grid(grid_t *grid)
	{
	int i, j, sum;
	for (i = 0; i < 9; i++) {
	sum = 0;
	for (j = 0; j < 9; j++) {
	printf("%d ", grid->grid[9*i+j]);
	sum += grid->grid[9*i+j];
	}
	printf("- %d\n", sum);
	}
	}

	int solve_grid(grid_t *grid, int level)
	{
	grid_t g; // local copy
	int i, j, k, m; // counters
	sub_t currentsub;
	int solved = 0;
	int unsolved = 0; // number of unsolved slots
	int lastpass = 0, subs = 0;

	// copy the passed grid to avoid propagating incorrect
	// solutions upwards
	memcpy(&g, grid, sizeof(grid_t));

	// make all simple substitutions
	for (;;) {
	subs = 0;
	unsolved = 0;

	// iterate over all rows
	for (i = 0; i < 9; i++) {
	// iterate over all columns
	for (j = 0; j < 9; j++) {
	int box, sol, solcount;
	int v[10] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };

	// skip slots that already have an assigned value
	if (g.grid[9*i+j] != 0) {
	continue;
	}

	// increment number of unsolved slots
	unsolved++;

	// eliminate all values occupied by other slots on this row
	for (k = 0; k < 9; k++) {
	v[g.grid[9*i+k]] = 0;
	}

	// eliminate values occupied by other slots in the same column
	for (k = 0; k < 9; k++) {
	v[g.grid[9*k+j]] = 0;
	}

	// finally, eliminate all slots occupied by values in the same 3x3 box
	box = 3*(i/3) + j/3;
	for (k = 3(box/3); k < 3(box/3)+3; k++) {
	for (m = 3(box%3); m < 3(box%3)+3; m++) {
	v[g.grid[9*k+m]] = 0;
	}
	}

	// count the number of possible values for this slot
	solcount = 0;
	sol = 0;
	for (k = 0; k < 10; k++) {
	if (v[k] != 0) {
	sol = v[k];
	solcount++;
	}
	}

	// if no possible values are found, there are no solutions
	if (solcount == 0) {
	return 0;
	}
	// if there is only one possible value, we substitute this value
	// into the grid
	else if (solcount == 1) {
	#ifdef DEBUG
	printf("unique substitution %d found at %d, %d\n", sol, i, j);
	#endif
	g.grid[i*9+j] = sol;
	subs++;
	}
	// otherwise just store a list of possible values until later
	// and try them until we find a solution.
	else {
	currentsub.row = i;
	currentsub.col = j;
	memcpy(&currentsub.v, v, sizeof(v));
	}
	}
	}

	// no possible substitutions remain, end loop
	if (subs == 0) {
	break;
	}
	}

	// permute solutions
	if (unsolved > 0) {
	for (i = 0; i < 10; i++) {
	if (currentsub.v[i] == 0) {
	continue;
	}

	g.grid[9*currentsub.row + currentsub.col] = currentsub.v[i];
	#ifdef DEBUG
	printf("%d: setting %d, %d to %d\n", level, currentsub.row, currentsub.col, currentsub.v[i]);
	#endif
	if (solve_grid(&g, level+1)) {
	solved = 1;
	break;
	}
	}
	} else {
	solved = 1;
	}


	if (!solved) {
	return 0;
	}

	// copy the final solution upwards the stack
	memcpy(grid, &g, sizeof(grid_t));

	return 1;
	}

	int main(int argc, char **argv)
	{
	grid_t grids, current, *next;
	int gridcount;
	int i;

	if (argc != 2) {
	printf("usage: sudoku [gridfile]\n");
	return 0;
	}

	gridcount = load_grids(&grids, argv[1]);
	if (gridcount == -1) {
	fprintf(stderr, "failed to open grid file.\n");
	return 1;
	}

	i = 0;
	for (current = grids; current != NULL; ) {
	printf("grid %d\n", i);
	print_grid(current);
	printf("\n");

	if (solve_grid(current, 0)) {
	print_grid(current);
	} else {
	printf("solution not found!\n");
	}

	printf("\n");

	next = current->next;
	free(current);
	current = next;
	i++;
	}

	return 0;
	}
	Grid 01
	003020600
	900305001
	001806400
	008102900
	700000008
	006708200
	002609500
	800203009
	005010300
	Grid 02
	200080300
	060070084
	030500209
	000105408
	000000000
	402706000
	301007040
	720040060
	004010003
	Grid 03
	000000907
	000420180
	000705026
	100904000
	050000040
	000507009
	920108000
	034059000
	507000000
	Grid 04
	030050040
	008010500
	460000012
	070502080
	000603000
	040109030
	250000098
	001020600
	080060020
	Grid 05
	020810740
	700003100
	090002805
	009040087
	400208003
	160030200
	302700060
	005600008
	076051090
	Grid 06
	100920000
	524010000
	000000070
	050008102
	000000000
	402700090
	060000000
	000030945
	000071006
	Grid 07
	043080250
	600000000
	000001094
	900004070
	000608000
	010200003
	820500000
	000000005
	034090710
	Grid 08
	480006902
	002008001
	900370060
	840010200
	003704100
	001060049
	020085007
	700900600
	609200018
	Grid 09
	000900002
	050123400
	030000160
	908000000
	070000090
	000000205
	091000050
	007439020
	400007000
	Grid 10
	001900003
	900700160
	030005007
	050000009
	004302600
	200000070
	600100030
	042007006
	500006800
	Grid 11
	000125400
	008400000
	420800000
	030000095
	060902010
	510000060
	000003049
	000007200
	001298000
	Grid 12
	062340750
	100005600
	570000040
	000094800
	400000006
	005830000
	030000091
	006400007
	059083260
	Grid 13
	300000000
	005009000
	200504000
	020000700
	160000058
	704310600
	000890100
	000067080
	000005437
	Grid 14
	630000000
	000500008
	005674000
	000020000
	003401020
	000000345
	000007004
	080300902
	947100080
	Grid 15
	000020040
	008035000
	000070602
	031046970
	200000000
	000501203
	049000730
	000000010
	800004000
	Grid 16
	361025900
	080960010
	400000057
	008000471
	000603000
	259000800
	740000005
	020018060
	005470329
	Grid 17
	050807020
	600010090
	702540006
	070020301
	504000908
	103080070
	900076205
	060090003
	080103040
	Grid 18
	080005000
	000003457
	000070809
	060400903
	007010500
	408007020
	901020000
	842300000
	000100080
	Grid 19
	003502900
	000040000
	106000305
	900251008
	070408030
	800763001
	308000104
	000020000
	005104800
	Grid 20
	000000000
	009805100
	051907420
	290401065
	000000000
	140508093
	026709580
	005103600
	000000000
	Grid 21
	020030090
	000907000
	900208005
	004806500
	607000208
	003102900
	800605007
	000309000
	030020050
	Grid 22
	005000006
	070009020
	000500107
	804150000
	000803000
	000092805
	907006000
	030400010
	200000600
	Grid 23
	040000050
	001943600
	009000300
	600050002
	103000506
	800020007
	005000200
	002436700
	030000040
	Grid 24
	004000000
	000030002
	390700080
	400009001
	209801307
	600200008
	010008053
	900040000
	000000800
	Grid 25
	360020089
	000361000
	000000000
	803000602
	400603007
	607000108
	000000000
	000418000
	970030014
	Grid 26
	500400060
	009000800
	640020000
	000001008
	208000501
	700500000
	000090084
	003000600
	060003002
	Grid 27
	007256400
	400000005
	010030060
	000508000
	008060200
	000107000
	030070090
	200000004
	006312700
	Grid 28
	000000000
	079050180
	800000007
	007306800
	450708096
	003502700
	700000005
	016030420
	000000000
	Grid 29
	030000080
	009000500
	007509200
	700105008
	020090030
	900402001
	004207100
	002000800
	070000090
	Grid 30
	200170603
	050000100
	000006079
	000040700
	000801000
	009050000
	310400000
	005000060
	906037002
	Grid 31
	000000080
	800701040
	040020030
	374000900
	000030000
	005000321
	010060050
	050802006
	080000000
	Grid 32
	000000085
	000210009
	960080100
	500800016
	000000000
	890006007
	009070052
	300054000
	480000000
	Grid 33
	608070502
	050608070
	002000300
	500090006
	040302050
	800050003
	005000200
	010704090
	409060701
	Grid 34
	050010040
	107000602
	000905000
	208030501
	040070020
	901080406
	000401000
	304000709
	020060010
	Grid 35
	053000790
	009753400
	100000002
	090080010
	000907000
	080030070
	500000003
	007641200
	061000940
	Grid 36
	006080300
	049070250
	000405000
	600317004
	007000800
	100826009
	000702000
	075040190
	003090600
	Grid 37
	005080700
	700204005
	320000084
	060105040
	008000500
	070803010
	450000091
	600508007
	003010600
	Grid 38
	000900800
	128006400
	070800060
	800430007
	500000009
	600079008
	090004010
	003600284
	001007000
	Grid 39
	000080000
	270000054
	095000810
	009806400
	020403060
	006905100
	017000620
	460000038
	000090000
	Grid 40
	000602000
	400050001
	085010620
	038206710
	000000000
	019407350
	026040530
	900020007
	000809000
	Grid 41
	000900002
	050123400
	030000160
	908000000
	070000090
	000000205
	091000050
	007439020
	400007000
	Grid 42
	380000000
	000400785
	009020300
	060090000
	800302009
	000040070
	001070500
	495006000
	000000092
	Grid 43
	000158000
	002060800
	030000040
	027030510
	000000000
	046080790
	050000080
	004070100
	000325000
	Grid 44
	010500200
	900001000
	002008030
	500030007
	008000500
	600080004
	040100700
	000700006
	003004050
	Grid 45
	080000040
	000469000
	400000007
	005904600
	070608030
	008502100
	900000005
	000781000
	060000010
	Grid 46
	904200007
	010000000
	000706500
	000800090
	020904060
	040002000
	001607000
	000000030
	300005702
	Grid 47
	000700800
	006000031
	040002000
	024070000
	010030080
	000060290
	000800070
	860000500
	002006000
	Grid 48
	001007090
	590080001
	030000080
	000005800
	050060020
	004100000
	080000030
	100020079
	020700400
	Grid 49
	000003017
	015009008
	060000000
	100007000
	009000200
	000500004
	000000020
	500600340
	340200000
	Grid 50
	300200000
	000107000
	706030500
	070009080
	900020004
	010800050
	009040301
	000702000
	000008006