数独(推論のいる場合)

数独の拘束条件だけでは答えが1つに絞れない場合に対応しているプログラムです。

例

例えば、こんな問題(0は空欄を意味します)は前回のプログラムでは解くことはできませんでしたが、今回のプログラムでは解くことができます。

000 104 870

000 007 400

300 000 200

000 050 060

005 020 907

003 000 040

050 900 080

000 080 000

890 605 700

ソースコード

sudoku.h:

#ifndef _SUDOKU_H_
#define _SUDOKU_H_
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <string.h>
struct State {
  char c;
  struct State* right;
  struct State* down;
};
struct Box {
  struct State* start;
  struct Box* LR[2];
  struct Box* UD[2];
};
int sudoku_basic_solve(struct Box** bs);
void sudoku_to_string(char* buf,struct Box** bs);
int sudoku_is_success(struct Box** bs);
int sudoku_is_inconsistent(struct Box** bs);
struct Box** sudoku(char* inp);
void sudoku_free(struct Box** bs);
void basic_test(void);
void sudoku_clear(void);
extern char candidates[35];
extern struct State* cand_s[5];
#endif

basic.c:

#include "sudoku.h"
char candidates[35];
struct State* cand_s[5];
static struct State* state(char c) {
struct State* s = malloc(sizeof(struct State));
  s->c = c;
  s->down = NULL; s->right = NULL;
  return s;
}
static 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;
}
static void box_free(struct Box* b) {
struct State* iter = b->start;
  while(iter != NULL) {
    free(iter);
    iter = iter->right;
  }
  free(b);
}
static 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;
}
static 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;
}
static 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;
}
static char* swap(char* start, char* end, char c) {
char*  ptr = start;
char tmp;
  if(c == *end) {
    if(start == end)
      return NULL;
    return end - 1;
  }
  if(start == end)
    return end;
  while(ptr != end) {
    if(*ptr == c) {
      tmp = *ptr; *ptr = *end; *end = tmp;
      return end - 1;
    }
    ptr++;
  }
  return end;
}
static 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 -3;
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 != NULL)
    end = swap(nine, end, *iter++);
  if(end == NULL)
    return -2;
  if(end == &nine[0]) {
    s->c = nine[0];
    return (int)nine[0] - '0';
  } else {
    int len = (end - &nine[0]) + 1;
    int pos = len * (len + 1)/2 - 3;
    if(candidates[pos] == 0) {
      cand_s[len-2] = s;
      memcpy(&candidates[pos], nine, len);
    }
    return -len;
  }
}

void sudoku_clear(void) {
  memset(candidates, 0, 35);
int i;
  for(i = 0; i < 5; i++) {
    cand_s[i] = NULL;
  }
}
int sudoku_basic_solve(struct Box** bs) {
int n = -1; int m; int i, j;
  sudoku_clear();
  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;
}
int sudoku_is_inconsistent(struct Box** bs) {
static char empty[35]; memset(empty, 0, 35);
return !sudoku_is_success(bs) && !memcmp(empty, candidates, 35);
}
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_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(-2 == 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);
sudoku_clear();
while(sudoku_basic_solve(bs) > 0);
char empty[35];
memset(empty, 0, 35);
assert(sudoku_is_success(bs) && !memcmp(empty, candidates, 35) && "is_success1");
assert(!sudoku_is_inconsistent(bs));
sudoku_free(bs);
}
{
char inp[] =
  "000 000 007\n"
  "704 000 893\n"
  "006 802 600\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);
int i = 0;
int n;
sudoku_clear();
while((n = sudoku_basic_solve(bs)) > 0)i++;
char empty[35];
memset(empty, 0, 35);
assert(!sudoku_is_success(bs) && n == -1 && !memcmp(empty, candidates, 35) && "inconsistent");
assert(sudoku_is_inconsistent(bs));
sudoku_free(bs);
}
{
char inp[] =
"269 134 875\n"
"180 267 493\n"
"347 598 216\n"

"978 453 162\n"
"415 826 937\n"
"623 719 548\n"

"756 901 384\n"
"031 082 659\n"
"890 645 721\n"
;
struct Box** bs = sudoku(inp);
int i = 0;
int n;
sudoku_clear();
while((n = sudoku_basic_solve(bs)) > 0)i++;
char empty[35];
memset(empty, 0, 35);
assert(!sudoku_is_success(bs) && n == -1 && !memcmp(empty, candidates, 35) && "inconsistent");
assert(sudoku_is_inconsistent(bs));
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);
int n;
sudoku_clear();
while((n = sudoku_basic_solve(bs)) > 0);
char empty[35];
memset(empty, 0, 35);
assert(!sudoku_is_success(bs) && n == -1 && memcmp(empty, candidates, 35) && "failed");
assert(!sudoku_is_inconsistent(bs));
sudoku_free(bs);
}
}
void test_candidates(void) {
char inp[] =
  "000 104 870\n"
  "000 007 400\n"
  "300 000 200\n"
  
  "000 050 060\n"
  "005 020 907\n"
  "003 000 040\n"
  
  "050 900 080\n"
  "000 080 000\n"
  "890 605 700\n"
  ;
  sudoku_clear();
struct Box** bs = sudoku(inp);
  while(sudoku_basic_solve(bs) > 0);
  assert(!strcmp("62", &candidates[0]));
  assert(cand_s[0] == bs[0]->start->right);
  assert(!strcmp("629", &candidates[3]));
  assert(cand_s[1] == bs[0]->start->right->right);
  assert(!strcmp("6295", &candidates[7]));
  assert(cand_s[2] == bs[0]->start);
  assert(!strcmp("12965", &candidates[12]));
  assert(cand_s[3] == bs[0]->start->down);
  assert(!strcmp("189476", &candidates[18]));
  assert(cand_s[4] == bs[0]->start->down->down->right->right);
  assert(!strcmp("1234569", &candidates[25]));
  assert(cand_s[5] == bs[8]->start->down->right->right);
  sudoku_clear();
  char empty[35];
  memset(empty, 0, 35);
  assert(!memcmp(candidates, empty, 35));
int i;
  for(i = 0; i < 5; i++) {
    assert(NULL == cand_s[i]);
  }
}

void basic_test(void) {
  test_state();
  test_box();
  test_box_value_at();
  test_value();
  test_basic_solve();
  test_is_success();
  test_candidates();
}

sudoku.c:

#include "sudoku.h"
#include <sys/types.h>
#include <sys/stat.h>
#include <unistd.h>
#include <sys/mman.h>
#include <fcntl.h>
static void sudoku_memset(char* mem, struct Box** bs) {
  memset(mem, 0, 90);
  int i;
  for(i = 0; i < 9; i++) {
    struct State* s = bs[i]->start;
    int j = i * 10;
    while(s != NULL) {
      mem[j++] = s->c;
      s = s->right;
    }
  }

}
static void sudoku_reset(struct Box** bs, char* mem) {
  int i;
  for(i = 0; i < 9; i++) {
    struct State* s = bs[i]->start;
    int j = i * 10;
    while(s != NULL) {
      s->c = mem[j++];
      s = s->right;
    }
  }
}

int sudoku_solve(struct Box** bs) {
int n;
  while((n = sudoku_basic_solve(bs)) > 0);
char* ptr = candidates;
int j;
  for(j = 0; j < 35; j++) {
    if(*ptr != 0)
      break;
    ptr++;
  }
  int len = strlen(ptr);
  if(sudoku_is_inconsistent(bs))
    return -1;
  if(sudoku_is_success(bs))
    return 1;
char cnd[8];
  memset(cnd, 0, 8);
  memcpy(cnd, ptr, len);
int i;
  struct State* s = cand_s[len -2];
char mem[90];
  for(i = 0; i < len; i++) {
    sudoku_memset(mem, bs);
    s->c = cnd[i];
    sudoku_clear();
    n = sudoku_solve(bs);
    if(sudoku_is_success(bs))
      break;
    sudoku_reset(bs, mem);
  }
  return n;
}
void test(void);
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;
  if(sudoku_solve(bs) > 0)
    printf("answer:\n");
  else  
    printf("inconsistent:\n"); 
  char buffer[109];
  sudoku_to_string(buffer, bs);
  printf("%s",buffer);
  munmap(inp, st.st_size);
  exit(0);
}
void test_sudoku_reset(void) {
char inp[] =
  "000 000 007\n"
  "704 000 893\n"
  "006 802 600\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);
sudoku_clear();
char mem[90];
sudoku_memset(mem, bs);
assert(!strcmp("000704006", &mem[0]));
assert(!strcmp("000000802", &mem[10]));
assert(!strcmp("007893600", &mem[20]));
assert(!strcmp("007080903", &mem[30]));
assert(!strcmp("528006400", &mem[40]));
assert(!strcmp("600701080", &mem[50]));
assert(!strcmp("000600459", &mem[60]));
assert(!strcmp("704090000", &mem[70]));
assert(!strcmp("900000108", &mem[80]));
while(sudoku_basic_solve(bs) > 0);
char empty[35];
assert(sudoku_is_inconsistent(bs));
sudoku_reset(bs, mem);
bs[2]->start->down->down->c = '0';
while(sudoku_basic_solve(bs) > 0);
assert(sudoku_is_success(bs));
sudoku_free(bs);
}

void test_solve(void) {
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);
  sudoku_clear();
  assert(sudoku_solve(bs) > 0);
char buf[109];
char expect[] =
  "835 126 749\n"
  "416 397 258\n"
  "792 548 631\n"
  
  "643 912 875\n"
  "981 754 362\n"
  "527 683 194\n"
  
  "269 835 417\n"
  "178 469 523\n"
  "354 271 986\n"
  ;
  sudoku_to_string(buf, bs);
  assert(!strcmp(expect, buf));
}
void test(void) {
  basic_test();
  test_sudoku_reset();
  test_solve();
}