シューティング･スター問題（８）考察４

シューティング･スター問題（８）考察４を示します。

（８）考察４

　シューティング･スターにおいて、すべての初期状態（29=512通り）から最終状態に変換可能であることをBasic言語（Tiny Basic）書かれたプログラムで確認せよ。

　３×３のマス目に番号を付ける。

●プログラム（SS131.bas）

' << SS131.bas >>
' シューティング･スターにおいて、すべての初期状態（29=512通り）に
' ついて、最終状態に変換可能であるか否かを確認するプログラム
'
Dim B(10,10): ' B(i,*)：マス目番号iに影響を与えるマス目番号を
              ' 保存する配列。
Dim Z(10,10): ' マス目iに影響を与えるマス目jが存在するとき
              ' Z(i,j)=1、存在しないときZ(i,j)=0。
Dim X(10):    ' マス目の初期状態。0は消灯状態、1は点灯状態。
Dim Y(10):    ' マス目の最終状態。0は消灯状態、1は点灯状態。
Dim D(10):    ' マス目の変化状態。0は変化なし、1は変化あり。
'
' マス目Iに影響を与えるマス目番号を読み込む。
For I=1 To 9
  For J=1 To 5: Read B(I,J): Next J
Next I
'
Data 1,2,4,0,0
Data 1,2,3,5,0
Data 2,3,6,0,0
Data 1,4,5,7,0
Data 1,3,5,7,9
Data 3,5,6,9,0
Data 4,7,8,0,0
Data 5,7,8,9,0
Data 6,8,9,0,0
'
' 最終状態Yの設定。                                   
For I=1 To 9: Y(I)=1: Next I                           
Y(5)=0
'
' 初期状態の設定。
For I=1 To 10: X(I)=0: Next I
X(1)=-1
N=0: ' 初期状態の個数。
'
Do
  ' 最初の状態の更新。
  X(1)=X(1)+1
  K=1
  While X(K) = 2
    X(K)=0: K=K+1: X(K)=X(K)+1
  Wend
  If K >= 10 Then Exit Do
  N=N+1
  '                                                         
  ' 初期設定。                                              
  For I=1 To 9                                              
    For J=1 To 9: Z(I,J)=0: Next J                          
    For J=1 To 5                                            
      If B(I,J) > 0 Then Z(I,B(I,J))=1                      
    Next J                                                  
  Next I                                                    
  '                                                         
  ' マス目の変化状態の設定。
  For I=1 To 9                                              
    If X(I) = Y(I) Then D(I)=0 Else D(I)=1                  
  Next I                                                    
  '                                                         
  ' 最初の状態、目標の状態を表示。                          
  Print"(";N;")"
  Print"最初の状態　目標の状態"                             
  For I=1 To 3                                               
    For J=1 To 3                                             
      K=3*(I-1)+J                                            
      If X(K) = 0 Then C$="■" Else C$="□"                  
      Print C$;                                              
    Next J                                                  
    Print Space$(6);                                        
    For J=1 To 3                                             
      K=3*(I-1)+J                                            
      If Y(K) = 0 Then C$="■" Else C$="□"                  
      Print C$;                                              
    Next J                                                   
    Print                                                    
  Next I                                                     
  '                                                         
  ' 考察２の手順で解を求める。
  For J=1 To 9                                              
    K=J                                                     
    While Z(K,J) = 0: K=K+1: Wend                           
    If K > 9 Then                                           
      Print"変換ができません"                               
      Stop                                                  
    End If                                                  
    '                                                       
    If J <> K Then                                          
      For P=1 To 9                                          
        W=Z(J,P): Z(J,P)=Z(K,P): Z(K,P)=W                   
      Next P                                                
      W=D(J): D(J)=D(K): D(K)=W                             
    End If                                                  
    '                                                       
    For I=1 To 9                                            
      If (Z(I,J) = 1) and (I <> J) Then                     
        For P=1 To 9: Z(I,P)=(Z(I,P)+Z(J,P)) Mod 2: Next P  
        D(I)=(D(I)+D(J)) Mod 2                              
      End If                                                
    Next I                                                  
  Next J                                                    
  '                                                         
  ' 解の表示。                                                 
  For I=1 To 9                                                 
    For J=1 To 9                                               
      If (Z(I,J) = 1) and (D(I) = 1) Then  
        Print Using"##";J;                                   
      End If                                                   
    Next J                                                     
  Next I
  Print"を押してください。" 
  Print
Loop
End