m×nのマス目に0,1を配置する問題・考察

　m×nのマス目に0,1を配置する問題・考察を示します。

（考察）
　m×nのマス目に、0,1を並べるとき、0が隣接しない配置を生成するプログラムを考察する。

' m×nのマス目に、0,1を並べるとき、
' 0が隣接しない配置を生成する。
' Tiny Basic
Public A(999): ' m×nのマス目を表す配列。
Public COUNT:  ' 配置の個数。
Public M,N:    ' マス目サイズm,n。

' マス目サイズm,nの読み込み。
Read M,N
Data 2,3

' 初期設定。
COUNT=0
For I=1 To M: A(I)=1: Next I

' 条件を満たす配置を生成する。
Call Gen(M+1)
Print Using"M=### N=### COUNT=######";M,N,COUNT
End
'
' 条件を満たす配置を生成する再帰呼び出し。
Sub Gen(K)
  If( K > M*(N+1) ) Then
    COUNT=COUNT+1
    Print Using"#####:";COUNT
    For I=1 To M
      For J=1 To N: Print Using"##";A(I+M*J);: Next J
      Print
    Next I
    ExitSub
  End If

  A(K)=1
  Call Gen(K+1)
  A(K)=0
  If(K mod M = 1) Then
    If (A(K-M)=1) Then Call Gen(K+1)
  Else
    If (A(K-1) = 1) And (A(K-M) = 1) Then Call Gen(K+1)
  End If
End Sub

実行結果
1:
1 1 1
1 1 1
2:
1 1 1
1 1 0
3:
1 1 0
1 1 1
4:
1 1 1
1 0 1
5:
1 1 0
1 0 1
6:
1 0 1
1 1 1
7:
1 0 1
1 1 0
8:
1 1 1
0 1 1
9:
1 1 1
0 1 0
10:
1 1 0
0 1 1
11:
1 0 1
0 1 1
12:
1 0 1
0 1 0
13:
0 1 1
1 1 1
14:
0 1 1
1 1 0
15:
0 1 0
1 1 1
16:
0 1 1
1 0 1
17:
0 1 0
1 0 1
M= 2 N= 3 COUNT= 17
OK