Sudoku solver in C

sudoku.c

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

int board[9][9];
int rowmask[9];
int colmask[9];
int sqrmask[3][3];
int possible[9][9];
int numpos[9][9];

static void
read_board(void)
{
  int i, j;

  for (i = 0; i < 9; ++i)
    {
      for (j = 0; j < 9; ++j)
	{
	  char c;
	  if (scanf("%c", &c) != 1)
	    error(1, 0, "Couldn't read");
	  if (c != ' ')
	    {
	      if (c < '0' || '9' < c)
		error(1, 0, "Invalid input");
	      board[i][j] = c - '0';
	    }
	}
      if (getchar() != '\n')
	error(1, 0, "Row too long");
    }
}

static void
check(void)
{
  int i, j;

  memset(rowmask, 0, sizeof rowmask);
  memset(colmask, 0, sizeof colmask);
  memset(sqrmask, 0, sizeof sqrmask);

  for (i = 0; i < 9; ++i)
    {
      int v;
      for (j = 0; j < 9; ++j)
	if (board[i][j])
	  {
	    v = 1 << board[i][j];
	    if (rowmask[i] & v)
	      error(1, 0, "Number %d repeats in row %d", board[i][j], i + 1);
	    rowmask[i] |= v;
	  }
    }

  for (j = 0; j < 9; ++j)
    {
      int v;
      for (i = 0; i < 9; ++i)
	if (board[i][j])
	  {
	    v = 1 << board[i][j];
	    if (colmask[j] & v)
	      error(1, 0, "Number %d repeats in column %d", board[i][j], j + 1);
	    colmask[j] |= v;
	  }
    }

  for (i = 0; i < 9; i += 3)
    for (j = 0; j < 9; j += 3)
      {
	int v, x, y;
	for (x = 0; x < 3; ++x)
	  for (y = 0; y < 3; ++y)
	    if (board[i + x][j + y])
	      {
		v = 1 << board[i + x][j + y];
		if (sqrmask[i / 3][j / 3] & v)
		  error(1, 0, "Number %d repeats in subsquare (%d, %d)",
			board[i + x][j + y], i / 3 + 1, j / 3 + 1);
		sqrmask[i / 3][j / 3] |= v;
	      }
      }
}

static void
compute_possible(void)
{
  int i, j;

  memset(possible, 0, sizeof possible);
  memset(numpos, 0, sizeof numpos);

  for (i = 0; i < 9; ++i)
    for (j = 0; j < 9; ++j)
      {
	int m;
	possible[i][j] = ~rowmask[i] & ~colmask[j] & ~sqrmask[i / 3][j / 3];
	possible[i][j] &= 1022;
	for (m = 512; m; m >>= 1)
	  if (possible[i][j] & m)
	    ++numpos[i][j];
      }
}

static int
bit(int x)
{
  int b;

  for (b = 0; 1 < x; x >>= 1, ++b)
    ;

  return b;
}

static int
solve(void)
{
  int i, j, mini, minj;
  int minpos = 10;
  int solved = 1;

  check();
  compute_possible();

  for (i = 0; i < 9; ++i)
    for (j = 0; j < 9; ++j)
	if (board[i][j] == 0)
	  {
	    solved = 0;
	    if (numpos[i][j] < minpos)
	      {
		mini = i;
		minj = j;
		minpos = numpos[i][j];
	      }
	  }

  if (solved)
    return 1;
  else if (minpos == 0)
    return 0;
  else
    {
      int p = possible[mini][minj];
      while (p)
	{
	  int b = bit(p);
	  board[mini][minj] = b;
	  if (solve())
	    return 1;
	  else
	    p &= ~(1 << b);
	}
      board[mini][minj] = 0;
      return 0;
    }
}

static void
print_board(void)
{
  int i, j;

  for (i = 0; i < 9; ++i)
    {
      for (j = 0; j < 9; ++j)
	printf("%d", board[i][j]);
      printf("\n");
    }
}

int
main(void)
{
  read_board();
  if (solve())
    print_board();
  else
    error(1, 0, "Unsolvable");
  return 0;
}

I hereby release this fine software under the GPL. 🌮