|
［ 簡単な説明 ］
「数独」と呼ばれるパズルを解くプログラム例です。 |
（トップに戻る）
/* sudoku.c */
#include <stdio.h>
#include <stdlib.h>
/*
#define CROSS /* 対角要素の制限を付加するオプション */
*/
#define N 1
void printmatrix(void);
int datain(int mn, int point);
void determine(void);
void printans(int mn, int *ans);
void save(int *rs, int *cs, int *vs);
int assume(int *i, int *j, int *rr, int *cc, int rs, int cs, int vs);
void nestup(int *rk, int i, int j, int rr, int cc, int v, int *cs, int *vs);
void nestdown(int *rk, int *rs, int *cs, int *vs);
void load(int rk);
int data[N][81] = {
/*
{ 0,0,4, 5,0,0, 0,8,0, 0,3,0, 0,6,0, 7,0,4, 0,2,0, 0,7,8, 0,5,0,
1,0,0, 0,0,0, 4,0,0, 9,8,7, 0,0,0, 5,6,0, 0,0,6, 0,0,0, 0,0,7,
0,0,3, 6,5,0, 0,0,8, 0,0,0, 0,4,0, 1,9,0, 0,0,0, 0,3,2, 0,0,0},
{ 0,0,4, 5,0,7, 8,0,0, 0,3,0, 0,6,0, 0,9,0, 0,2,0, 8,0,4, 0,1,0,
1,0,0, 0,5,0, 0,0,2, 0,0,0, 0,0,0, 0,0,0, 5,4,0, 0,2,0, 0,7,6,
0,6,0, 0,0,0, 0,5,0, 0,7,9, 0,1,0, 2,4,0, 0,0,8, 9,0,2, 3,0,0}
/*
{ 0,6,0, 2,0,4, 0,5,0, 4,7,0, 0,6,0, 0,8,3, 0,0,5, 0,7,0, 1,0,0,
9,0,0, 1,0,3, 0,0,2, 0,1,2, 0,0,0, 3,4,0, 6,0,0, 7,0,9, 0,0,8,
0,0,6, 0,8,0, 7,0,0, 1,4,0, 0,9,0, 0,2,5, 0,8,0, 3,0,5, 0,9,0},
{ 0,0,0, 3,0,0, 0,1,0, 0,9,4, 0,0,1, 0,0,7, 2,0,0, 7,0,0, 4,0,0,
0,0,0, 0,5,0, 3,0,0, 5,8,0, 0,0,0, 0,6,9, 0,0,3, 0,8,0, 0,0,0,
0,0,7, 0,0,5, 0,0,6, 6,0,0, 4,0,0, 2,8,0, 0,1,0, 0,0,6, 0,0,0},
{ 0,0,3, 0,4,0, 8,0,0, 0,0,0, 1,0,9, 0,0,0, 2,0,9, 0,0,0, 3,0,7,
0,5,0, 0,0,0, 0,4,0, 8,0,0, 0,2,0, 0,0,9, 0,1,0, 0,0,0, 0,6,0,
5,0,1, 0,0,0, 4,0,6, 0,0,0, 2,0,5, 0,0,0, 0,0,6, 0,8,0, 7,0,0},
*/
{ 0,2,0, 0,7,5, 0,1,0, 1,0,0, 0,0,4, 5,0,8, 0,5,6, 8,0,0, 2,0,0,
8,1,0, 0,0,0, 7,0,0, 9,0,0, 0,0,0, 0,0,3, 0,0,2, 0,0,0, 0,4,5,
0,0,9, 0,0,1, 4,3,0, 3,0,1, 7,0,0, 0,0,9, 0,7,0, 3,9,0, 0,2,0}
/*
{ 0,0,1, 0,0,0, 8,0,0, 0,2,0, 0,1,0, 0,7,0, 3,0,0, 0,2,0, 0,0,6,
0,0,2, 0,3,0, 7,0,0, 4,0,0, 2,0,7, 0,0,5, 0,0,0, 0,6,0, 0,0,0,
5,0,0, 0,7,0, 0,0,4, 0,6,0, 0,8,0, 0,3,0, 0,0,7, 6,0,3, 2,0,0}
*/
};
static int nstack = 50;
int cq, rq, iq, jq;
int ds, dss;
int D[10], R[9], C[9], Mat[3][3];
int AR[9], AC[9], AM[3][3];
int V[9][9];
int AV[9][9];
int *RS, *CS, *VS;
#ifdef CROSS
int X1, X2, AX1, AX2;
#endif
void printmatrix(void)
{
int i, j, k;
for(j = 0; j < 3; j++)
{
printf("+");
for(k = 0; k < 3; k++) printf("---");
}
printf("+\n");
for(i = 0; i < 9;)
{
printf("|");
for(j = 0; j < 9;)
{
printf("%2d ", V[i][j]);
if(++j % 3 == 0) printf("|");
}
printf("\n");
if(++i % 3 == 0)
{
for(j = 0; j < 3; j++)
{
printf("+");
for(k = 0; k < 3; k++) printf("---");
}
printf("+\n");
}
}
}
void printans(int mn, int *ans)
{
printf("*** answer %d - %d ***\n", mn, (*ans)++);
printmatrix();
}
int datain(int mn, int point)
{
int c, i, ii, j, jj, p, r, s, v;
p = 0;
if(point >= N) return 0;
for(i = 0; i < 9; i++) R[i] = C[i] = 511;
for(i = 0; i < 3; i++) for(j = 0; j < 3; j++) Mat[i][j] = 511;
#ifdef CROSS
X1 = X2 = 511;
#endif
ds = r = 0;
for(i = 0; i < 3; i++)
{
for(ii = 0; ii < 3; ii++, r++)
{
c = 0;
for(j = 0; j < 3; j++)
{
for(jj = 0; jj < 3; jj++, c++)
{
V[r][c] = v = data[point][p++];
if(v == 0) continue;
ds++;
s = D[v];
R[r] -= s;
C[c] -= s;
Mat[i][j] -= s;
}
}
}
}
#ifdef CROSS
for(p = 0; p < 9; p++)
{
if(V[p][p]) X1 -= D[V[p][p]];
if(V[p][9 - p]) X2 -= D[V[p][9 - p]];
}
#endif
printf("*** problem %d ***\n", mn);
printmatrix();
return 1;
}
void determine(void)
{
int rc, rm, cc, cm, mm, mr, s;
int c, f, i, ii, j, jj, nc, r, v;
do
{
f = 0;
for(v = 1; v <= 9; v++)
{
s = D[v];
#ifdef CROSS
if(X1 == s)
{
f++;
for(r = 0; r < 9; r++)
{
if(V[r][r]) continue;
V[r][r] = v;
R[r / 3] -= s;
C[r / 3] -= s;
Mat[r / 3][r / 3] -= s;
break;
}
}
if(X2 == s)
{
f++;
for(r = 0; r < 9; r++)
{
c = 9 - r;
if(V[r][c]) continue;
V[r][c] = v;
R[r / 3] -= s;
C[c / 3] -= s;
Mat[r / 3][c / 3] -= s;
break;
}
}
#endif
r = 0;
for(i = 0; i < 3; i++)
{
for(ii = 0; ii < 3; ii++, r++)
{
rc = R[r];
if((rc & s) == 0) continue;
nc = 0;
for(j = 0; j < 3; j++)
{
if((s & Mat[i][j]) == 0) continue;
c = j * 3;
rm = rc & Mat[i][j];
for(jj = 0; jj < 3; jj++, c++)
{
if(V[r][c] > 0 || (s & C[c]) == 0) continue;
if((s ^ (rm & C[c])) == 0)
{
nc = 1;
cq = c;
jq = j;
goto next1;
}
nc++;
if(nc == 1)
{
cq = c;
jq = j;
}
}
}
next1: if(nc == 1)
{
f++;
V[r][cq] = v;
R[r] -= s;
C[cq] -= s;
Mat[i][jq] -= s;
#ifdef CROSS
if(r == cq) X1 -= s;
if(r == 3 - cq) X2 -= s;
#endif
}
}
}
c = 0;
for(j = 0; j < 3; j++)
{
for(jj = 0; jj < 3; jj++, c++)
{
cc = C[c];
if((cc & s) == 0) continue;
nc = 0;
for(i = 0; i < 3; i++)
{
if((s & Mat[i][j]) == 0) continue;
r = i * 3;
cm = cc & Mat[i][j];
for(ii = 0; ii < 3; ii++, r++)
{
if(V[r][c] > 0 || (s & R[r]) == 0) continue;
if((s ^ (cm & R[r])) == 0)
{
nc = 1;
rq = r;
iq = i;
goto next2;
}
nc++;
if(nc == 1)
{
rq = r;
iq = i;
}
}
}
next2: if(nc == 1)
{
f++;
V[rq][c] = v;
R[rq] -= s;
C[c] -= s;
Mat[iq][j] -= s;
#ifdef CROSS
if(rq == c) X1 -= s;
if(rq == 3 - c) X2 -= s;
#endif
}
}
}
for(i = 0; i < 3; i++)
{
for(j = 0; j < 3; j++)
{
if((Mat[i][j] & s) == 0) continue;
nc = 0;
r = i * 3;
mm = Mat[i][j];
for(ii = 0; ii < 3; ii++, r++)
{
if((R[r] & s) == 0) continue;
c = j * 3;
mr = mm & R[r];
for(jj = 0; jj < 3; jj++, c++)
{
if(V[r][c] > 0 || (s & C[c]) == 0) continue;
if((s ^ (mr & C[c])) == 0)
{
nc = 1;
rq = r;
cq = c;
goto next3;
}
nc++;
if(nc == 1)
{
rq = r;
cq = c;
}
}
}
next3: if(nc == 1)
{
f++;
V[rq][cq] = v;
R[rq] -= s;
C[cq] -= s;
Mat[i][j] -= s;
#ifdef CROSS
if(rq == cq) X1 -= s;
if(rq == 3 - cq) X2 -= s;
#endif
}
}
}
}
ds += f;
#ifdef CROSS
}while(ds < 83 && f > 0);
#else
}while(ds < 81 && f > 0);
#endif
}
void save(int *rs, int *cs, int *vs)
{
int c, r;
dss = ds;
*rs = *cs = *vs = 0;
for(r = 0; r < 9; r++)
{
AR[r] = R[r];
AC[r] = C[r];
for(c = 0; c < 9; c++) AV[r][c] = V[r][c];
}
for(r = 0; r < 3; r++) for(c = 0; c < 3; c++) AM[r][c] = Mat[r][c];
#ifdef CROSS
AX1 = X1;
AX2 = X2;
#endif
}
int assume(int *i, int *j, int *rr, int *cc, int rs, int cs, int vs)
{
int rmc;
int c, k, r;
for(r = rs; r < 9; r++)
{
for(c = cs; c < 9; c++)
{
if(V[r][c] > 0) cs = vs = 0;
else
{
*i = r / 3;
*j = c / 3;
rmc = (R[r] & C[c]) & Mat[*i][*j];
for(k = vs + 1; k <= 9; k++)
{
if((D[k] & rmc) > 0)
{
*rr = r + 1;
*cc = c + 1;
return k;
}
}
return 0;
}
}
}
return 0;
}
void nestup(int *rk, int i, int j, int rr, int cc, int v, int *cs, int *vs)
{
int s;
int *wc, *wr, *wv;
int k, n;
(*rk)++;
if(*rk >= nstack)
{
n = nstack + 20;
wr = (int *)malloc(n * sizeof(int *));
wc = (int *)malloc(n * sizeof(int *));
wv = (int *)malloc(n * sizeof(int *));
if(wr == NULL || wc == NULL || wv == NULL)
{
fprintf(stderr, "Error : memory allocation error.\n");
exit(-1);
}
for(k = 0; k < nstack; k++)
{
wr[k] = RS[k];
wc[k] = CS[k];
wv[k] = VS[k];
}
free((char *)RS);
free((char *)CS);
free((char *)VS);
RS = wr;
CS = wc;
VS = wv;
nstack = n;
}
RS[*rk] = rr;
CS[*rk] = cc;
VS[*rk] = v;
ds++;
V[rr-1][cc-1] = v;
s = D[v];
R[rr-1] -= s;
C[cc-1] -= s;
Mat[i][j] -= s;
(*cs)++;
*vs = 0;
}
void nestdown(int *rk, int *rs, int *cs, int *vs)
{
*rs = RS[*rk] - 1;
*cs = CS[*rk] - 1;
*vs = VS[*rk];
(*rk)--;
}
void load(int rk)
{
int s;
int c, k, r, v;
ds = dss;
for(r = 0; r < 9; r++)
{
R[r] = AR[r];
C[r] = AC[r];
for(c = 0; c < 9; c++) V[r][c] = AV[r][c];
}
for(r = 0; r < 3; r++) for(c = 0; c < 3; c++) Mat[r][c] = AM[r][c];
for(k = 0; k <= rk; k++)
{
r = RS[k]-1;
c = CS[k]-1;
v = VS[k];
ds++;
V[r][c] = v;
s = D[v];
R[r] -= s;
C[c] -= s;
Mat[r / 3][c / 3] -= s;
}
#ifdef CROSS
X1 = AX1;
X2 = AX2;
#endif
determine();
}
int main(void)
{
int jj;
int mn = 1, ans = 1, point = 0;
int i, j, rk, rr, cc, v;
int rs, cs, vs;
RS = (int *)malloc(nstack * sizeof(int));
CS = (int *)malloc(nstack * sizeof(int));
VS = (int *)malloc(nstack * sizeof(int));
if(RS == NULL || CS == NULL || VS == NULL)
{
fprintf(stderr, "Error : memory allocation error.\n");
exit(-1);
}
jj = 1;
for(i = 1; i <= 9; i++)
{
D[i] = jj;
jj *= 2;
}
while(datain(mn, point++))
{
ans = 1;
determine();
#ifdef CROSS
if(ds >= 83) printans(mn, &ans);
#else
if(ds >= 81) printans(mn, &ans);
#endif
else
{
save(&rs, &cs, &vs);
rk = -1;
while(1)
{
while(1)
{
v = assume(&i, &j, &rr, &cc, rs, cs, vs);
if(v == 0) break;
nestup(&rk, i, j, rr, cc, v, &cs, &vs);
determine();
#ifdef CROSS
if(ds >= 83)
#else
if(ds >= 81)
#endif
{
printans(mn, &ans);
break;
}
}
if(rk == -1) break;
nestdown(&rk, &rs, &cs, &vs);
load(rk);
}
}
mn++;
}
return 1;
}
|
（トップに戻る）
*** problem 1 *** +---------+---------+---------+ | 0 6 0 | 2 0 4 | 0 5 0 | | 4 7 0 | 0 6 0 | 0 8 3 | | 0 0 5 | 0 7 0 | 1 0 0 | +---------+---------+---------+ | 9 0 0 | 1 0 3 | 0 0 2 | | 0 1 2 | 0 0 0 | 3 4 0 | | 6 0 0 | 7 0 9 | 0 0 8 | +---------+---------+---------+ | 0 0 6 | 0 8 0 | 7 0 0 | | 1 4 0 | 0 9 0 | 0 2 5 | | 0 8 0 | 3 0 5 | 0 9 0 | +---------+---------+---------+ *** answer 1 - 1 *** +---------+---------+---------+ | 8 6 1 | 2 3 4 | 9 5 7 | | 4 7 9 | 5 6 1 | 2 8 3 | | 3 2 5 | 9 7 8 | 1 6 4 | +---------+---------+---------+ | 9 5 8 | 1 4 3 | 6 7 2 | | 7 1 2 | 8 5 6 | 3 4 9 | | 6 3 4 | 7 2 9 | 5 1 8 | +---------+---------+---------+ | 5 9 6 | 4 8 2 | 7 3 1 | | 1 4 3 | 6 9 7 | 8 2 5 | | 2 8 7 | 3 1 5 | 4 9 6 | +---------+---------+---------+ |
（トップに戻る）
*** problem 2 *** +---------+---------+---------+ | 0 0 0 | 3 0 0 | 0 1 0 | | 0 9 4 | 0 0 1 | 0 0 7 | | 2 0 0 | 7 0 0 | 4 0 0 | +---------+---------+---------+ | 0 0 0 | 0 5 0 | 3 0 0 | | 5 8 0 | 0 0 0 | 0 6 9 | | 0 0 3 | 0 8 0 | 0 0 0 | +---------+---------+---------+ | 0 0 7 | 0 0 5 | 0 0 6 | | 6 0 0 | 4 0 0 | 2 8 0 | | 0 1 0 | 0 0 6 | 0 0 0 | +---------+---------+---------+ *** answer 2 - 1 *** +---------+---------+---------+ | 7 6 5 | 3 4 9 | 8 1 2 | | 8 9 4 | 5 2 1 | 6 3 7 | | 2 3 1 | 7 6 8 | 4 9 5 | +---------+---------+---------+ | 1 4 6 | 9 5 7 | 3 2 8 | | 5 8 2 | 1 3 4 | 7 6 9 | | 9 7 3 | 6 8 2 | 1 5 4 | +---------+---------+---------+ | 3 2 7 | 8 1 5 | 9 4 6 | | 6 5 9 | 4 7 3 | 2 8 1 | | 4 1 8 | 2 9 6 | 5 7 3 | +---------+---------+---------+ |
（トップに戻る）
*** problem 3 *** +---------+---------+---------+ | 0 0 3 | 0 4 0 | 8 0 0 | | 0 0 0 | 1 0 9 | 0 0 0 | | 2 0 9 | 0 0 0 | 3 0 7 | +---------+---------+---------+ | 0 5 0 | 0 0 0 | 0 4 0 | | 8 0 0 | 0 2 0 | 0 0 9 | | 0 1 0 | 0 0 0 | 0 6 0 | +---------+---------+---------+ | 5 0 1 | 0 0 0 | 4 0 6 | | 0 0 0 | 2 0 5 | 0 0 0 | | 0 0 6 | 0 8 0 | 7 0 0 | +---------+---------+---------+ *** answer 3 - 1 *** +---------+---------+---------+ | 1 6 3 | 7 4 2 | 8 9 5 | | 7 8 5 | 1 3 9 | 6 2 4 | | 2 4 9 | 6 5 8 | 3 1 7 | +---------+---------+---------+ | 6 5 7 | 9 1 3 | 2 4 8 | | 8 3 4 | 5 2 6 | 1 7 9 | | 9 1 2 | 8 7 4 | 5 6 3 | +---------+---------+---------+ | 5 2 1 | 3 9 7 | 4 8 6 | | 4 7 8 | 2 6 5 | 9 3 1 | | 3 9 6 | 4 8 1 | 7 5 2 | +---------+---------+---------+ |
（トップに戻る）
*** problem 4 *** +---------+---------+---------+ | 0 2 0 | 0 7 5 | 0 1 0 | | 1 0 0 | 0 0 4 | 5 0 8 | | 0 5 6 | 8 0 0 | 2 0 0 | +---------+---------+---------+ | 8 1 0 | 0 0 0 | 7 0 0 | | 9 0 0 | 0 0 0 | 0 0 3 | | 0 0 2 | 0 0 0 | 0 4 5 | +---------+---------+---------+ | 0 0 9 | 0 0 1 | 4 3 0 | | 3 0 1 | 7 0 0 | 0 0 9 | | 0 7 0 | 3 9 0 | 0 2 0 | +---------+---------+---------+ *** answer 4 - 1 *** +---------+---------+---------+ | 4 2 8 | 9 7 5 | 3 1 6 | | 1 9 3 | 2 6 4 | 5 7 8 | | 7 5 6 | 8 1 3 | 2 9 4 | +---------+---------+---------+ | 8 1 5 | 4 3 9 | 7 6 2 | | 9 4 7 | 5 2 6 | 1 8 3 | | 6 3 2 | 1 8 7 | 9 4 5 | +---------+---------+---------+ | 2 8 9 | 6 5 1 | 4 3 7 | | 3 6 1 | 7 4 2 | 8 5 9 | | 5 7 4 | 3 9 8 | 6 2 1 | +---------+---------+---------+ *** answer 4 - 2 *** +---------+---------+---------+ | 4 2 8 | 9 7 5 | 3 1 6 | | 1 9 3 | 6 2 4 | 5 7 8 | | 7 5 6 | 8 1 3 | 2 9 4 | +---------+---------+---------+ | 8 1 5 | 4 3 9 | 7 6 2 | | 9 4 7 | 2 5 6 | 1 8 3 | | 6 3 2 | 1 8 7 | 9 4 5 | +---------+---------+---------+ | 2 8 9 | 5 6 1 | 4 3 7 | | 3 6 1 | 7 4 2 | 8 5 9 | | 5 7 4 | 3 9 8 | 6 2 1 | +---------+---------+---------+ |
（トップに戻る）
| sudoku.c | 確定サーチを用いて数独を解くプログラム （メインルーチン） |
| disp.c | 数独の表示ルーチン |
| conio.c | 表示の低レベルルーチン |
/* file = sudoku2.c * * 【使用法】 * * A>SUDOKU2 入力ファイル名 * * 各数値を足し合わせた数を指定することにより、それぞれの動作をあわ * 行います。このフラグを省略した場合は、７が指定されたものとみまします。 * （すべての確定サーチを行う） * * 入力ファイルのフォーマットは、問題の空欄を０として、数字を並べるだけ * です。例として問題３を挙げておきます。 * * * A>TYPE MONDAI3.INP * 0 0 1 0 0 0 6 0 0 * 0 8 0 2 0 6 0 5 0 * 6 0 0 0 3 0 0 0 1 * 0 9 0 0 0 4 0 7 0 * 0 0 2 0 0 0 5 0 0 * 0 4 0 9 0 0 0 6 0 * 1 0 0 0 8 0 0 0 7 * 0 2 0 7 0 3 0 1 0 * 0 0 9 0 0 0 4 0 0 * * 松田 晋 */ #include <stdio.h> #include <stdlib.h> int col[9], row[9], mas[3][3]; /* 行、列、マスの許容値テーブル */ int bit[] = {0 /* dummy */, 1, 2, 4, 8, 16, 32, 64, 128, 256}; typedef struct masu masu_t; struct masu { masu_t *next; /* 順方向ポインタ */ masu_t *prev; /* 逆方向ポインタ */ char col; /* 列 */ char row; /* 行 */ char num; /* 数字 */ }; masu_t board[9][9], head; void pause(void); void disp_num(int c, int r, int n, int mode); void display_board(void); void usage(void); void flush(void); /* 後始末 */ void sudoku(int n); /* 引数（ひきすう）ｎは残りの空欄の個数 */ int search_f; /* 確定サーチを制御するフラグ */ void set_num(int b, int r, int c, masu_t *p, int f) { p->num = b; /* ボードに数を置く */ row[r] &= ~bit[b]; /* 許容値テーブルのクリア */ col[c] &= ~bit[b]; mas[r / 3][c / 3] &= ~bit[b]; p->prev->next = p->next; /* 双方向リストから */ p->next->prev = p->prev; /* 要素を取り除く */ disp_num(c, r, b, f); /* 数字の表示 */ } /* set_num */ void erase_num(int b, int r, int c, masu_t *p) { p->num = 0; /* ボードをもとに戻す */ row[r] |= bit[b]; /* 許容値テーブルを戻す */ col[c] |= bit[b]; mas[r / 3][c / 3] |= bit[b]; p->prev->next = p; /* 双方向リストを */ p->next->prev = p; /* 元に戻す */ disp_num(c, r, 0, 0); /* 数字をはがす */ } /* erase_num */ void init_pointers(void) { /* ポインタの初期化 */ masu_t *p; for (p = &board[0][0]; p <= &board[8][8]; p++) { p->prev = p - 1; p->next = p + 1; } board[0][0].prev = &head; board[8][8].next = &head; head.next = &board[0][0]; head.prev = &board[8][8]; } /* init_pointers */ void init_table(void) /* 許容値テーブルの初期設定 */ { int i, j; /* 初期状態ではなにを置いても良い */ for (i = 0; i < 9; i++) { col[i] = 0777; /* 行、列の許容値テーブルを */ row[i] = 0777; /* 111111111bで初期設定する */ } for (i = 0; i < 3; i++) for (j = 0; j < 3; j++) mas[i][j] = 0777; /* マスについても同じ */ } /* init_table */ int read_board(FILE *f) /* 問題の読み込みと */ { /* ボード及びテーブルの設定 */ int r, c, b, n; masu_t *p; n = 0; p = &board[0][0]; for (r = 0; r < 9; r++) for (c = 0; c < 9; c++, p++) { p->col = c; p->row = r; fscanf(f, "%d", &b); /* 問題の読み込み */ if (b) /* 読み込んだ数字が０以外ならば */ set_num(b, r, c, p, 0); /* 確定設定 */ else { /* 読み込んだ数字が０ならば */ n++; /* それを数える */ p->num = 0; /* ボードのクリア */ } } return n; /* 戻り値は空欄の個数 */ } /* read_board */ int search_masu(int n) /* 各マスについての確定サーチ */ { int b, r, c, nk; int rr, cc, r_save, c_save; masu_t *p; for (rr = 0; rr < 3; rr++) for (cc = 0; cc < 3; cc++) for (b = 1; b <= 9; b++) if (mas[rr][cc] & bit[b]) { nk = 0; for (r = rr * 3; r < rr * 3 + 3; r++) for (c = cc * 3; c < cc * 3 + 3; c++) if (row[r] & col[c] & bit[b] && board[r][c].num == 0) { nk++; r_save = r; c_save = c; } if (nk == 1) { /* bを置得る場所が１個なら確定 */ p = &board[r_save][c_save]; set_num(b, r_save, c_save, p, 1); /* 確定設定 */ sudoku(n - 1); /* 次のマスを埋める */ erase_num(b, r_save, c_save, p); return 1; } else if (nk == 0) /* 置得る場所が０個なら戻る */ return 1; } return 0; } /* search_masu */ int search_row(int n) /* 各行についての確定サーチ */ { int b, r, c, nk, c_save; masu_t *p; for (r = 0; r < 9; r++) for (b = 1; b <= 9; b++) if (row[r] & bit[b]) { nk = 0; for (c = 0; c < 9; c++) if (col[c] & mas[r / 3][c / 3] & bit[b] && board[r][c].num == 0) { nk++; c_save = c; } if (nk == 1) { /* bを置得る場所が１個なら確定 */ p = &board[r][c_save]; set_num(b, r, c_save, p, 1); /* 確定設定 */ sudoku(n - 1); /* 次のマスを埋める */ erase_num(b, r, c_save, p); return 1; } else if (nk == 0) /* 置得る場所が０個なら戻る */ return 1; } return 0; } /* search_row */ int search_col(int n) /* 各桁についての確定サーチ */ { int b, r, c, nk, r_save; masu_t *p; for (c = 0; c < 9; c++) for (b = 1; b <= 9; b++) if (col[c] & bit[b]) { nk = 0; for (r = 0; r < 9; r++) if (row[r] & mas[r / 3][c / 3] & bit[b] && board[r][c].num == 0) { nk++; r_save = r; } if (nk == 1) { /* bを置得る場所が１個なら確定 */ p = &board[r_save][c]; set_num(b, r_save, c, p, 1); /* 確定設定 */ sudoku(n - 1); /* 次のマスを埋める */ erase_num(b, r_save, c, p); return 1; } else if (nk == 0) /* 置得る場所が０個なら戻る */ return 1; } return 0; } /* search_col */ void sudoku(int n) /* ｎは残りの空欄の個数 */ { int r, c, s, b; masu_t *p; if (n == 0) { /* もう空欄が無ければ、解が求められている */ pause(); return; } /* 確定サーチ */ if ((search_f & 1) && search_masu(n)) return; if ((search_f & 2) && search_row(n)) return; if ((search_f & 4) && search_col(n)) return; /* 以下、バックトラック */ p = head.next; /* 未確定の場所を求める */ r = p->row; c = p->col; /* 許容値テーブルのビット積により、この欄に置ける数の集合を求める */ s = row[r] & col[c] & mas[r / 3][c / 3]; for (b = 1; b <= 9; b++) /* １〜９の各数字について */ if (s & bit[b]) { /* bが未使用であれば */ set_num(b, r, c, p, 2); /* 仮設定 */ sudoku(n - 1); /* バックトラック */ erase_num(b, r, c, p); /* 仮設定を元に戻す */ } } /* sudoku */ int init(int argc, char *argv[]) /* 初期化 */ { /* 空欄の個数を返す */ int n; FILE *f; if (argc < 2) { usage(); exit(1); } f = fopen(argv[1], "r"); if (f == NULL) { fprintf(stderr, "オープン・エラー:%s\n", argv[1]); exit(1); } init_pointers(); /* ポインタの初期設定 */ init_table(); /* 許容値テーブルの初期設定 */ display_board(); /* 数独盤の作成 */ n = read_board(f); /* 入力データの読み込み */ fclose(f); pause(); return n; /* 空欄の個数を返す */ } int main(int argc, char *argv[]) { int n; n = init(argc, argv); /* ｎは空欄の個数 */ if (argc < 3) search_f = 7; else search_f = atoi(argv[2]); sudoku(n); /* ｎ個の空欄を埋める */ flush(); /* 後始末 */ return 0; } /* main */ |
/* file = disp.c * * 目的：数独の表示を行う * * 作成：松田晋 */ #include <stdio.h> void locate(int x, int y); /* カーソルを移動する */ void reverseVideo(void); /* リバース表示 */ void normalVideo(void); /* 通常表示 */ void cls(void); /* 画面消去 */ void bell(void); /* ブザーを鳴らす */ /* 関数 disp_num * * 引数：int c : 列 * int r : 行 * int n : 数字（０は数字が入っていないことを示す） * int mode : 表示フラグ * 0 → 入力データ（ノーマル・全角） * 1 → 確定（リバース・全角） * 2 → 仮設定（リバース・半角） */ void disp_num(int c, int r, int n, int mode) { static char *num_tbl[] = {"０", "１", "２", "３", "４", "５", "６", "７", "８", "９"}; locate(c * 4 + 3, r * 2 + 2); if (mode == 0) normalVideo(); else reverseVideo(); if (n == 0) printf(" "); else if (mode == 2) /* 仮設定の場合は半角表示 */ putchar('0' + n); else /* 確定の場合は全角表示 */ printf(num_tbl[n]); } /* disp_num */ void display_board(void) { cls(); printf("・・・・・・・・・・・・・・・・・・・\n" "・ ・ ・ ・ ・ ・ ・ ・ ・ ・\n" "・・・・・・・・・・・・・・・・・・・\n" "・ ・ ・ ・ ・ ・ ・ ・ ・ ・\n" "・・・・・・・・・・・・・・・・・・・\n" "・ ・ ・ ・ ・ ・ ・ ・ ・ ・\n" "・・・・・・・・・・・・・・・・・・・\n" "・ ・ ・ ・ ・ ・ ・ ・ ・ ・\n" "・・・・・・・・・・・・・・・・・・・\n" "・ ・ ・ ・ ・ ・ ・ ・ ・ ・\n" "・・・・・・・・・・・・・・・・・・・\n" "・ ・ ・ ・ ・ ・ ・ ・ ・ ・\n" "・・・・・・・・・・・・・・・・・・・\n" "・ ・ ・ ・ ・ ・ ・ ・ ・ ・\n" "・・・・・・・・・・・・・・・・・・・\n" "・ ・ ・ ・ ・ ・ ・ ・ ・ ・\n" "・・・・・・・・・・・・・・・・・・・\n" "・ ・ ・ ・ ・ ・ ・ ・ ・ ・\n" "・・・・・・・・・・・・・・・・・・・\n"); } /* display_board */ void usage(void) { fprintf(stderr, "使用法：SUDOKU 入力ファイル名 ［確定サーチフラグ］\n" "\n" "確定サーチフラグは、０〜７の数値で、" "下記のように設定します。\n" "\n" "\bit１ ＝ 各マスについて、確定サーチを行う。\n" "\bit２ ＝ 各列について、確定サーチを行う。\n" "\bit４ ＝ 各桁について、確定サーチを行う。\n" "\n" " 各数値を足し合わせた数を指定することにより、" "それぞれの動作をあわせて\n" "行います。このフラグを省略した場合は、" "７が指定されたものとみまします。\n" "（すべての確定サーチを行う）\n"); } void pause(void) { normalVideo(); locate(1, 23); printf("Hit return key!"); bell(); (void) getchar(); locate(1, 23); printf(" "); } /* pause */ void flush(void) /* 後始末 */ { locate(3, 24); reverseVideo(); printf("＝＝＝＝探索終了＝＝＝＝"); normalVideo(); } |
/* file = conio.c * * 目的：表示の低レベルルーチン * ＡＮＳＩエスケープシーケンス利用 * * 作成：松田晋 */ #include <stdio.h> #include <stdlib.h> #include <conio.h> void locate(int x, int y) /* カーソルを移動する */ { printf("\033[%d;%dH", y, x); } void reverseVideo(void) /* リバース表示 */ { printf("\033[7m"); } /* reverseVideo */ void normalVideo(void) /* 通常表示 */ { printf("\033[m"); } /* normalVideo */ void cls(void) /* 画面消去 */ { printf("\033[2J"); } void bell(void) /* ブザーを鳴らす */ { putchar('\007'); } |
（トップに戻る）
戻る（メインメニュー）
戻る（その他メニュー）
注意事項