aboutsummaryrefslogtreecommitdiffstats
path: root/c/sudoku.c
blob: 072d9575eb8211702f677f283a2389ab215497e1 (plain) (blame)
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
#include <stdbool.h>
#include <stdio.h>


bool inBox(int i, int n, char puzzle[])
{
  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] - '0' == n)
        return true;
    }
  }
  return false;
}


bool inCol(int i, int n, char puzzle[])
{
  int col = i % 9;
  for(int j = col; j < 81; j += 9) {
    if(puzzle[j] - '0' == n)
      return true;
  }
  return false;
}


bool inRow(int i, int n, char puzzle[])
{
  int row = i/9;
  for(int j = row; j/9 <= row; j++) {
    if(puzzle[j] - '0' == n)
      return true;
  }
  return false;
}


char* solve(char puzzle[])
{

  /* 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, puzzle) || inCol(i, n, puzzle) || inBox(i, n, puzzle))
        continue;

      puzzle[i] = n + '0';
      return solve(puzzle);
    }

    // need to backtrack

  next:
    i++;
  }

  return puzzle; // we solved it!
}


void display(char puzzle[])
{
  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[])
{
  display(argv[1]);
  for(int i=1; i < argc; i++) {
    char* puzzle = solve(argv[i]);

    display(puzzle);
  }
  return 0;
}