A sudoku solver using simple backtracking. (C++)

in.txt

53  7    
6  195   
 98    6 
8   6   3
4  8 3  1
7   2   6
 6    28 
   419  5
    8  79

sudoku.cpp

#include <bits/stdc++.h>
#include <vector>
using namespace std;

#define BSIZE (9)
#define EMPTY (-1)
int board[BSIZE][BSIZE];
typedef struct {int x, y;} coord;
typedef struct move_t {coord c; int n; move_t(coord& _c, int& _n) : c(_c), n(_n) {};} move_t;
vector <move_t> s;
coord firstempty;

bool getempty()
{
	int i, j;
	for (i = 0; i < BSIZE; i++)
		for (j = 0; j < BSIZE; j++)
			if (board[i][j] == EMPTY)
			{
				firstempty = {i, j};
				return true;
			}
	return false;
}

bool check()
{
	bool check[10];
	
	// Rows.
	for (int i = 0; i < BSIZE; i++)
	{
		memset(check, 0, sizeof(check));
		for (int j = 0; j < BSIZE; j++)
			if (board[i][j] != EMPTY)
			{
				if (check[board[i][j]] == 1)
					return false;
				else
					check[board[i][j]] = 1;
			}
	}

	// Columns.
	for (int j = 0; j < BSIZE; j++)
	{
		memset(check, 0, sizeof(check));
		for (int i = 0; i < BSIZE; i++)
			if (board[i][j] != EMPTY)
			{
				if (check[board[i][j]] == 1)
					return false;
				else
					check[board[i][j]] = 1;
			}
	}

	// Subboxes.
	assert(BSIZE == 9);
	for (int m = 0; m < BSIZE; m += 3)
		for (int n = 0; n < BSIZE; n += 3)
		{
			memset(check, 0, sizeof(check));
			for (int i = m; i < m+3; i++)
				for (int j = n; j < n+3; j++)
					if (board[i][j] != EMPTY)
					{
						if (check[board[i][j]] == 1)
							return false;
						else
							check[board[i][j]] = 1;
					}
		}

	// No failures, so board must be valid.
	return true;
}

void solve()
{
	// Initialise.
	if (!getempty())
		return;
	for (int i = 1; i <= 9; i++)
		s.push_back(move_t(firstempty, i));

	// Go.
	while (s.size() != 0)
	{
		move_t m = s.back(); s.pop_back();
		board[m.c.x][m.c.y] = m.n;

		if (!check()) // reject()
		{
			board[m.c.x][m.c.y] = EMPTY;
			continue;
		}

		if (!getempty()) // accept()
			return;

		for (int i = 1; i <= 9; i++)
			s.push_back(move_t(firstempty, i));
	}
}

int main()
{
	freopen("in.txt", "r", stdin);

	for (int i = 0; i < BSIZE; i++)
	{
		for (int j = 0; j < BSIZE; j++)
		{
			char c = getc(stdin);
			board[i][j] = c == ' ' ? EMPTY : c - '0';
		}
		getc(stdin);
	}

	solve();

	for (int i = 0; i < BSIZE; i++)
	{
		for (int j = 0; j < BSIZE; j++)
			fputc((board[i][j] == EMPTY ? ' ' : board[i][j] + '0'), stdout);
		fputc('\n', stdout);
	}
}