c/sudoku.c


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109

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


char PUZZLE[81];


bool inBox(int i, int n)
{
  int inum = n + '0';
  int boxRow = (i / 9 / 3) * 27;
  int boxCol = ((i % 9) / 3) * 3;

  for(int j = boxRow; j < boxRow + 27; j += 9) {
    for(int k = boxCol; k < boxCol + 3; k++){
      if(PUZZLE[j + k] == inum && i != j + k)
        return true;
    }
  }
  return false;
}


bool inCol(int i, int n)
{
  int inum = n + '0';
  int col = i % 9;

  for(int j = col; j < 81; j += 9) {
    if(PUZZLE[j] == inum && i != j )
      return true;
  }
  return false;
}


bool inRow(int i, int n)
{
  int inum = n + '0';
  int row = (i/9) * 9;

  for(int j = row; j < row + 9; j++) {
    if(PUZZLE[j] == inum && i != j)
      return true;
  }
  return false;
}


bool solve()
{

  /* search for an unanswered square */
  int i = 0;
  while(PUZZLE[i] != '\0') {
    if(PUZZLE[i] - '0' != 0) {
      goto next; // this square is answered
    }

    for(int n=1; n<10; n++) {
      if(inRow(i, n) || inCol(i, n) || inBox(i, n))
        continue;

      PUZZLE[i] = n + '0';
      if(solve())
        return true;
    }

    // need to backtrack
    PUZZLE[i] = 0 + '0';
    return false;

  next:
    i++;
  }

  return true;
}


void display()
{
  printf("\n  ");

  int i = 0;
  while(PUZZLE[i] != '\0') {
    printf(" %d", PUZZLE[i] - '0');

    if(i % 9 == 8)
      printf("\n  ");
    i++;
  }

  printf("\n");
}


int main(int argc, char *argv[])
{
  for(int i=1; i < argc; i++) {
    strcpy(PUZZLE, argv[i]);
    display();

    solve();
    display();
  }
  return 0;
}