|
|
> No.4090[元記事へ]
匿名希望さんへのお返事です。
> 現在パソコンで数独の問題を解く場合再帰用法のプログラムを
> 使っているようです。この場合9×9以外に16×16や25×25
> の場合などもすべて完全に解けるのでしょうか。
> それとも特殊な場合にのみ解けるのでしょうか。
> よろしくお願いします。
山中氏のプログラムちょっといじってみました。
PUBLIC NUMERIC N,N1
!'RESTORE 1
RESTORE 2
!'RESTORE 3
READ N1
LET N=N1*N1
DIM M(0 TO N-1,0 TO N-1)
MAT READ M
CALL BACKTRACK(M,0)
1 DATA 3
DATA 4,1,0,0,0,8,0,7,0
DATA 0,0,2,0,0,9,1,0,5
DATA 7,8,9,0,0,0,3,6,4
DATA 0,0,0,0,4,1,7,0,0
DATA 1,0,8,0,5,6,0,2,9
DATA 0,7,0,9,8,0,6,0,0
DATA 2,0,7,0,0,4,8,0,3
DATA 0,4,3,0,9,0,2,1,0
DATA 6,0,0,0,2,0,5,0,7
2 DATA 4
DATA 1, 0, 2, 0, 0,14, 5,13, 0,10, 0, 0, 0,11, 0, 0
DATA 0, 0,16, 0, 0, 0, 0, 7, 0,11,14, 6, 0, 0,13,10
DATA 15,11, 0, 0, 0, 6, 0, 1, 2, 0, 0, 0, 8, 0, 0,12
DATA 6, 0, 0,12, 0, 0, 0, 8, 4, 0, 7, 9, 0, 0, 0, 3
DATA 0, 0, 0, 9, 2, 1, 0, 0,12,14, 0, 0, 7, 6, 0, 0
DATA 5,13, 1, 0, 0, 0,16, 6, 0, 3,15, 4, 0, 8, 0,11
DATA 10, 2, 0, 0,13, 5, 3, 0, 0, 0, 0, 7, 0,15,16, 0
DATA 0, 0,15, 0,14, 0, 4,11, 0, 1, 6, 2,10, 0, 0, 0
DATA 16,10, 0, 0, 8, 7, 0, 0, 0,12, 0, 0, 0, 0, 0, 0
DATA 0, 0, 0, 0,12, 0,14, 0,13, 0,16, 0, 0, 0, 5, 0
DATA 0, 7, 6,11, 0,15, 2, 0, 0, 0, 8, 0, 4, 0, 0, 0
DATA 3,15, 0, 4,11,13, 0, 0, 5, 0, 0, 0, 9, 1, 0, 0
DATA 0, 1, 0, 2, 0,11, 0, 4, 0, 0,10, 0, 0, 5,14,16
DATA 0, 0,10, 0, 1,12, 0, 0,14,13, 0,16, 0, 7, 6, 0
DATA 0, 0,14, 0, 0, 0, 7,10, 9, 0, 0,15, 1, 0, 0, 0
DATA 0, 6, 0, 8, 0, 0,13, 0, 0, 4, 0, 3, 2, 0, 0,15
3 DATA 5
DATA 12, 4, 0,16, 0, 0,13, 1,22, 0, 0, 0, 0, 0,17,20,21,14,15, 0,10,19, 0, 0,11
DATA 21,18,20,22, 7, 9,11, 0,16, 3,15, 0, 0, 1,13,10, 0, 4,24, 0, 8, 0, 0,23, 0
DATA 14, 1,15, 9, 0, 0,23, 0, 0, 0, 3,18,10, 0, 0, 0, 0, 0, 0, 5, 0,13,16, 0,24
DATA 0,13,24, 0, 0, 0,21, 4,25, 6, 0, 0,11, 0,22,18,19, 1, 0, 3, 0, 0,0 ,20, 0
DATA 0, 0,11, 0, 0,18,10, 0,15,19, 0,20,24, 0, 0, 0,13, 0, 0, 0, 1,22, 3,12, 0
DATA 1,14, 0, 3, 0, 4, 7, 0, 0, 0,13,10, 0,19,20,24,11, 5, 0,21, 0,18,22,17, 0
DATA 0,20,22,11, 0, 0, 0,16,10, 0, 7,21, 0, 0,23, 0, 1, 9, 0, 0,13, 5, 0,14, 3
DATA 19,24, 7,23, 0,14, 0,20,11, 5, 0, 0, 0, 0, 0,13,18, 0, 3,22, 0, 1, 0,10, 0
DATA 0, 0,25, 0, 0,15,19,13, 0,22, 1, 3,18, 0, 0, 0,14, 0,12, 0, 0,23,11,24,20
DATA 10, 0, 0, 0,13, 0, 6, 3, 1,18,22, 0, 0, 0,24, 0,25, 0, 0,23,19, 0, 7, 2, 0
DATA 16, 6,19,18, 0, 0,22, 0, 0,24,20,23, 3, 0, 0, 7, 0,11,10, 1, 0, 0,13, 0, 8
DATA 0, 0,13, 1, 0,10, 3,11,14,20,16, 0, 0, 0,21,19, 9,24,22,18, 0, 0, 0, 0,23
DATA 15, 0,12, 0,24, 1, 0,23, 0, 7,18,22,13, 0, 0, 0, 0, 0, 4, 0, 3,14,19, 0, 0
DATA 0, 3, 0, 4, 0, 0, 0,15, 0, 0, 0, 0, 1, 0, 0,14, 0,13, 6, 0,18, 0,24,22,21
DATA 22, 0, 0,20,14,19,18, 0, 0, 0, 0, 0, 0,24, 0,21, 3, 0, 0, 0,11,10, 1, 0, 0
DATA 13, 0, 6, 0, 0,23, 5,24, 0,15, 0, 0,20, 0, 0, 0, 0,22,18,11, 0, 0, 0, 3, 1
DATA 24,11, 5, 0, 3, 0,20,18, 0,13, 0, 1,22,12, 0,15, 0, 0,21, 0, 0, 0, 0, 4,10
DATA 0,23, 1, 0,18, 0, 0, 0, 0, 0,24, 0, 0, 0, 0, 3, 0,12, 0, 0,22, 0, 0, 0,19
DATA 0, 0, 0, 7, 0,16, 0,22,19, 0, 0, 0, 0,11, 3, 0,24, 0, 1, 0,20, 0, 0, 0,13
DATA 4,15, 0, 0,22, 3, 0,21, 0, 1, 0, 0, 0,18, 6, 0,10, 0, 0,20,24, 7,17,11, 0
DATA 6, 0,21, 0, 0, 0, 0, 0,18,11, 0,14, 0,23, 1, 0,20, 3, 0,19, 0,24, 4, 0,22
DATA 11, 0,18,13,20, 0, 0, 0,24,14, 0, 0, 0, 3, 0, 1, 0,10, 0, 4, 0, 0, 0,15, 0
DATA 3,16, 4,24, 0,22, 0, 0, 0, 0, 0,13, 0, 0,10, 0,23,18, 0, 0, 0,21, 0,19,25
DATA 23, 7, 0, 0, 0,20, 0,10, 3,21, 6,24, 0,22, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1,18
DATA 0,22,14, 0, 1,13,15,19,23, 0,11,16, 0,20, 0, 9, 0,21, 0, 0, 0, 3,10, 0,12
END
EXTERNAL SUB BACKTRACK(M(,),P)
IF P<N*N THEN
LET ROW=INT(P/N)
LET COL=MOD(P,N)
IF M(ROW,COL)<>0 THEN
CALL BACKTRACK(M,P+1)
ELSE
FOR K=1 TO N
IF CHECKRULE(M,ROW,COL,K)=1 THEN
LET M(ROW,COL)=K
CALL BACKTRACK(M,P+1)
LET M(ROW,COL)=0
END IF
NEXT K
END IF
ELSE
FOR I=0 TO N-1
FOR J=0 TO N-1
PRINT USING "###":M(I,J);
IF MOD(J+1,N1)=0 THEN PRINT "|";
NEXT J
PRINT
IF MOD(I+1,N1)=0 THEN PRINT REPEAT$("-",3*N+N1)
NEXT I
PRINT
END IF
END SUB
EXTERNAL FUNCTION CHECKRULE(M(,),ROW,COL,K)
LET CHECKRULE=0
FOR Y=0 TO N-1
IF M(Y,COL)=K THEN EXIT FUNCTION
NEXT Y
FOR X=0 TO N-1
IF M(ROW,X)=K THEN EXIT FUNCTION
NEXT X
LET BX=INT(COL/N1)*N1
LET BY=INT(ROW/N1)*N1
FOR X=0 TO N1-1
FOR Y=0 TO N1-1
IF M(BY+Y,BX+X)=K THEN EXIT FUNCTION
NEXT Y
NEXT X
LET CHECKRULE=1
END FUNCTION
|
|