|
投稿者：山中和義
投稿日：2012年10月 1日(月)19時46分53秒
|
|
|
|
ネット上で大きな話題だそうですね。
> 小さなサイズ（7×7程度）であれば「深さ優先検索（DFS）」というアルゴリズムで解けます。
!問題
!m行n列の格子状の道がある。
!同じ交差点を通らないようにして、左上から右下へ向かうときの道順は何通りか。
!例 m=n=3の場合
! 始点─・─・
! │ │ │
! ・─・─・
! │ │ │
! ・─・─終点
!のとき、
! 始点─・ ・
! │
! ・ ・─・
! │
! ・ ・ 終点
!のような最短経路は条件を満たす。
!また、
! 始点 ・─・
! │ │ │
! ・─・ ・
! │
! ・ ・ 終点
!のような遠回りも条件を満たす。
!求める道順は、12通りある。
!参考サイト http://mathworld.wolfram.com/Self-AvoidingWalk.html
LET t0=TIME
LET M=6 !行
LET N=M !列
PUBLIC NUMERIC C !解の個数
LET C=0
DIM P(0 TO M-1,0 TO N-1) !経路 p(y,x)
MAT P=(-1)*CON
LET P(0,0)=0 !左上がスタート位置
LET P(0,1)=1 !左斜めの対角線で折り返すと対称になる (0,0)→(0,1)
CALL try(0,1,2,P,M,N) !(0,1)
PRINT 2*C;"通り"
PRINT "計算時間=";TIME-t0
END
EXTERNAL SUB try(y,x,s,P(,),M,N) !バックトラック法で検索する
IF x=N-1 AND y=M-1 THEN !ゴール（右下）に到達したなら
LET C=C+1 !経路を表示する
!!PRINT "No.";C
!!MAT PRINT P;
ELSE
IF y=0 OR y=M-1 THEN !上壁沿いか下壁沿いなら、左側は袋小路なので進入禁止とする
ELSE
IF x>0 THEN !左端以外なら左へ
LET xx=x-1
IF P(y,xx)=-1 THEN !未踏なら
LET P(y,xx)=s !仮に進む
CALL try(y,xx,s+1,P,M,N) !次へ
LET P(y,xx)=-1 !戻す
END IF
END IF
END IF
IF x<N-1 THEN !右へ
LET xx=x+1
IF P(y,xx)=-1 THEN
LET P(y,xx)=s
CALL try(y,xx,s+1,P,M,N)
LET P(y,xx)=-1
END IF
END IF
IF x=0 OR x=N-1 THEN !左壁沿いか右壁沿いなら、上側は袋小路なので進入禁止とする
ELSE
IF y>0 THEN !上へ
LET yy=y-1
IF P(yy,x)=-1 THEN
LET P(yy,x)=s
CALL try(yy,x,s+1,P,M,N)
LET P(yy,x)=-1
END IF
END IF
END IF
IF y<M-1 THEN !下へ
LET yy=y+1
IF P(yy,x)=-1 THEN
LET P(yy,x)=s
CALL try(yy,x,s+1,P,M,N)
LET P(yy,x)=-1
END IF
END IF
END IF
END SUB
|
|
|
|
投稿者：山中和義
投稿日：2012年10月 6日(土)07時18分57秒
|
|
|
|
> No.1985[元記事へ]
> 小さなサイズ（7×7程度）であれば「深さ優先検索（DFS）」というアルゴリズムで解けます。
C言語などのサンプルでは、漸化式による表現で計算しています。
LET t0=TIME
PUBLIC NUMERIC M,N
LET M=6 !行
LET N=M !列
PUBLIC NUMERIC P(0 TO 8,0 TO 8) !経路 p(y,x)
MAT P=ZER(M+2,N+2) !-1:通路、0:壁（番兵）
FOR y=1 TO M
FOR x=1 TO N
LET P(y,x)=-1
NEXT x
NEXT y
LET P(1,1)=0 !左上がスタート位置
MAT PRINT P; !debug
PRINT 2*calc(1,2);"通り" !(1,1)→(1,2) ※左斜めの対角線で折り返すと対称になる
PRINT "計算時間=";TIME-t0
END
EXTERNAL FUNCTION calc(x,y) !漸化式として計算する
IF x=N AND y=M THEN !ゴールなら
LET calc=1
ELSEIF P(y,x)<0 THEN !通路なら
LET P(y,x)=1 !仮に進む
LET w=0
IF NOT(y=1 OR y=M) THEN LET w=w+calc(x-1,y) !左へ ※上壁沿いか下壁沿いなら、左側は袋小路なので進入禁止とする
LET w=w+calc(x+1,y) !右へ
IF NOT(x=1 OR x=N) THEN LET w=w+calc(x,y-1) !上へ ※左壁沿いか右壁沿いなら、上側は袋小路なので進入禁止とする
LET w=w+calc(x,y+1) !下へ
LET calc=w
LET P(y,x)=-1 !元に戻す
ELSE !通過していたら
LET calc=0
END IF
END FUNCTION
|
|
|
|
投稿者：山中和義
投稿日：2012年10月 7日(日)18時47分24秒
|
|
|
|
> No.1986[元記事へ]
> 小さなサイズ（7×7程度）であれば「深さ優先検索（DFS）」というアルゴリズムで解けます。
次のようなアルゴリズムでも算出可能なようです。
!0:右,1:上,2:左,3:下の進行方向、-1:通路 を表すとする。
!N行N列の格子状の道は、N=7の場合、
! -1 2 2 2 2 2 2 2 -1
! 1 -1 -1 -1 -1 -1 -1 -1 1
! 1 -1 -1 -1 -1 -1 -1 -1 1
! 1 -1 -1 -1 -1 -1 -1 -1 1
! 1 -1 -1 -1 -1 -1 -1 -1 1
! 1 -1 -1 -1 -1 -1 -1 -1 1
! 1 -1 -1 -1 -1 -1 -1 -1 1
! 1 -1 -1 -1 -1 -1 -1 -1 1
! -1 2 2 2 2 2 2 2 -1
!と表される。
!左斜めの対角線での線対称を考慮して、左上（スタート位置）の進路方向を右と限定できる。
!そして、求める値は算出した結果を2倍すればよい。
!よって、
! -1 2 2 2 2 2 2 2 -1
! 1 0 -1 -1 -1 -1 -1 -1 1
! 1 -1 -1 -1 -1 -1 -1 -1 1
! 1 -1 -1 -1 -1 -1 -1 -1 1
! 1 -1 -1 -1 -1 -1 -1 -1 1
! 1 -1 -1 -1 -1 -1 -1 -1 1
! 1 -1 -1 -1 -1 -1 -1 -1 1
! 1 -1 -1 -1 -1 -1 -1 -1 1
! -1 2 2 2 2 2 2 2 -1
!を初期値とする。
!
!●外壁との袋小路の判定
!たとえば、3行6列目で右端の壁に接した場合、
! -1 2 2 2 2 2 2 2 -1
! 1 0 3 -1 -1 -1 -1 -1 1
! 1 -1 3 -1 -1 -1 -1 ? 1
! 1 -1 0 0 0 0 0 * 1
! 1 -1 -1 -1 -1 -1 -1 ? 1
! 1 -1 -1 -1 -1 -1 -1 -1 1
! 1 -1 -1 -1 -1 -1 -1 -1 1
! 1 -1 -1 -1 -1 -1 -1 -1 1
! -1 2 2 2 2 2 2 2 -1
!より、
!上側（2行6列目）は、右下（ゴール位置）への道順はないので進入禁止と判断するれば、
!その分だけ計算量は少なくなる。
!
!●自分が通った経路による袋小路の判定
!たとえば、3行2列目で接した場合、
! -1 2 2 2 2 2 2 2 -1
! 1 0 3 -1 -1 -1 -1 -1 1
! 1 -1 0 0 0 0 0 3 1
! 1 ? * ? -1 -1 -1 3 1
! 1 -1 1 -1 -1 -1 -1 3 1
! 1 -1 1 -1 -1 -1 -1 3 1
! 1 -1 1 2 2 2 2 2 1
! 1 -1 -1 -1 -1 -1 -1 -1 1
! -1 2 2 2 2 2 2 2 -1
!より、
!右側（3行3列目）は、右下（ゴール位置）への道順はないので進入禁止と判断する。
!
!これらは、
! 進行方向に対して右または左隣接で、同じ方向の経路が並行するかどうか
!で判定できる。
LET t0=TIME
PUBLIC NUMERIC M,N
LET M=6 !行
LET N=M !列
PUBLIC NUMERIC C !解の個数
LET C=0
PUBLIC NUMERIC P(0 TO 8,0 TO 8) !経路 p(y,x)
MAT P=(-1)*CON(M+2,N+2) !通路とする
FOR y=1 TO M !外の辺は壁（番兵）とする
LET P(y,0)=1
LET P(y,N+1)=1
NEXT y
FOR x=1 TO N
LET P(0,x)=2
LET P(M+1,x)=2
NEXT x
LET P(1,1)=0 !左上がスタート位置
MAT PRINT P; !debug
CALL try(1,2) !(1,1)→(1,2) ※左斜めの対角線で折り返すと対称になる
PRINT 2*C;"通り"
PRINT "計算時間=";TIME-t0
END
EXTERNAL SUB try(y,x) !バックトラック法で検索する
IF x=N AND y=M THEN !ゴール（右下）なら
LET C=C+1 !経路を表示する
!!PRINT "No.";C
!!MAT PRINT P;
ELSE
LET xx=x-1 !左へ
IF P(y,xx)=-1 THEN !未踏なら
IF NOT( P(y-1,x)=2 OR P(y+1,x)=2 ) THEN !※袋小路
LET P(y,x)=2 !仮に進む（進行方向）
CALL try(y,xx)
LET P(y,x)=-1 !戻す
END IF
END IF
LET xx=x+1 !右へ
IF P(y,xx)=-1 THEN
IF NOT( P(y-1,x)=0 OR P(y+1,x)=0 ) THEN !※袋小路
LET P(y,x)=0
CALL try(y,xx)
LET P(y,x)=-1
END IF
END IF
LET yy=y-1 !上へ
IF P(yy,x)=-1 THEN
IF NOT( P(y,x-1)=1 OR P(y,x+1)=1 ) THEN !※袋小路
LET P(y,x)=1
CALL try(yy,x)
LET P(y,x)=-1
END IF
END IF
LET yy=y+1 !下へ
IF P(yy,x)=-1 THEN
IF NOT( P(y,x-1)=3 OR P(y,x+1)=3 ) THEN !※袋小路
LET P(y,x)=3
CALL try(yy,x)
LET P(y,x)=-1
END IF
END IF
END IF
END SUB
|
|
|
|
投稿者：山中和義
投稿日：2012年10月 9日(火)10時47分5秒
|
|
|
|
> No.1987[元記事へ]
> 1×1、2×2、3×3とマスの数を増やしていくお姉さん。
> 5×5からはパソコンで計算し、
> 7×7からは処理が間に合わないとしてスーパーコンピュータが登場しました。
4×4マス（5×5ノード）の8512通りまでは、手計算で行っている。
DFSのような総当りなのだろうか。
3×3ノードの場合
・─・─・
│ │ │
・─・─・
│ │ │
・─・─・
次のように分割する。
Ｓ─ ・─・
│ │ │
・─ ・─・
│ │ │
・─ ・─Ｇ
左斜めの対角線による線対称を考えて、左上（スタート位置）から右に進むとする。
Ｓ─ ・─・
│ │
・─ ・─・
│ │ │
・─ ・─Ｇ
左側は、次の2通り（連結部の個数が1つ,3つのもの）が考えられる。
Ｓ─ ●─・ Ｓ─ ●─・ Ｓ─ ● ・ Ｓ─ ● ・
│ │ │ │
・ ・ ・ ・ ・─・ ・ ・─・ ・ ・ ・
│ │ │ │
・ ・ Ｇ ・ ・─Ｇ ・ ・ Ｇ ・ ・─Ｇ
この場合の右側は、2^(3-1)=4通り
Ｓ─ ●─・ Ｓ─ ● ・
│ │
・─ ●─・ ・─ ● ・
│ │
・─ ●─Ｇ ・─ ●─Ｇ
この場合の右側は、2通り
よって、4+2=6通り
したがって、6*2=12通り
補足 連結部
・個数について
左側から右側への移動の個数を「出」、右側から左側への移動の個数を「入」とすると、
「出」=「入」+1 となり、個数は1,3,5,7,…である。
・向きの「場合の数」
個数が1の場合は、→●の1通り
個数が3の場合は、3=2+1から、3!/(2!1!)=3通り
←● →● →●
→● ←● →●
： ： ：
→● →● ←●
である。
3×3の場合では、
Ｓ←● ×
→●
：
→●
→● ────┐
→● 袋小路 │
： │
←● ────┘Ｇ
は、不適なので、
→●
←●
：
→●
のみとなる。
（終り）
補足 袋小路
・外壁との袋小路
5×5の場合では、
Ｓ─・ ・ ・ ・
│
・ ・ ・ ・ ×
│ ↑
・ ・─・─・─●
↓
・ ・ ・ ・ ○
│
・ ・ ・ ・ Ｇ
なので、
Ｓ→・→・→・→・
↓ │ │ │ ↓
・─・─・─・─・
↓ │ │ │ ↓
・─・─・─・─・
↓ │ │ │ ↓
・─・─・─・─・
↓ │ │ │ ↓
・→・→・→・→Ｇ
のように、一方通行となる。
・自分が通った経路による袋小路
Ｓ─・→・─・─・
│
○←●→× ・ ・
│ │ │
・ ・─・─・─・
│
・─・─・─・─Ｇ
これは、
進行方向に対して右または左隣接で、同じ方向の経路が並行するかどうか
で判定できる。
（終り）
4×4ノードの場合
・─・─・─・
│ │ │ │
・─・─・─・
│ │ │ │
・─・─・─・
│ │ │ │
・─・─・─・
次のように分割する。
Ｓ─・─ ・─・
│ │ │
・─・─ ・─・
│ │ │ │
・─・─ ・─・
│ │ │ │
・─・─ ・─Ｇ
Ｓ→・→ ・→・
│ │ ↓
・─・─ ・─・
↓ │ │ ↓
・─・─ ・─・
↓ │ │ ↓
・→・→ ・→Ｇ
連結部が1個の場合、位置はC(4,1)=4通り、向きは1通り
Ｓ─・→ ●─・
│ │
・ ・ ・─・
│ │
・ ・ ・─・
│ │
・ ・ ・─Ｇ
8通り
1×8=8通り
Ｓ─・ ・ ・ ・─・ ・─・
│ │ │ │ │
・ ・→ ●─・ ● ・ ● ・
│ │ │ │
・ ・ ・─・ ・ ・ ・─・
│ │ │ │
・ ・ ・─Ｇ ・ Ｇ ・─Ｇ
4通り └─ 2通り ─┘
1×(4+2)=6通り
Ｓ─・ Ｓ─・ Ｓ─・ ・ ・ ・ ・ ・─・
│ │ │ │ │
・ ・ ・─・ ・─・ ・ ・ ・─・ ・ ・
│ │ │ │ │ │ │
・ ・→ ・─・→ ・ ・→ ●─・ ● ・ ● ・
│ │ │ │ │ │
・ ・ ・ ・ ・─・ ・─Ｇ ・ Ｇ ・ Ｇ
2通り └─ 2通り ─┘
3×(2+2)=12通り
Ｓ─・ Ｓ─・ Ｓ─・ Ｓ─・ ・ ・ ・ ・ ・ ・ ・─・
│ │ │ │ │ │
・─・ ・─・ ・ ・ ・ ・ ・ ・ ・ ・ ・─・ ・ ・
│ │ │ │ │ │ │ │
・ ・ ・─・ ・─・ ・ ・ ・ ・ ・─・ ・ ・ ・ ・
│ │ │ │ │ │ │ │ │ │
・─・→ ・ ・→ ・─・→ ・ ・→ ●─Ｇ ● Ｇ ● Ｇ ● Ｇ
└─────── 4通り ────────┘
4×4=16通り
計42通り
連結部が3個の場合、
位置はC(4,3)=4通り、それぞれ向きは3!/(2!1!)=3通り（1通りのみが適となる）
Ｓ─・→ Ｓ─・→ Ｓ─・→ ●─・
│ │
・ ・← ・─・← ・─・← ●─・
│ │ │
・ ・→ ・─・→ ・ ・→ ●─・
│ │ │ │
・ ・ ・ ・ ・─・ ・─Ｇ
2×2=4通り
3×4=12通り
Ｓ─・→ Ｓ─・→ Ｓ─・→ Ｓ─・→ ●─・ ●─・
│ │
・ ・← ・ ・← ・─・← ・─・← ●─・ ● ・
│ │ │ │ │ │
・ ・ ・─・ ・─・ ・ ・ ・─・ ・─・
│ │ │ │ │ │
・ ・→ ・─・→ ・ ・→ ・─・→ ●─Ｇ ●─Ｇ
4通り 1通り
4×(4+1)=20通り
Ｓ─・→ Ｓ─・→ Ｓ─・→ ●─・
│ │
・ ・ ・ ・ ・─・ ・─・
│ │ │ │
・ ・← ・─・← ・ ・← ●─・
│ │ │
・ ・→ ・─・→ ・─・→ ●─Ｇ
4通り
3×4=12通り
Ｓ─・ Ｓ─・ ・ ・ ・─・
│ │ │ │
・ ・→ ・ ・→ ●─・ ● ・
│ │ │
・ ・← ・─・← ●─・ ●─・
│ │
・ ・→ ・─・→ ●─Ｇ ●─Ｇ
2通り 1通り
2×(2+1)=6通り
計50通り
よって、42+50=92通り
したがって、92*2=184通り
|
|
|
|
投稿者：山中和義
投稿日：2012年10月12日(金)10時42分42秒
|
|
|
|
> No.1988[元記事へ]
（続き）
> 1×1、2×2、3×3とマスの数を増やしていくお姉さん。
> 5×5からはパソコンで計算し、
> 7×7からは処理が間に合わないとしてスーパーコンピュータが登場しました。
以上のまとめとして、次のことが見えてくる。
補足 経路の略図
右向きの矢印（2個以上あるなら）に着目すると、
・1つは左上（スタート位置）に繋がっている。
・もう1つは右下（ゴール位置）に繋がっている。
・残りは、中継である。
となる。
連結部が1つの場合、1通り
Ｓ─ ⇒ ┐
│
Ｇ
連結部が3つの場合、2通り
Ｓ┐┌ ⇒ ─┐
│└ ← ┐│
└─ → ┘Ｇ
Ｓ─ → ┐
┌ ← ┘
└ ⇒ ─Ｇ
（終り）
4×4ノードの場合
実際の格子に割り当てる。
Ｓ→・→ ・→・
│ │ ↓
・─・─ ・─・
↓ │ │ ↓
・─・─ ・─・
↓ │ │ ↓
・→・→ ・→Ｇ
■連結部が1つの場合
Ｓ─ ⇒ ┐
│
Ｇ
行の位置は、C(4,1)=4通り
Ｓ→・⇒ ●→・ Ｓ→・ ・→・ Ｓ→・ ・→・ Ｓ→・ ・→・
│ ↓ │ │ ↓ │ │ ↓ │ │ ↓
・ ・ ・─・ ・ ・⇒ ●─・ ・─・ ・─・ ・─・ ・─・
│ ↓ │ ↓ ↓ │ │ ↓ ↓ │ │ ↓
・ ・ ・─・ ・ ・ ・─・ ・─・⇒ ●─・ ・─・ ・─・
│ ↓ │ ↓ ↓ │ │ ↓ ↓ │ │ ↓
・ ・ ・→Ｇ ・ ・ ・→Ｇ ・→・ ・→Ｇ ・→・⇒ ●→Ｇ
1×2^3=8通り 1×(2^2+1*2^1)=6通り 3×(2^1+2*2^0)=12通り 2^2×(2^0+3*2^0)=16通り
計8+6+12+16=42通り
■連結部が3つの場合
Ｓ┐┌ ⇒ ─┐
│└ ← ┐│
└─ → ┘Ｇ
行の位置は、C(4,3)=4通り
Ｓ→・⇒ ●→・ Ｓ→・⇒ ●→・ Ｓ→・⇒ ●→・ Ｓ→・ ・→・
│ ↓ │ ↓ │ │ ↓ │ │ ↓
・─・← ・ ・ ・─・← ・ ・ ・─・ ・─・ ・─・⇒ ●─・
↓ │ │ ↓ ↓ │ │ ↓ ↓ │ ↓ ↓ │ ↓
・─・→ ・ ・ ・─・ ・ ・ ・─・← ・ ・ ・─・← ・ ・
↓ │ ↓ ↓ │ │ ↓ ↓ │ │ ↓ ↓ │ │ ↓
・→・ ・ Ｇ ・→・→ ・ Ｇ ・→・→ ・ Ｇ ・→・→ ・ Ｇ
0通り 0通り 0通り 0通り
計0通り ※1,2行目で「スタート」が「ゴール」と繋がって、残り2本と結ぶことができない。
Ｓ─ → ┐
┌ ← ┘
└ ⇒ ─Ｇ
行の位置は、C(4,3)=4通り
Ｓ→・→ ・→・ Ｓ→・→ ・→・ Ｓ→・→ ・→・ Ｓ→・→ ・→・ Ｓ→・ ・→・
│ ↓ │ ↓ ↓ │ ↓ │ │ ↓
・─・← ・─・ ・─・← ・─・ ・─・← ・ ・ ・─・ ・─・ ・ ・→ ・─・
↓ │ ↓ │ ↓ │ │ ↓ ↓ │ │ ↓ │ ↓
・─・⇒ ●─・ ・─・ ・─・ ・─・ ・─・ ・─・← ・─・ ・─・← ・─・
↓ │ │ ↓ ↓ │ │ ↓ ↓ │ ↓ │ ↓ │
・→・ ・→Ｇ ・→・⇒ ●→Ｇ ・→・⇒ ●→Ｇ ・→・⇒ ●→Ｇ ・→・⇒ ●→Ｇ
3×2*2=12通り 2^2×2*2=16通り 2^2×1=4通り 3×2^2=12通り 2×(2^1+1*2^0)=6通り
計12+(16+4)+12+6=50通り
よって、42+50=92通り
したがって、92*2=184通り
5×5ノードの場合
連結部が5つの場合、8通り
Ｓ┐┌ ⇒ ─┐
│└ ← ┐│
│┌ → ┘│
│└ ← ┐│
└─ → ┘Ｇ
Ｓ┐┌─ ⇒ ──┐
││┌ ← ─┐│
││└ → ┐││
│└─ ← ┘││
└── → ─┘Ｇ
Ｓ┐┌ ⇒ ──┐
│└ ← ─┐│
└─ → ┐││
┌ ← ┘││
└ → ─┘Ｇ
Ｓ── → ┐
┌─ ← ┘
│┌ ⇒ ─┐
│└ ← ┐│
└─ → ┘Ｇ
Ｓ┐┌─ → ┐
││┌ ← ┘
││└ ⇒ ─┐
│└─ ← ┐│
└── → ┘Ｇ
Ｓ─ → ┐
┌ ← ┘
└ → ┐
┌ ← ┘
└ ⇒ ─Ｇ
Ｓ── → ─┐
┌─ ← ┐│
│┌ → ┘│
│└ ← ─┘
└─ ⇒ ─Ｇ
Ｓ┐┌ → ─┐
│└ ← ┐│
└─ → ┘│
┌ ← ─┘
└ ⇒ ─Ｇ
を併せて考えれば求まるだろう。
|
|
|
|
投稿者：山中和義
投稿日：2012年10月14日(日)21時40分32秒
|
|
|
|
> No.1985[元記事へ]
> 『フカシギの数え方』 おねえさんといっしょ！ みんなで数えてみよう！
6畳の敷き方に違和感が、、、 フカシギ
!畳の敷き方
!例
!1畳（2×1）
!┌┐
!││
!└┘
!3畳（2×3）
!┌┬┬┐ ┌┬─┐ ┌─┬┐
!││││ │├─┤ ├─┤│
!└┴┴┘ └┴─┘ └─┴┘
!3通り
!参考サイト
! 図形問題 シリーズ
!
! 畳の敷き方数
! http://www.geocities.jp/ikuro_kotaro/koramu/603_t2.htm
! http://www.geocities.jp/ikuro_kotaro/koramu/2185_s4.htm
! コマ大数学科120講：畳
PUBLIC NUMERIC M,N
LET M=4 !行 ※偶数
LET N=3 !列
DIM P(0 TO M+1,0 TO N+1)
FOR i=0 TO M+1 !0,m+1は壁（番兵）
FOR J=0 TO N+1 !0,n+1は壁（番兵）
LET P(i,J)=0 !0:置けない
NEXT J
NEXT i
FOR i=1 TO M
FOR J=1 TO N
LET P(i,J)=-1 !-1:置ける
NEXT J
NEXT i
MAT PRINT P; !debug
PUBLIC NUMERIC DX(0 TO 1),DY(0 TO 1) !配置方向
DATA 0,1 !縦、横
DATA 1,0
MAT READ DX
MAT READ DY
PUBLIC NUMERIC C !解の個数
LET C=0
CALL try(1,M*N,1,1,p) !左上から順に
PRINT C;"通り"
!検算
LET S=1 !2^(m*n/2)Π[i=1,m]Π[j=1,n]{cos(i*π/(m+1))^2+cos(j*π/(n+1))^2}^1/4
FOR i=1 TO M
FOR J=1 TO N
LET S=S*SQR(SQR(COS(i*PI/(M+1))^2+COS(J*PI/(N+1))^2))
NEXT J
NEXT i
PRINT 2^(M*N/2)*S
END
EXTERNAL SUB try(D,Q,X,Y,P(,)) !バックトラック法で検索する
FOR K=0 TO 1 !各方向
IF P(Y,X)=-1 AND P(Y+DY(K),X+DX(K))=-1 THEN !y行x列目（左上が基準）に置けるなら
LET P(Y,X)=D !d番目を仮に敷いてみる
LET P(Y+DY(K),X+DX(K))=D
LET W=Q-2 !残りの枚数
IF W=0 THEN !すべて敷き詰められたなら
LET C=C+1
!!PRINT "No.";C !結果を表示する
!!MAT PRINT P;
ELSE
FOR i=Y TO M !空き位置を見つける
FOR J=1 TO N
IF P(i,J)=-1 THEN EXIT FOR !i行J列目
NEXT J
IF J<=N THEN EXIT FOR
NEXT i
IF i<=M THEN CALL try(D+1,W,J,i,P) !次へ
END IF
LET P(Y,X)=-1 !元に戻す
LET P(Y+DY(K),X+DX(K))=-1
END IF
NEXT K
END SUB
|
|
|
戻る
