Sudoku 해결 프로그램

#include <stdio.h>

#include <stdlib.h>

#include <memory.h>

int table[9][9];

int finish = 1;

FILE *out;

typedef struct node

{

int x, y;

int cand[10];

struct node *next;

}list;

list *head, *tail;

int input()

{

FILE *fp1 = fopen("input.txt", "rt");

if (fp1 == NULL) return 0;                 

for (int i = 0; i < 9; i++)

{

for (int j = 0; j < 9; j++)

{

fscanf(fp1, " %1d", &table[i][j]);

}

}

fclose(fp1);

return 1;

}

void col(int x, int *a)

{

int i;

for (i = 0; i < 9; i++)

{

if (table[i][x] != 0)

{

a[table[i][x]] = 0;

}

}

}

void row(int y, int *a)

{

int i;

for (i = 0; i < 9; i++)

{

if (table[y][i] != 0)

{

a[table[y][i]] = 0;

}

}

}

int end()

{

for (int i = 0; i < 9; i++)

{

for (int j = 0; j < 9; j++)

{

if (table[i][j] == 0)

{

return 0;

}

}

}return 1;

}

void big(int y, int x, int *a)

{

int i, j;

for (i = y; i < y + 3; i++)

{

for (j = x; j < x + 3; j++)

{

if (table[i][j] != 0)

{

a[table[i][j]] = 0;

}

}

}

}

void samesame(int *a, int *b, int *c)

{

int i;

for (i = 1; i <= 9; i++)

{

a[i] = a[i] & b[i] & c[i];

}

}

void get_cand(int y, int x, int *a)

{

int i, j;

int cand[3][10];

for (i = 0; i < 3; i++)

{

for (j = 0; j < 10; j++)

{

cand[i][j] = 1;

}

}

row(y, cand[0]);

col(x, cand[1]);

big((y / 3) * 3, (x / 3) * 3, cand[2]);

samesame(cand[0], cand[1], cand[2]);

memcpy(a, cand[0], sizeof(int) * 10);

}

void set()

{

int x, y;

list *temp;

temp = (list *)malloc(sizeof(list));

head = (list *)malloc(sizeof(list));

tail = (list *)malloc(sizeof(list));

temp = head;

for (y = 0; y<9; y++)

{

for (x = 0; x<9; x++)

{

if (table[y][x] == 0)

{

temp->y = y;

temp->x = x;

temp->next = (list *)malloc(sizeof(list));

temp = temp->next;

}

}

}

tail = temp;

}

void solveproblem(list *paper)

{

int i;

if (paper == tail)

{

if (end())

{

int i, j;

fprintf(out, "%d번째\n", finish);

for (i = 0; i < 9; i++)

{

for (j = 0; j < 9; j++)

{

fprintf(out, " %d", table[i][j]);

}fprintf(out, "\n");

}

if (finish == 1)

{

exit(1);

}

}

}

get_cand(paper->y, paper->x, paper->cand);

for (i = 1; i <= 9; i++)

{

if (paper->cand[i])

{

table[paper->y][paper->x] = i;

solveproblem(paper->next);

table[paper->y][paper->x] = 0;

}

}

}

int main()

{

if (input() == 0){printf("File error"); return 0;}

out = fopen("solution.txt", "wt");

set();

solveproblem(head);

fclose(out);

}

input.txt