Viewing file: c/sudoku/sudoku.c | Back to directory listing
Author: Loren Segal | Last modified: February 21 2006 12:00 am | Download

#include <stdio.h>
#include <math.h>
 
#define SHARED_ROW 1
#define SHARED_COL 2
#define SHARED_BLK 4
static int count = 0;
 
typedef struct {
  int x;
  int y;
  int value;
  int data;
} cell;
 
cell grid[9][9];
int _setvalues = 0;
 
void makemove();
 
void printgrid()
{
  int x,y;
  for (y = 0; y < 9; y++)
  {
    for (x = 0; x < 9; x++)
    {
      printf("%d ", grid[x][y].value);
    }
    printf("\n");
  }
}
 
int main()
{
  int y,x;
  char buf[19];
  FILE *fp = fopen("grid.txt", "r");
  for(y = 0; y < 9; y++)
  {
    fgets(buf, 18, fp);
    for (x = 0; x < 9; x++)
    {  
      grid[x][y].x = x;
      grid[x][y].y = y;
      grid[x][y].value = buf[x] - '0';
      grid[x][y].data = 0;
      if (!grid[x][y].value) _setvalues++;
    }
  }
  printgrid();
  printf("\n");
  while (_setvalues) 
    makemove();
  printgrid();
}
 
int checkvalue(cell *g)
{
  int i, c = 0, n = 0;
  for (i = 0; i < 9; i++)
  {
    if (~g->data & (1 << i)) { c++; n = i; }
  }
  if (c == 1) 
  {
    g->data = 0;
    g->value = n + 1;
    _setvalues--;
    //printf("%d Set value for %d,%d: %d\n",_setvalues, g->x, g->y, g->value);
    return 1;
  }
  return 0;
}
 
int sharedgrid(int a, int b, int x, int y)
{
  int ret = 0;
  if (x == a && y != b) // check column
  {  
    ret |= SHARED_COL;
  } 
  if (x != a && y == b) // check row
  {
    ret |= SHARED_ROW;
  }
  if (!(a == x && b == y) && (int)(x / 3) == (int)(a / 3) && (int)(y / 3) == (int)(b / 3)) // check block
  {
    ret |= SHARED_BLK;
  }
  return ret;
}
 
void makemove()
{
  int x, y, i, c, a, b;
  count++;
  // check lines
  for (y = 0; y < 9; y++)
  {
    for (x = 0; x < 9; x++)
    {
      if (grid[x][y].value != 0) continue;
      for (b = 0; b < 9; b++)
      {
        for (a = 0; a < 9; a++)  
        {
          if (!sharedgrid(x,y,a,b) || !grid[a][b].value) continue; 
          grid[x][y].data |= (1 << (grid[a][b].value-1));
        }
      }
      if (checkvalue(&grid[x][y])) return;
    }
  }
 
  for (y = 0; y < 9; y++)
  {
    for (x = 0; x < 9; x++)
    {
      if (grid[x][y].value != 0) continue;
      for (i = 0; i < 9; i++)
      {
        int e[3] = {0}, r, d = 0; e[0] = 0; e[1] = 0; e[2] = 0;
        if (grid[x][y].data & (1 << i)) continue;
        for (b = 0; b < 9; b++)
        {
          for (a = 0; a < 9; a++)
          {
            r = sharedgrid(x,y,a,b);
            if (!r || grid[a][b].value) continue;
            if (~grid[a][b].data & (1 << i)) 
            { 
              if (r & SHARED_ROW) e[0]++;
              if (r & SHARED_COL) e[1]++;
              if (r & SHARED_BLK) e[2]++;
            } 
            d++;
          }
        }  
        if (d > 0 && (!e[0] || !e[1] || !e[2])) { grid[x][y].data = ~(1 << i); checkvalue(&grid[x][y]); return; }
      }
    }
  }
}