数独(推論のいらない場合)
数独を解くプログラムです。少しでも問題が難しいと、解けなくなります。
コード
#include <stdio.h> #include <stdlib.h> #include <assert.h> #include <string.h> struct State { char c; struct State* right; struct State* down; }; struct State* state(char c) { struct State* s = malloc(sizeof(struct State)); s->c = c; s->down = NULL; s->right = NULL; return s; } struct Box { struct State* start; struct Box* LR[2]; struct Box* UD[2]; }; struct Box* box(const char* inp) { struct Box* b = malloc(sizeof(struct Box)); b->start = state(*inp++); struct State* s = b->start; while(*inp != 0) { struct State* r = state(*inp++); s->right = r; s = r; } s = b->start; while(s->right->right->right != NULL) { s->down = s->right->right->right; s = s->right; } b->LR[0] = NULL; b->LR[1] = NULL; b->UD[0] = NULL; b->UD[1] = NULL; return b; } void box_free(struct Box* b) { struct State* iter = b->start; while(iter != NULL) { free(iter); iter = iter->right; } free(b); } int box_to_string(char* buf,const struct Box* b) { struct State* iter = b->start; int n = 0; while(iter != NULL) { char c = iter->c; if(c != '0') { *buf++ = c; n++; } iter = iter->right; } *buf = '\0'; return n; } int box_column_at(char* buf,const struct Box* b, int index) { struct State* iter = b->start; int i; for(i = 0; i < index; i++) iter = iter->right; int n = 0; while(iter != NULL) { char c = iter->c; if(c != '0') { *buf++ = c; n++; } iter = iter->down; } *buf = '\0'; return n; } int box_row_at(char* buf,const struct Box* b, int index) { struct State* iter = b->start; int i; for(i = 0; i < index; i++) iter = iter->down; int n = 0; for(i = 0; i < 3; i++) { char c = iter->c; if(c != '0') { *buf++ = c; n++; } iter = iter->right; } *buf = '\0'; return n; } char* swap(char* start, char* end, char c) { char* ptr = start; char tmp; if(c == *end) return end -1; while(ptr != end) { if(*ptr == c) { tmp = *ptr; *ptr = *end; *end = tmp; return end-1; } ptr++; } return end; } int box_value_at(struct Box* b, int index) { struct State* s = b->start; int i; for(i = 0; i < index; i++) s = s->right; if(s->c != '0') return - ((int)s->c - '0'); char buf[24]; int n; n = box_to_string(buf, b); n += box_row_at(buf+n, b->LR[0], index/3); n += box_row_at(buf+n, b->LR[1], index/3); n += box_column_at(buf+n, b->UD[0], index % 3); n += box_column_at(buf+n, b->UD[1], index % 3); char nine[] = "123456789"; char* end = &nine[8]; char* iter = &buf[0]; while(*iter != 0) { end = swap(nine, end, *iter++); } if(end == &nine[0]) { s->c = nine[0]; return (int)nine[0] - '0'; } else { return -1; } } int sudoku_basic_solve(struct Box** bs) { int n = -1; int m; int i, j; for(i = 0; i < 9; i++) { for(j = 0; j < 9; j++) { if((m = box_value_at(bs[i], j)) > 0) n = m; } } return n; } void sudoku_to_string(char* buf,struct Box** bs) { int i; struct State* s; for(i = 0; i < 3; i++) { s = bs[i]->start; *buf++ = s->c; s = s->right; *buf++ = s->c; s = s->right; *buf++ = s->c; *buf++ = ' '; } *--buf = '\n'; buf++; for(i = 0; i < 3; i++) { s = bs[i]->start; s = s->down; *buf++ = s->c; s = s->right; *buf++ = s->c; s = s->right; *buf++ = s->c; *buf++ = ' '; } *--buf = '\n'; buf++; for(i = 0; i < 3; i++) { s = bs[i]->start; s = s->down; s = s->down; *buf++ = s->c; s = s->right; *buf++ = s->c; s = s->right; *buf++ = s->c; *buf++ = ' '; } *--buf = '\n'; buf++; for(i = 3; i < 6; i++) { s = bs[i]->start; *buf++ = s->c; s = s->right; *buf++ = s->c; s = s->right; *buf++ = s->c; *buf++ = ' '; } *--buf = '\n'; buf++; for(i = 3; i < 6; i++) { s = bs[i]->start; s = s->down; *buf++ = s->c; s = s->right; *buf++ = s->c; s = s->right; *buf++ = s->c; *buf++ = ' '; } *--buf = '\n'; buf++; for(i = 3; i < 6; i++) { s = bs[i]->start; s = s->down; s = s->down; *buf++ = s->c; s = s->right; *buf++ = s->c; s = s->right; *buf++ = s->c; *buf++ = ' '; } *--buf = '\n'; buf++; for(i = 6; i < 9; i++) { s = bs[i]->start; *buf++ = s->c; s = s->right; *buf++ = s->c; s = s->right; *buf++ = s->c; *buf++ = ' '; } *--buf = '\n'; buf++; for(i = 6; i < 9; i++) { s = bs[i]->start; s = s->down; *buf++ = s->c; s = s->right; *buf++ = s->c; s = s->right; *buf++ = s->c; *buf++ = ' '; } *--buf = '\n'; buf++; for(i = 6; i < 9; i++) { s = bs[i]->start; s = s->down; s = s->down; *buf++ = s->c; s = s->right; *buf++ = s->c; s = s->right; *buf++ = s->c; *buf++ = ' '; } *--buf = '\n'; buf++; *buf = '\0'; } int sudoku_is_success(struct Box** bs) { int i; for(i = 0; i < 9; i++) { struct State* iter = bs[i]->start; while(iter->right != NULL) { if(iter->c == '0') return 0; iter = iter->right; } } return 1; } struct Box** sudoku(char* inp) { struct Box** boxes = malloc(9 * sizeof boxes[0]); char cpy[109]; memset(cpy, 0, 109); memcpy(cpy, inp, 108); int i; for(i = 3; i < 109; i += 4) cpy[i] = '\0'; char buf[10]; int j = 0; for(i = 0; i < 99; i += 12) { char* one = &cpy[i]; i+=12; char* two = &cpy[i]; i+=12; char* three = &cpy[i]; sprintf(buf, "%s%s%s", one, two, three); boxes[j] = box(buf); j += 3; } j = 1; for(i = 4; i < 103; i += 12) { char* one = &cpy[i]; i+=12; char* two = &cpy[i]; i+=12; char* three = &cpy[i]; sprintf(buf, "%s%s%s", one, two, three); boxes[j] = box(buf); j += 3; } j = 2; for(i = 8; i < 109; i += 12) { char* one = &cpy[i]; i+=12; char* two = &cpy[i]; i+=12; char* three = &cpy[i]; sprintf(buf, "%s%s%s", one, two, three); boxes[j] = box(buf); j += 3; } for(j = 0; j <= 6; j+= 3) { for(i = j; i < (j + 3); i++) { boxes[i]->LR[0] = boxes[j + (i + 1) % 3]; boxes[i]->LR[1] = boxes[j + (i + 2) % 3]; boxes[i]->UD[0] = boxes[(i + 3) % 9]; boxes[i]->UD[1] = boxes[(i + 6) % 9]; } } return boxes; } void sudoku_free(struct Box** bs) { int i; for(i = 0; i < 9; i++) box_free(bs[i]); free(bs); } void test(void); #include <sys/types.h> #include <sys/stat.h> #include <unistd.h> #include <sys/mman.h> #include <fcntl.h> int main(int argc, char* argv[]) { if(argc == 2 && !strcmp("test", argv[1])) { test(); exit(0); } int fd; if(argc != 2) { fprintf(stderr, "usage:%s <filename>\n", argv[0]); exit(1); } fd = open(argv[1], O_RDONLY); if(fd < 0) { fprintf(stderr, "failed\n"); exit(1); } char* inp; struct stat st; fstat(fd, &st); inp = mmap(NULL, st.st_size, PROT_READ, MAP_PRIVATE, fd, 0); close(fd); printf("input:\n%s", inp); struct Box** bs = sudoku(inp); int i = 0; while(sudoku_basic_solve(bs) > 0)i++; if(sudoku_is_success(bs)) { printf("answer (%d steps):\n", i); char buffer[109]; sudoku_to_string(buffer, bs); printf("%s",buffer); } else { printf("failed\n"); } munmap(inp, st.st_size); exit(0); } void test_state(void) { struct State* s = state('3'); assert('3' == s->c); assert(NULL == s->right); assert(NULL == s->down); free(s); } void test_box(void) { char inp[] = "123456789"; struct Box* b = box(inp); char buf[10]; box_to_string(buf, b); assert(!strcmp("123456789", buf)); assert(3 == box_column_at(buf, b, 0)); assert(!strcmp("147", buf)); assert(3 == box_column_at(buf, b, 1)); assert(!strcmp("258", buf)); assert(3 == box_column_at(buf, b, 2)); assert(!strcmp("369", buf)); assert(3 == box_row_at(buf, b, 0)); assert(!strcmp("123", buf)); assert(3 == box_row_at(buf, b, 1)); assert(!strcmp("456", buf)); assert(3 == box_row_at(buf, b, 2)); assert(!strcmp("789", buf)); box_free(b); } void test_box_value_at(void) { struct Box* b = box("007080903"); b->LR[0] = box("528006400"); b->LR[1] = box("600701080"); b->UD[0] = box("000704006"); b->UD[1] = box("000600459"); char buf[10]; box_to_string(buf, b); assert(!strcmp("7893", buf)); assert(1 == box_column_at(buf, b->UD[0], 0)); assert(!strcmp("7", buf)); assert(2 == box_column_at(buf, b->UD[1], 0)); assert(!strcmp("64", buf)); assert(3 == box_row_at(buf, b->LR[0], 0)); assert(!strcmp("528", buf)); assert(1 == box_row_at(buf, b->LR[1], 0)); assert(!strcmp("6", buf)); assert(-1 == box_value_at(b, 1)); box_to_string(buf, b); assert(!strcmp("7893", buf)); assert(1 == box_value_at(b, 0)); box_to_string(buf, b); assert(!strcmp("17893", buf)); box_free(b->LR[0]); box_free(b->LR[1]); box_free(b->UD[0]); box_free(b->UD[1]); box_free(b); } void test_value(void) { char inp[] = "78935286764"; char nine[] = "123456789"; char* end = &nine[8]; end = swap(nine, end, inp[0]); assert(!strcmp("123456987", nine)); assert(&nine[7] == end); end = swap(nine, end, inp[1]); assert(!strcmp("123456987", nine)); assert(&nine[6] == end); } void test_basic_solve(void) { char inp[] = "000 000 007\n" "704 000 893\n" "006 802 000\n" "007 528 600\n" "080 006 701\n" "903 400 080\n" "000 704 900\n" "600 090 000\n" "459 000 108\n" ; struct Box** bs = sudoku(inp); char buf[109]; box_to_string(buf, bs[0]); assert(!strcmp("746", buf)); box_to_string(buf, bs[1]); assert(!strcmp("82", buf)); box_to_string(buf, bs[2]); assert(!strcmp("7893", buf)); box_to_string(buf, bs[3]); assert(!strcmp("7893", buf)); box_to_string(buf, bs[4]); assert(!strcmp("52864", buf)); box_to_string(buf, bs[5]); assert(!strcmp("6718", buf)); box_to_string(buf, bs[6]); assert(!strcmp("6459", buf)); box_to_string(buf, bs[7]); assert(!strcmp("749", buf)); box_to_string(buf, bs[8]); assert(!strcmp("918", buf)); int j = 0; while(sudoku_basic_solve(bs) > 0)j++; assert(9 == j); while(sudoku_basic_solve(bs) > 0)j++; sudoku_to_string(buf, bs); char expect[] = "815 349 267\n" "724 651 893\n" "396 872 415\n" "147 528 639\n" "582 936 741\n" "963 417 582\n" "231 784 956\n" "678 195 324\n" "459 263 178\n" ; assert(!strcmp(expect, buf) && "check answer"); sudoku_free(bs); } void test_is_success(void) { { char inp[] = "000 000 007\n" "704 000 893\n" "006 802 000\n" "007 528 600\n" "080 006 701\n" "903 400 080\n" "000 704 900\n" "600 090 000\n" "459 000 108\n" ; struct Box** bs = sudoku(inp); while(sudoku_basic_solve(bs) > 0); assert(sudoku_is_success(bs) && "is_success1"); sudoku_free(bs); } { char inp[] = "030 000 040\n" "010 097 050\n" "002 508 600\n" "003 000 800\n" "900 004 300\n" "007 600 004\n" "009 805 400\n" "070 000 020\n" "050 071 080\n" ; struct Box** bs = sudoku(inp); while(sudoku_basic_solve(bs) > 0); assert(!sudoku_is_success(bs) && "is_success2"); sudoku_free(bs); } } void test(void) { test_state(); test_box(); test_box_value_at(); test_value(); test_basic_solve(); test_is_success(); }