読者です 読者をやめる 読者になる 読者になる

数独(推論のいらない場合)

数独を解くプログラムです。少しでも問題が難しいと、解けなくなります。

コード

#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();
}