動機
学校の授業でmatlabを触る機会があり、そこで数独がすんなり解けたので自分でもソルバを作ってみたくなりました。(matlabは凄いのでぜひ触ってみてください！)
数独とは
数独とは、数字を使ったパズルゲームの一種で、規則に従って9×9のマスに1から9までの数字を並べ、マスを全て埋めるゲームのことである。
数独では3×3のブロックが縦横に3個ずつ並んだ9×9（合計81個）のマスが用いられる。縦横それぞれのマスには1～9までの数字のいずれかが入るが、同じ列に同じ数字を重複して入れることはできない。また、3×3のブロック内でも同じ数字を重複して入れることはできない。
マスのいくつかには、ヒントあるいは制約として、あらかじめ数字が埋められている。この数字が数独を解く上での手がかりとなり、数や配置によって難易度が分かれる。
手法
総当たりで解きました。最大でオーダーN^81(81重ループ)となるため、何も枝切りしない場合永遠に結果が返りませんでした。81重ループの箇所を再帰で再現しました。
そこで、ある数字をあるマスに置く際その行と列とブロックを調査しその数字と同じものが見られたら飛ばすという重複を排除する処理を加えたところすんなり結果が返るようになりました。
遊び方
./
|_sudokuSolver.c
|_/Problems
|_p1.txt(など問題ファイル)
のようなディレクトリ構成にして、
0,2,3,0,0,5,0,6,0
7,0,5,0,2,0,9,0,0
0,0,0,0,7,0,0,0,4
5,8,0,0,0,0,3,0,9
0,0,0,0,0,0,0,0,0
6,0,2,0,1,0,5,0,0
0,0,0,2,9,0,0,0,0
2,3,7,0,0,8,0,0,0
0,4,1,0,0,0,0,0,0
のような問題ファイルの形式にしてください。空欄は0で表現しています。その後コンパイルして実行してみてください！
コード
170行ほどになるので折りたたんでます。
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define N 9
int judge();
void error(int);
void makeOriginalTable();
void makeUseTable();
void show();
void solve();
void makeCheckArray();
int checkCheckArray();
void saiki(int);
int isDuplicate(int, int);
int originalTable[N][N];
int useTable[N][N];
int check[N + 1];
char *problemFilePath = "./Problems/p3.txt";
int main()
{
clock_t c_start, c_end;
c_start = clock();
solve();
c_end = clock();
printf("%f\n", (double)(c_end - c_start) / CLOCKS_PER_SEC);
return 0;
}
int judge()
{
int i, j, k, l;
makeCheckArray();
// block
for (i = 0; i < N; i += 3)
{
for (j = 0; j < N; j += 3)
{
makeCheckArray();
for (k = i; k < i + (N / 3); k++)
for (l = j; l < j + (N / 3); l++)
check[useTable[k][l]]--;
if (checkCheckArray() == 0)
return 0;
}
}
// row
for (i = 0; i < N; i++)
{
makeCheckArray();
for (j = 0; j < N; j++)
{
check[useTable[i][j]]--;
}
if (checkCheckArray() == 0)
return 0;
}
// column
for (i = 0; i < N; i++)
{
makeCheckArray();
for (j = 0; j < N; j++)
{
check[useTable[j][i]]--;
}
if (checkCheckArray() == 0)
return 0;
}
return 1;
}
void error(int num)
{
switch (num)
{
case 0:
{
printf("init(): fp == NULL");
exit(0);
break;
}
case 1:
{
printf("init(): buf == EOF");
exit(1);
break;
}
default:
break;
}
}
void makeOriginalTable()
{
FILE *fp = fopen(problemFilePath, "r");
char buf;
int i, j;
if (fp == NULL)
error(0);
for (i = 0; i < N; i++)
{
for (j = 0; j < N; j++)
{
fscanf(fp, "%c,", &buf);
if (buf == ',' || buf == '\n')
{
j--;
continue;
}
originalTable[i][j] = atoi(&buf);
}
}
}
void makeUseTable()
{
for (int i = 0; i < N; i++)
for (int j = 0; j < N; j++)
useTable[i][j] = originalTable[i][j];
}
void show()
{
for (int i = 0; i < N; i++)
{
if (i % (N / 3) == 0)
printf(" - - - - - - - - - \n");
for (int j = 0; j < N; j++)
{
if (j % (N / 3) == 0)
printf("| ");
printf("%d ", useTable[i][j]);
}
printf("|\n");
}
printf(" - - - - - - - - - \n\n");
}
void solve()
{
makeOriginalTable();
makeUseTable();
saiki(0);
}
void makeCheckArray()
{
check[0] = 0; // 0は各ブロック各列各行に0個でいてほしい
for (int i = 1; i < N + 1; i++)
check[i] = 1;
}
int checkCheckArray()
{
for (int i = 0; i < N; i++)
{
if (check[i] != 0)
return 0; //
}
return 1;
}
void saiki(int num)
{
int r = num / N, c = num % N, i;
if (num >= N * N)
return;
if (originalTable[r][c] != 0)
{
saiki(num + 1);
return;
}
while (useTable[r][c] < N)
{
if (isDuplicate(num, ++useTable[r][c]))
continue;
if (judge() == 1)
{
show();
return;
}
saiki(num + 1);
}
useTable[r][c] = originalTable[r][c];
}
int isDuplicate(int place, int num)
{
int r = place / N, c = place % N, i, j, cnt = 0;
for (i = 0; i < N; i++)
{
if (useTable[r][i] == num)
cnt++;
}
if (cnt != 1)
return 1;
cnt = 0;
for (i = 0; i < N; i++)
{
if (useTable[i][c] == num)
cnt++;
}
if (cnt != 1)
return 1;
cnt = 0;
while ((r--) % (N / 3) != 0)
;
while ((c--) % (N / 3) != 0)
;
r++;
c++;
for (i = r; i < (r + (N / 3)); i++)
{
for (j = c; j < (c + (N / 3)); j++)
{
if (useTable[i][j] == num)
cnt++;
}
}
if (cnt != 1)
return 1;
return 0;
}
実行結果
0,4,7,0,5,0,0,0,0
2,0,0,0,8,0,0,4,0
0,0,0,2,0,0,0,0,0
0,8,0,3,0,0,0,5,4
0,0,3,4,0,0,0,7,9
0,0,0,0,0,0,0,0,0
5,0,0,0,0,7,0,2,0
0,0,0,0,0,6,7,9,0
6,0,4,0,0,3,0,0,0
を入力ファイルに据えます。上記コードのmain関数を少し書き換えて3回実行して平均時間を求めました。
> ./a.exe
- - - - - - - - -
| 3 4 7 | 6 5 1 | 9 8 2 |
| 2 6 5 | 7 8 9 | 3 4 1 |
| 9 1 8 | 2 3 4 | 5 6 7 |
- - - - - - - - -
| 7 8 6 | 3 9 2 | 1 5 4 |
| 1 5 3 | 4 6 8 | 2 7 9 |
| 4 9 2 | 1 7 5 | 6 3 8 |
- - - - - - - - -
| 5 3 9 | 8 1 7 | 4 2 6 |
| 8 2 1 | 5 4 6 | 7 9 3 |
| 6 7 4 | 9 2 3 | 8 1 5 |
- - - - - - - - -
0.050000
- - - - - - - - -
| 3 4 7 | 6 5 1 | 9 8 2 |
| 2 6 5 | 7 8 9 | 3 4 1 |
| 9 1 8 | 2 3 4 | 5 6 7 |
- - - - - - - - -
| 7 8 6 | 3 9 2 | 1 5 4 |
| 1 5 3 | 4 6 8 | 2 7 9 |
| 4 9 2 | 1 7 5 | 6 3 8 |
- - - - - - - - -
| 5 3 9 | 8 1 7 | 4 2 6 |
| 8 2 1 | 5 4 6 | 7 9 3 |
| 6 7 4 | 9 2 3 | 8 1 5 |
- - - - - - - - -
0.052000
- - - - - - - - -
| 3 4 7 | 6 5 1 | 9 8 2 |
| 2 6 5 | 7 8 9 | 3 4 1 |
| 9 1 8 | 2 3 4 | 5 6 7 |
- - - - - - - - -
| 7 8 6 | 3 9 2 | 1 5 4 |
| 1 5 3 | 4 6 8 | 2 7 9 |
| 4 9 2 | 1 7 5 | 6 3 8 |
- - - - - - - - -
| 5 3 9 | 8 1 7 | 4 2 6 |
| 8 2 1 | 5 4 6 | 7 9 3 |
| 6 7 4 | 9 2 3 | 8 1 5 |
- - - - - - - - -
0.056000
0.052667
振り返り
二日かかりました。81重ループみたいなちょっと無理そうな処理も再帰で簡単に書くことができたので楽しかったです。これを思いつくのに時間がかかりました...。平均実行時間は5msとなりました。この方は0.1msより短い時間で解いていました。ビット操作などを用いているようです！参考にしつつ高速化していきたいです。
因みにmatlabでは整数計画法や最適化などよくわかりませんが高速化処理が盛りだくさん使われていてすごかったです。