Re: 数独 - SHIRAISHI Kazuo

2025/01/08 (Wed) 08:01:25

とりあえず気になったのが，変数trueの値を変える文が見当たらないことです。十進BASICでは変数の初期値は0に設定されています。

Re: 数独 - 永野護

2025/01/08 (Wed) 14:46:19

アドバイスに感謝します。

Re: 数独 - しばっち

2025/01/12 (Sun) 07:59:52

次のプログラムはバックトラック法(後戻り法)と呼ばれる手法を
使用しています。

このバックトラック法は今回のようなパズル問題を解くのに有効な
方法ですがプログラミング初心者には少々難しいかもしれません。

この手法は覚えておいて損はないと思います。

https://ja.wikipedia.org/wiki/バックトラッキング
https://www.cc.kyoto-su.ac.jp/~yamada/ap/backtrack.html
http://www.tommylab.ynu.ac.jp/lecture/Algorithm/10/10.pdf
https://sevendays-study.com/algorithm/ex-day4.html


内部関数、内部副プログラムのままではうまくいかず
外部関数、外部副プログラムとするとうまくいったので
パックトラック法を実装する時は外部関数や外部副プログラム
として定義した方がいいかと思います。


OPTION BASE 0
PUBLIC NUMERIC Board(5, 5),True,False,COUNT

!' サンプルの6x6数独問題 (0は空きマス)
DATA 1, 0, 3, 0, 0, 0
DATA 0, 0, 0, 0, 0, 4
DATA 0, 0, 0, 0, 2, 0
DATA 0, 5, 0, 0, 0, 0
DATA 3, 0, 0, 0, 0, 0
DATA 0, 0, 0, 4, 0, 0
LET True=1
LET False=0

!' 盤面を初期化
FOR i = 0 TO 5
FOR j = 0 TO 5
READ Board(i, j)
NEXT j
NEXT i

PRINT "元の盤面:"
FOR i = 0 TO 5
FOR j = 0 TO 5
IF Board(i, j) = 0 THEN
PRINT ".";
ELSE
PRINT STR$(Board(i, j));
END IF
NEXT j
PRINT
NEXT i
CALL SolveSudoku(0)
END

EXTERNAL FUNCTION IsValid (Row, Col, Num)
!' 行と列をチェック
FOR i = 0 TO 5
IF Board(Row, i) = Num THEN
LET IsValid = False
EXIT FUNCTION
END IF
IF Board(i, Col) = Num THEN
LET IsValid = False
EXIT FUNCTION
END IF
NEXT i
LET IsValid = True
END FUNCTION

EXTERNAL SUB SolveSudoku(N)
IF N>35 THEN
LET COUNT=COUNT+1
PRINT "解けた盤面:";COUNT
FOR i = 0 TO 5
FOR j = 0 TO 5
PRINT Board(i, j);
NEXT j
PRINT
NEXT i
IF COUNT=100 THEN STOP
ELSE
LET Col=MOD(N,6)
LET Row=INT(N/6)
IF Board(Row, Col) = 0 THEN
FOR Num = 1 TO 6
IF IsValid(Row, Col, Num) = True THEN
LET Board(Row, Col) = Num
CALL SolveSudoku(N+1) ! 再帰呼び出し
LET Board(Row, Col) = 0
END IF
NEXT Num
ELSE
CALL SolveSudoku(N+1) ! 再帰呼び出し
END IF
END IF
END SUB


再帰呼び出しを使用することで多重ループ(ここではFORループ29個)を代替させることができます。
※下記プログラム参照
-----------------------------------------------------------------------------------
上記のプログラムを総当り法(※厳密には少し違う)で書き換えてみました。

6^29(36845653286788892983296)回という途方もない回数のループですが
if文によってループが制御されています。

プログラム的にやっていることは上記のプログラムと同じです。(プログラムの書き方が違うだけ!?)


OPTION BASE 0
DIM Board(5, 5)

!' サンプルの6x6数独問題 (0は空きマス)
DATA 1, 0, 3, 0, 0, 0
DATA 0, 0, 0, 0, 0, 4
DATA 0, 0, 0, 0, 2, 0
DATA 0, 5, 0, 0, 0, 0
DATA 3, 0, 0, 0, 0, 0
DATA 0, 0, 0, 4, 0, 0
LET True=1
LET False=0

!' 盤面を初期化
FOR i = 0 TO 5
FOR j = 0 TO 5
READ Board(i, j)
NEXT j
NEXT i

PRINT "元の盤面:"
FOR i = 0 TO 5
FOR j = 0 TO 5
IF Board(i, j) = 0 THEN
PRINT ".";
ELSE
PRINT STR$(Board(i, j));
END IF
NEXT j
PRINT
NEXT i

FOR A1=1 TO 6
IF IsValid (0,1,A1)=True THEN
LET Board(0,1)=A1
FOR A2=1 TO 6
IF IsValid (0, 3, A2)=True THEN
LET Board(0,3)=A2
FOR A3=1 TO 6
IF IsValid (0, 4, A3)=True THEN
LET Board(0,4)=A3
FOR A4=1 TO 6
IF IsValid (0, 5, A4)=True THEN
LET Board(0,5)=A4
FOR B1=1 TO 6
IF IsValid (1, 0, B1)=True THEN
LET Board(1,0)=B1
FOR B2=1 TO 6
IF IsValid (1, 1, B2)=True THEN
LET Board(1,1)=B2
FOR B3=1 TO 6
IF IsValid (1, 2, B3)=True THEN
LET Board(1,2)=B3
FOR B4=1 TO 6
IF IsValid (1, 3, B4)=True THEN
LET Board(1,3)=B4
FOR B5=1 TO 6
IF IsValid (1, 4, B5)=True THEN
LET Board(1,4)=B5
FOR C1=1 TO 6
IF IsValid (2, 0, C1)=True THEN
LET Board(2,0)=C1
FOR C2=1 TO 6
IF IsValid (2, 1, C2)=True THEN
LET Board(2,1)=C2
FOR C3=1 TO 6
IF IsValid (2, 2, C3)=True THEN
LET Board(2,2)=C3
FOR C4=1 TO 6
IF IsValid (2, 3, C4)=True THEN
LET Board(2,3)=C4
FOR C5=1 TO 6
IF IsValid (2, 5, C5)=True THEN
LET Board(2,5)=C5
FOR D1=1 TO 6
IF IsValid (3, 0, D1)=True THEN
LET Board(3,0)=D1
FOR D2=1 TO 6
IF IsValid (3, 2, D2)=True THEN
LET Board(3,2)=D2
FOR D3=1 TO 6
IF IsValid (3, 3, D3)=True THEN
LET Board(3,3)=D3
FOR D4=1 TO 6
IF IsValid (3, 4, D4)=True THEN
LET Board(3,4)=D4
FOR D5=1 TO 6
IF IsValid (3, 5, D5)=True THEN
LET Board(3,5)=D5
FOR E1=1 TO 6
IF IsValid (4, 1, E1)=True THEN
LET Board(4,1)=E1
FOR E2=1 TO 6
IF IsValid (4, 2, E2)=True THEN
LET Board(4,2)=E2
FOR E3=1 TO 6
IF IsValid (4, 3, E3)=True THEN
LET Board(4,3)=E3
FOR E4=1 TO 6
IF IsValid (4, 4, E4)=True THEN
LET Board(4,4)=E4
FOR E5=1 TO 6
IF IsValid (4, 5, E5)=True THEN
LET Board(4,5)=E5
FOR F1=1 TO 6
IF IsValid (5, 0, F1)=True THEN
LET Board(5,0)=F1
FOR F2=1 TO 6
IF IsValid (5, 1, F2)=True THEN
LET Board(5,1)=F2
FOR F3=1 TO 6
IF IsValid (5, 2, F3)=True THEN
LET Board(5,2)=F3
FOR F4=1 TO 6
IF IsValid (5, 4, F4)=True THEN
LET Board(5,4)=F4
FOR F5=1 TO 6
IF IsValid (5, 5, F5)=True THEN
LET Board(5,5)=F5
LET COUNT=COUNT+1
PRINT "解けた盤面:";COUNT
FOR i = 0 TO 5
FOR j = 0 TO 5
PRINT Board(i, j);
NEXT j
PRINT
NEXT i
IF COUNT=100 THEN STOP
LET Board(5,5)=0
END IF
NEXT F5
LET Board(5,4)=0
END IF
NEXT F4
LET Board(5,2)=0
END IF
NEXT F3
LET Board(5,1)=0
END IF
NEXT F2
LET Board(5,0)=0
END IF
NEXT F1
LET Board(4,5)=0
END IF
NEXT E5
LET Board(4,4)=0
END IF
NEXT E4
LET Board(4,3)=0
END IF
NEXT E3
LET Board(4,2)=0
END IF
NEXT E2
LET Board(4,1)=0
END IF
NEXT E1
LET Board(3,5)=0
END IF
NEXT D5
LET Board(3,4)=0
END IF
NEXT D4
LET Board(3,3)=0
END IF
NEXT D3
LET Board(3,2)=0
END IF
NEXT D2
LET Board(3,0)=0
END IF
NEXT D1
LET Board(2,5)=0
END IF
NEXT C5
LET Board(2,3)=0
END IF
NEXT C4
LET Board(2,2)=0
END IF
NEXT C3
LET Board(2,1)=0
END IF
NEXT C2
LET Board(2,0)=0
END IF
NEXT C1
LET Board(1,4)=0
END IF
NEXT B5
LET Board(1,3)=0
END IF
NEXT B4
LET Board(1,2)=0
END IF
NEXT B3
LET Board(1,1)=0
END IF
NEXT B2
LET Board(1,0)=0
END IF
NEXT B1
LET Board(0,5)=0
END IF
NEXT A4
LET Board(0,4)=0
END IF
NEXT A3
LET Board(0,3)=0
END IF
NEXT A2
LET Board(0,1)=0
END IF
NEXT A1

FUNCTION IsValid (Row,COL,Num)
!' 行と列をチェック
FOR i = 0 TO 5
IF Board(Row, i) = Num THEN
LET IsValid = False
EXIT FUNCTION
END IF
IF Board(i, Col) = Num THEN
LET IsValid = False
EXIT FUNCTION
END IF
NEXT i
LET IsValid = True
END FUNCTION
END