|
|
!ナンバープレース探索プログラムを、速くする。
!
!再帰なし、再帰あり１，２，３の、４タイプを、まとめた。
!処理は、分岐無しで直線状に行き来しており、再帰なしの Normal の方が？
!-------------------------------------------------------------------
DEBUG ON
OPTION ARITHMETIC NATIVE
DECLARE FUNCTION numplace, numpla1, numpla2, numpla3, OUTPUT_, checkout$
LET crlf$= CHR$(13)& CHR$(10)
OPTION BASE 0
DIM tb(8,8), copy(8,8) !問題を置く配列
DIM i0(80),j0(80) !１）
DIM u3(80,3),v3(80,3) !２）
DIM q(80,9) !３）
DIM qp(80) !Normal型 専用。q() の各消費量( 初期値 0)
!--------------
! 実行前の準備
!--------------
SUB pre_ready
!------------------------------------------------
!１）空白の座標だけを、高速に調査できるように、
! 連続 番号で、座標を並べた i0(s),j0(s) 作成
!------------------------------------------------
LET s9=-1
FOR i=0 TO 8
FOR j=0 TO 8
IF tb(i,j)=0 THEN
LET s9=s9+1
LET i0(s9)=i
LET j0(s9)=j
END IF
NEXT j
NEXT i
!------------------------------------------------------
!２）空白の座標の全てについて、
! 各々、所属する３ｘ３枠で、その縦横列５個所を除く、
! 他４箇所の 座標を並べた u3(s,0~3),v3(s,0~3) 作成
!------------------------------------------------------
FOR s=0 TO s9
LET i=i0(s)
LET j=j0(s)
LET p=0
FOR u=INT(i/3)*3 TO INT(i/3)*3 +2
FOR v=INT(j/3)*3 TO INT(j/3)*3 +2
IF u<>i AND v<>j THEN
LET u3(s,p)=u
LET v3(s,p)=v
LET p=p+1
END IF
NEXT v
NEXT u
NEXT s
!---------------------------------------------
!３）空白の座標の全てについて、
! 初期値の有る個所から 受ける制限で、
! 取り得る数を、予め格納する q(s,0~9) 作成
!---------------------------------------------
FOR s=0 TO s9
LET p=0
FOR k=1 TO 9
!------------ 縦横列チェック
FOR w=0 TO 8
IF k=tb(w,j0(s)) OR k=tb(i0(s),w) THEN EXIT FOR !false
NEXT w
IF 8< w THEN
!------------ 3x3 枠の残り４箇所チェック
IF k=tb(u3(s,0),v3(s,0)) OR k=tb(u3(s,1),v3(s,1)) THEN !false
ELSEIF k=tb(u3(s,2),v3(s,2)) OR k=tb(u3(s,3),v3(s,3)) THEN !false
ELSE !OK.
LET q(s,p)=k
LET p=p+1
END IF
END IF
NEXT k
LET q(s,p)=0 !終端マーク
NEXT s
END SUB
!----------------------------------------------
! メイン プログラム
!----------------------------------------------
MAT READ tb
! MAT tb=TRN(tb) !転置( 長時間かかる問題が、転置すると一瞬で終る事もある)
CALL pre_ready !準備
PRINT "問題"
MAT PRINT tb; !問題表示
MAT copy=tb
!
LET z$="0132" !実行する型だけを、任意な順と個数 並べる
!
FOR sel=1 TO LEN(z$)
MAT tb=copy
LET cnt=0
SELECT CASE z$(sel:sel)
CASE "0"
LET T$="Normal型" !再帰を使わない。１番の最高速
LET t0=TIME
LET res= numplace
LET t1=TIME-t0
CASE "1"
LET T$="再帰１型" !単一文の再帰型。２番速
LET t0=TIME
LET res= numpla1(0)
LET t1=TIME-t0
CASE "2"
LET T$="再帰２型" !２つの文にまたがる再帰型。最も遅い４番速
LET t0=TIME
LET res= numpla2(0)
LET t1=TIME-t0
CASE "3"
LET T$="再帰３型" !再帰２型の速度向上型。３番速
LET t0=TIME
LET res= numpla3(0)
LET t1=TIME-t0
END SELECT
IF res=0 THEN PRINT "false after (";cnt;"通り)"
PRINT USING T$& " 実行時間#####.### sec":MOD( t1,86400)
PRINT
NEXT sel
PRINT "終了"
!----------------------------------------------
! ●１つ完成 の表示と、正誤の確認
!----------------------------------------------
!単一解。又は、複数解の全表示。
!---------------
FUNCTION OUTPUT_
LET cnt=cnt+1
PRINT "(";cnt;")";checkout$(tb) !正誤の確認 再検査( NG.なら、戻らず停止)
MAT PRINT tb;
LET OUTPUT_=1 !●( 引数=1：１解で終了。引数=0：複数解 )
END FUNCTION
!複数解の場合で 高速に その個数を調べる時
!----------------
!FUNCTION OUTPUT_
! LET cnt=cnt+1
! IF MOD(cnt,1000)=0 THEN PRINT "(";cnt;")"
! LET OUTPUT_=0 !●( 引数=1：１解で終了。引数=0：複数解 )
!END FUNCTION
!----------------------------------------------
! 問題を解く本体( 再帰無し Normal型 )
!----------------------------------------------
FUNCTION numplace
MAT qp=ZER
FOR s=0 TO s9
LET i=i0(s)
LET j=j0(s)
FOR p=qp(s) TO 9 ! s ごとの候補 q() のポインター p
LET k=q(s,p) !候補の数字 k
IF k=0 THEN EXIT FOR !NG. k の使い切り
!------------ 縦横列チェック
FOR w=0 TO 8
IF k=tb(w,j) OR k=tb(i,w) THEN EXIT FOR !next k
NEXT w
IF 8< w THEN
!------------ 3x3 枠の残り４箇所チェック
IF k=tb(u3(s,0),v3(s,0)) OR k=tb(u3(s,1),v3(s,1)) THEN !next k
ELSEIF k=tb(u3(s,2),v3(s,2)) OR k=tb(u3(s,3),v3(s,3)) THEN !next k
ELSE
LET tb(i,j)=k
IF s=s9 THEN LET k=OUTPUT_ !●１つ完成
LET qp(s)=p+1 !次の開始 p 記憶( 再帰では同位置に戻り
EXIT FOR !next p を通るので qp()自体、不要)
END IF !next k
END IF !next k
NEXT p
IF k=0 THEN
!------------ NG. k の使い切り
LET tb(i,j)=0
LET qp(s)=0
LET s=s-2 !1つ手前の s で、やり直し
IF s< -1 THEN EXIT FOR !探索限界で、終了
END IF
NEXT s
LET numplace=k
END FUNCTION
!----------------------------------------------
! 問題を解く本体( 再帰型１)
!----------------------------------------------
FUNCTION numpla1(s)
IF s9< s THEN
LET numpla1=OUTPUT_ !●１つ完成
ELSE
local i,j,p
LET numpla1=1 !preset true
LET i=i0(s)
LET j=j0(s)
FOR p=0 TO 8
LET k=q(s,p)
IF k=0 THEN EXIT FOR
!------------ 縦横列チェック
FOR w=0 TO 8
IF k=tb(w,j) OR k=tb(i,w) THEN EXIT FOR ! next k
NEXT w
IF 8< w THEN
!------------ 3x3 枠の残り４箇所チェック
IF k=tb(u3(s,0),v3(s,0)) OR k=tb(u3(s,1),v3(s,1)) THEN !next k
ELSEIF k=tb(u3(s,2),v3(s,2)) OR k=tb(u3(s,3),v3(s,3)) THEN !next k
ELSE
LET tb(i,j)=k
IF 0< numpla1(s+1) THEN EXIT FUNCTION
END IF
END IF
NEXT p
!------------ NG. k の使い切り
LET tb(i,j)=0
LET numpla1=0
END IF
END FUNCTION
!----------------------------------------------
! 問題を解く本体( 再帰型２)
!----------------------------------------------
FUNCTION numpla2(s)
IF s9< s THEN
LET numpla2=OUTPUT_ !●１つ完成
ELSE
local p
LET numpla2=1 !preset true
FOR p=0 TO 8
LET k=q(s,p)
IF k=0 THEN EXIT FOR
IF 0< test(s,k) THEN EXIT FUNCTION
NEXT p
!------------ NG. k の使い切り
LET tb(i0(s),j0(s))=0
LET numpla2=0
END IF
END FUNCTION
FUNCTION test(s,k)
LET test=0
LET i=i0(s)
LET j=j0(s)
!------------ 縦横列チェック
FOR w=0 TO 8
IF k=tb(w,j) OR k=tb(i,w) THEN EXIT FUNCTION ! next k
NEXT w
!------------ 3x3 枠の残り４箇所チェック
IF k=tb(u3(s,0),v3(s,0)) OR k=tb(u3(s,1),v3(s,1)) THEN EXIT FUNCTION ! next k
IF k=tb(u3(s,2),v3(s,2)) OR k=tb(u3(s,3),v3(s,3)) THEN EXIT FUNCTION ! next k
!------------
LET tb(i,j)=k
LET test=numpla2(s+1)
END FUNCTION
!----------------------------------------------
! 問題を解く本体( 再帰型３) 再帰２の速度向上
!----------------------------------------------
FUNCTION numpla3(s)
IF s9< s THEN
LET numpla3=OUTPUT_ !●１つ完成
ELSE
LET numpla3=1
IF 0< test3(s) THEN EXIT FUNCTION
!------------ NG. k の使い切り
LET tb(i0(s),j0(s))=0
LET numpla3=0
END IF
END FUNCTION
FUNCTION test3(s)
local p
LET test3=0 !preset false
FOR p=0 TO 8
LET k=q(s,p)
IF k=0 THEN EXIT FUNCTION !NG.
LET i=i0(s)
LET j=j0(s)
!------------ 縦横列チェック
FOR w=0 TO 8
IF k=tb(w,j) OR k=tb(i,w) THEN EXIT FOR ! next k
NEXT w
IF 8< w THEN
!------------ 3x3 枠の残り４箇所チェック
IF k=tb(u3(s,0),v3(s,0)) OR k=tb(u3(s,1),v3(s,1)) THEN ! next k
ELSEIF k=tb(u3(s,2),v3(s,2)) OR k=tb(u3(s,3),v3(s,3)) THEN ! next k
!------------
ELSE
LET tb(i,j)=k
LET test3=numpla3(s+1)
END IF
END IF
NEXT p
END FUNCTION
!----------------------------------------------
! tb(,) の解が 規則通りに並んでいるかを 検査
!----------------------------------------------
FUNCTION checkout$(tb(,))
local i,j
LET w$=""
FOR k=1 TO 9
FOR z=0 TO 8 STEP 3
LET i1=0
LET i2=0
LET i3=0
FOR w=z TO z+2
!------------ 横列チェック
FOR j=8 TO 0 STEP -1
IF k=tb(w,j) THEN EXIT FOR !ok
NEXT j
IF j< 0 THEN LET w$=w$& crlf$& STR$(w+1)& "行目、横方向に "& STR$(k)& " 無し"
!------------ 縦列チェック
FOR i=8 TO 0 STEP -1
IF k=tb(i,w) THEN EXIT FOR !ok
NEXT i
IF i< 0 THEN LET w$=w$& crlf$& STR$(w+1)& "列目、縦方向に "& STR$(k)& " 無し"
!------------ 3x3 チェック
IF 6<=i THEN
LET i3=1
ELSEIF 3<=i THEN
LET i2=1
ELSEIF 0<=i THEN
LET i1=1
END IF
NEXT w
IF i1=0 THEN LET w$=w$& crlf$& "(1行,"& STR$(z+1)& "列)┏ から右下3x3に "& STR$(k)& " 無し"
IF i2=0 THEN LET w$=w$& crlf$& "(4行,"& STR$(z+1)& "列)┏ から右下3x3に "& STR$(k)& " 無し"
IF i3=0 THEN LET w$=w$& crlf$& "(7行,"& STR$(z+1)& "列)┏ から右下3x3に "& STR$(k)& " 無し"
NEXT z
NEXT k
IF w$="" THEN
LET checkout$="OK"
ELSE
PRINT w$
MAT PRINT tb;
PRINT T$;" (";cnt;")";"でエラー、以降の中止"
STOP
END IF
END FUNCTION
!( #5300 )上級＋＋ ※1 通りの解を持つ
DATA 3,0,0,0,0,2,0,0,0
DATA 0,0,6,0,0,0,0,9,0
DATA 0,0,9,0,0,4,0,0,3
DATA 0,9,0,0,0,0,0,0,5
DATA 0,5,0,8,0,0,0,6,0
DATA 8,0,0,0,3,0,0,1,0
DATA 2,0,0,9,0,0,3,0,0
DATA 0,6,0,0,0,0,4,0,0
DATA 0,0,0,1,0,0,0,0,7
!( #5425 )上級＋＋ ※(7行,2列)を、1→0 に改変、21 通りの解を持つ
DATA 0,8,0, 0,0,0, 4,0,0
DATA 6,0,0, 2,0,0, 0,0,0
DATA 0,9,0, 4,0,0, 0,2,0
DATA 9,0,0, 0,0,6, 1,0,0
DATA 0,0,2, 9,0,0, 5,0,0
DATA 0,0,3, 0,0,0, 0,0,6
DATA 0,0,0, 0,0,4, 0,3,0
DATA 0,0,0, 0,0,7, 0,0,5
DATA 0,0,5, 0,0,0, 0,7,0
END
|
|