sudoku.c (3475B)
1 #include <stdio.h> 2 #include <stdlib.h> 3 #include <ctype.h> 4 #include <assert.h> 5 #include <unistd.h> 6 7 #define ORDER 3 8 #define WIDTH (ORDER*ORDER) 9 #define CELLS (WIDTH*WIDTH) 10 11 struct grid 12 { 13 unsigned short cells[CELLS]; 14 unsigned char assigned; 15 }; 16 17 static unsigned count_ones(unsigned x) 18 { 19 unsigned n = 0; 20 while (x) 21 { 22 n += x & 1; 23 x >>= 1; 24 } 25 return n; 26 } 27 28 static unsigned unshift(unsigned x) 29 { 30 unsigned n = 0; 31 assert(count_ones(x) == 1); 32 33 while (~x & 1) 34 { 35 x >>= 1; 36 ++n; 37 } 38 return n; 39 } 40 41 static int is_mod_max(unsigned x, unsigned mod) 42 { 43 return x % mod == mod - 1; 44 } 45 46 static void print_grid(struct grid const* g) 47 { 48 char buf[2 * CELLS]; 49 char* b = buf; 50 51 for (unsigned i = 0; i < CELLS; ++i) 52 { 53 unsigned cell = g->cells[i]; 54 unsigned ones = count_ones(cell); 55 56 if (!cell) 57 *b++ = '!'; 58 else if (ones > 1) 59 *b++ = ' '; 60 else 61 *b++ = '1' + unshift(cell); 62 63 if (is_mod_max(i, WIDTH)) 64 { 65 *b++ = '\n'; 66 if (is_mod_max(i, WIDTH * ORDER)) 67 *b++ = '\n'; 68 } 69 else if (is_mod_max(i, ORDER)) 70 *b++ = ' '; 71 } 72 assert(write(1, buf, b - buf) == b - buf); 73 } 74 75 static unsigned pick_one(unsigned choices) 76 { 77 unsigned n = 0; 78 unsigned val = 1; 79 do 80 { 81 while (val & ~choices) 82 val <<= 1; 83 } while (n--); 84 85 assert(val); 86 return val; 87 } 88 89 static unsigned round_down(unsigned n, unsigned radix) 90 { 91 return n / radix * radix; 92 } 93 94 static int resolve_assignment(struct grid* g, unsigned c); 95 96 static int exclude(struct grid* g, unsigned cell, unsigned val) 97 { 98 unsigned short* c = g->cells + cell; 99 if (*c == val) 100 return 0; 101 if (~*c & val) 102 return 1; 103 104 *c &= ~val; 105 106 if (count_ones(*c) == 1) 107 return resolve_assignment(g, cell); 108 return 1; 109 } 110 111 static int resolve_assignment(struct grid* g, unsigned c) 112 { 113 unsigned val = g->cells[c]; 114 g->assigned++; 115 116 for (unsigned x = 0; x < WIDTH; ++x) 117 { 118 unsigned C = round_down(c, WIDTH) + x; 119 if (C != c) 120 if (!exclude(g, C, val)) 121 return 0; 122 } 123 124 for (unsigned y = 0; y < WIDTH; ++y) 125 { 126 unsigned C = (c % WIDTH) + WIDTH * y; 127 if (C != c) 128 if (!exclude(g, C, val)) 129 return 0; 130 } 131 132 for (unsigned z = 0; z < WIDTH; ++z) 133 { 134 unsigned C = round_down(c, WIDTH * ORDER) + c / ORDER % ORDER * ORDER; 135 C += z / ORDER * WIDTH; 136 C += z % ORDER; 137 if (C != c) 138 if (!exclude(g, C, val)) 139 return 0; 140 } 141 142 return 1; 143 } 144 145 static int try_grid(struct grid g) 146 { 147 if (g.assigned == CELLS) 148 { 149 print_grid(&g); 150 return 1; 151 } 152 153 unsigned x = 0; 154 unsigned c = 0; 155 do 156 { 157 while (count_ones(g.cells[c]) == 1) 158 ++c; 159 ++c; 160 } while (x--); 161 --c; 162 unsigned val = pick_one(g.cells[c]); 163 164 struct grid G = g; 165 G.cells[c] = val; 166 if (resolve_assignment(&G, c)) 167 if (try_grid(G)) 168 return 1; 169 170 G = g; 171 G.cells[c] &= ~val; 172 if (count_ones(G.cells[c]) == 1) 173 if (!resolve_assignment(&G, c)) 174 return 0; 175 176 return try_grid(G); 177 } 178 179 void init_grid(struct grid* g, char const* str) 180 { 181 for (unsigned i = 0; *str && i < CELLS; ++str) 182 { 183 if (*str == '\n') 184 { 185 i = round_down(i + WIDTH, WIDTH); 186 continue; 187 } 188 while (isspace(*str)) 189 if(!*++str) 190 return; 191 192 if (isdigit(*str) && *str != '0') 193 { 194 g->cells[i] = 1 << (*str - '1'); 195 g->assigned++; 196 } 197 ++i; 198 } 199 } 200 201 char const test[] = 202 "53..7...." 203 "6..195..." 204 ".98....6." 205 "8...6...3" 206 "4..8.3..1" 207 "7...2...6" 208 ".6....28." 209 "...419..5" 210 "....8..79"; 211 212 int main() 213 { 214 struct grid g; 215 216 unsigned mask = 0; 217 for (unsigned i = 0; i < WIDTH; ++i) 218 mask |= 1 << i; 219 for (unsigned i = 0; i < CELLS; ++i) 220 g.cells[i] = mask; 221 222 init_grid(&g, test); 223 // print_grid(&g); 224 225 226 return !try_grid(g); 227 }