JAVA言語によるコイン問題

Kubo 1995-2017

社員研修の最後に課題として出題したプログラムの思考方法をJAVAに書き改めました。

本プログラムの利点は解法に至る思考方法とプログラム技法を試すことである。
※再帰を使用するのかリスト構造にするのかは修学程度で決めればよい。

命題

1. 10円玉と100円玉それぞれ3枚以上のコインを下図のように並べる。
   ●●●〇〇〇　(n=3と定義した場合)
2. 隣り合うコイン2枚をセットでそのまま並んだコインの延長線上に移動させる。
   以下はn=3とした場合の移動ルール(・はコインの置いてない場所を明示的に表示)
   　　●・・〇〇〇●● (左から2番目と3番目をセットで一番右に移動)
   あるいは
   　　●●・・〇〇●〇 (左から3番目と4番目をセットで一番右に移動)
   もちろん
   〇〇●●●〇・・ (右から1番目と2番目をセットで一番左に移動)
   も可能。
   ※追加考察の結果
   　「移動先は必ず動かすコインの左右どちらかが元のコインに接すること」
   　を追加ルールしても構わない(後述)。
3. 「2」のルールに従い、続けて移動を繰り返す。以下は移動例。
   移動0回目：●●●●〇〇〇〇　(n=4とした場合)
   移動1回目：●・・●〇〇〇〇●●
   移動2回目：●〇〇●・・〇〇●●
   移動3回目：●〇〇●〇●〇・・●
   移動4回目：・・〇●〇●〇●〇●
4. 「3」の例のように10円と100円のコインが4枚の場合、4回の移動で交互にできる。
   以上が10円玉と100円玉を4枚使用したコイン問題として余興として出題できる。
   整理すると、
   1)テーブルにコイン4枚ずつを「移動0回目」のように並べ
   2)隣り合うコイン2枚をセットで回転させることなく、空いている場所に移動させる。
   3)その際移動先のコインと接する場所に移動させること。
   4)「2-3」のルールを4回繰り返す。
   5)「移動4回目」のように連続した交互になれば成功。
   というゲームができる。

以上、コインを使用してルールを理解する

拡張命題

1. さて、コインが4枚ずつの場合は4回の移動で交互にできた。
   では、コインが3枚ずつの場合はどうか？
   移動0回目：●●●〇〇〇
   移動1回目：・・●〇〇〇●●
   移動2回目：・・●〇〇・・●〇●
   移動3回目：・・・・〇●〇●〇●
   3回でできた。
2. それではコインが5枚ずつの場合はどうか？
   移動0回目：●●●●●〇〇〇〇〇
   移動1回目：●・・●●〇〇〇〇〇●●
   移動2回目：●〇〇●●〇〇・・〇●●
   移動3回目：●〇〇●・・〇●〇〇●●
   移動4回目：●〇〇●〇●〇●〇・・●
   移動5回目：・・〇●〇●〇●〇●〇●
   5回でできた。
3. 以上を一般化してコインがn枚ずつの場合はn回でできるか検証のためプログラム化して法則発見の一助とする(ただしnは3以上)。
4. JAVA言語で完成したプログラム。
   プログラムするにあたり、以下の条件を課した。
   1)移動パターンを総当たりして解を求める手法でプログラムすること。
   2)再起処理を使用してロジックを考えること。
   3)コインの枚数を入力できるようにすること。
   4))正解のパターンを表示させること(なければ『無し』を表示)。
5. 当初「コインの延長線上のどこでも移動可能」としたルールでプログラムしたが、総当たりのパターン数が膨大になったため「移動先をコインの隣接のみ」に限定した。
   しかし、限定しても「n回で交互になる(しかも最終形は空間が無い)」ことがn=10までは確認できた。
   結果、余興として「コイン問題－命題4」のようなルールが成立しゲーム化できた。

以上、拡張命題を解く準備として、
コイン10枚までをコンピュータを使用して検証プログラムを作成してみる。

プログラムリスト

1. 処理速度を考慮しない再帰を使用したプログラム例
2. プログラムリスト
   ////////////////////////////////////////////
   //        coin Change
   //
   //        coded by S.Kubo
   ////////////////////////////////////////////
   import java.util.Scanner;
   import java.util.Date;
   
   //////////////////////
   //        enum
   //
   enum markType{
           BLACK("X"),
           WHITE("O"),
           NULL("."),;
           private final String text;
   
           private markType( final String text ){ this.text=text; }
           @Override
           public String toString(){ return this.text; }
   }
   
   
   //////////////////////
   //coinBase
   //
   class coinBase{
           markType arry[];
           int num;
   
   //============
   //construct
           public coinBase( int n ){
                   num = n;
                   arry = new markType[num*6];
           }
           public coinBase( coinBase coins ){
                   this.num=coins.num;
                   this.arry = new markType[this.num*6];
                   for( int x=0; x<this.num*6; x++ ){
                           this.arry[x]=coins.arry[x];
                   }
           }
   //============
   //Initialize
           public void init(){
                   int cnt=0;
                   for( int x=0; x<this.num*2; x++ ){
                           this.arry[cnt++] = markType.NULL;
                   }
                   for( int x=0; x<this.num; x++ ){
                           this.arry[cnt++] = markType.BLACK;
                   }
                   for( int x=0; x<this.num; x++ ){
                           this.arry[cnt++] = markType.WHITE;
                   }
                   for( int x=0; x<this.num*2; x++ ){
                           this.arry[cnt++] = markType.NULL;
                   }
           }
   
   //============
   //Print
           public void print(){
                   for( int x=0; x<this.num*6; x++ ){
                           System.out.print( this.arry[x] );
                   }
                   System.out.println();
           }
   //============
   //Is Get 2-Coins
           public boolean isGet( int n ){
                   if( n<0 || n>this.num*6-2 ){ return false; }
                   if( this.arry[n]==markType.NULL || this.arry[n+1]==markType.NULL ){
                           return false;
                   }else{
                           return true;
                   }
           }
   //============
   //Is Put 2-Coins Null-Case
           public boolean isPutNull( int n ){
                   if( n<0 || n>this.num*6-2 ){ return false; }
                   if( this.arry[n]==markType.NULL && this.arry[n+1]==markType.NULL ){
                           return true;
                   }else{
                           return false;
                   }
           }
   //============
   //Is Put 2-Coins Touch-Case
           public boolean isPutTouch( int n ){
                   if( n<1 || n>this.num*6-3 ){ return false; }
                   if( this.arry[n+2]!=markType.NULL || this.arry[n-1]!=markType.NULL ){
                           return true;
                   }else{
                           return false;
                   }
           }
   //============
   //Move 2-Coins
           public void move( int i, int j){
                   this.arry[j] = this.arry[i];
                   this.arry[j+1] = this.arry[i+1];
                   this.arry[i] = this.arry[i+1] = markType.NULL;
           }
   //============
   //Is Alternate Coins
           public boolean isAlternate(){
                   for( int i=0; i< this.num*6; i++ ){
                           if( this.arry[i]!=markType.NULL && this.arry[i]!=this.arry[i+1] ){
                                   for( int j=i; j< i+this.num*2; j+=2 ){
                                           if( this.arry[j]!=this.arry[i] || this.arry[j+1]!=this.arry[i+1] ){
                                                   return false;
                                           }
                                   }
                                   return true;
                           }
                   }
                   return false;
           }
   
   //============
   //Recursive Coin-Patterns
           public boolean run( int n ){
           //print();
                   if( n>=this.num ){
                           return isAlternate();
                   }
                   for( int i=0; i< this.num*6; i++ ){
                           if( isGet( i ) ){
                                   for( int j=0; j<this.num*6; j++ ){
                                           if( isPutNull( j ) && isPutTouch( j ) ){
   
                                                   coinBase coins = new coinBase(this);
                                                   coins.move( i, j );
   
                                                   if( coins.run( n+1 )==true ){
                                                           coins.print();
                                                           return true;
                                                   }
                                           }
                                   }
                           }
                   }
                   return false;
           }
   }
   
   //////////////////////
   //        coinChange Main Process
   //
   public class coinChange{
           public static void main(String[] args) {
                   Scanner in = new Scanner( System.in );
                   int maxN;
                   do{
                           System.out.println( "Please enter the number of Your coins(3-n)" );
                           maxN = in.nextInt();
                   }while( maxN<3 );
                   coinBase coins = new coinBase(maxN);
                   coins.init();
                   Date start = new Date();
                   if( coins.run( 0 )==true ){
                           coins.print();
                   }else{
                           System.out.print( "Can Not" );
                           System.out.println();
                   }
                   Date end = new Date();
                   long t=end.getTime() - start.getTime();
                   System.out.print( t+"ms" );
           }
   }

プログラム構造

1. プログラムは単純である。

   1.   コインが移動するのに十分な空間(配列を)用意。
   coinBase Class

   2.   完成条件「コインの間が空かないで交互になる」まで再帰で総当たりをする。
   isAlternate()            完成条件。
   run( int n )             再帰。nは再起の深さ。

   3.   移動できるコインを探す。
   つまり「隣り合うコインは空間以外」が移動可能なコイン。
   isGet( int n )           nは調べる最初の配列番号。

   4.   移動場所を探す。条件１「置ける場所は空間」である。
   isPutNull( int n )       nは調べる最初の配列番号。

   5.   移動場所を探す。条件２「置ける場所はコインに隣接」する。
   isPutTouch( int n )      nは調べる最初の配列番号。

   実行結果

   ・Windows10 core-i7 3.4GHz 32Mem
   ・n=3～n=5    処理時間は6ms、13ms、330ms

   ・n=6         処理時間は23945ms　システム上、解法の表示は下から上へとなる。

   ..............OXOXOXOXOXOX..........

   ............XOOXOXOXOXO..X..........

   ............XOOXOXOX..OOXX..........

   ............XOO..XOXXOOOXX..........

   ............XOOXXXO..OOOXX..........

   ............X..XXXOOOOOOXX..........

   ............XXXXXXOOOOOO............

    

   ・n=7         処理時間は3427066ms

   ................OXOXOXOXOXOXOX............

   ..............XOOXOXOXOXOXO..X............

   ..............XOOXOX..OXOXOOXX............

   ..............XOOXOXXOO..XOOXX............

   ..............XOOX..XOOOXXOOXX............

   ..............XOOXXXXOOO..OOXX............

   ..............X..XXXXOOOOOOOXX............

   ..............XXXXXXXOOOOOOO..............

パターンを推測する

1. 先のプログラムでコンピュータによる7枚の実行結果は約57分であった。
   当たり前だが、本アルゴリズムでの検証は以降指数的に時間がかかる。
   ただし、過去に10枚までプログラムで検証済みで、10枚の時は10回で交互にできる。
   従って、ここまで(7枚)の結果を踏まえて8枚以降を推測する。
   ・8枚を面パターンから推測してみる。

   
   1. パターン表から以下の部分はパターンで推測できる
   ●●●●●●●●〇〇〇〇〇〇〇〇
   ●・・●●●●●〇〇〇〇〇〇〇〇●●
   ●〇〇●？？？？？？？？？？〇〇●●
   ●〇〇？？？？？？？？？？？〇〇●●
   ●〇〇？？？？？？？？？？？〇〇●●
   ●〇〇？？？？？？？？？？？〇〇●●
   ●〇〇●〇●〇●〇●〇●〇●〇・・●
   ・・〇●〇●〇●〇●〇●〇●〇●〇●
   
   2. もう少しパターンを見つける
   ●●●●●●●●〇〇〇〇〇〇〇〇
   ●・・●●●●●〇〇〇〇〇〇〇〇●●
   ●〇〇●●●●●〇？？？？？〇〇●●
   ●〇〇？〇？？●〇？？？？？〇〇●●
   ●〇〇●〇●？●〇？？？？？〇〇●●
   ●〇〇●〇●？●〇？？？？？〇〇●●
   ●〇〇●〇●〇●〇●〇●〇●〇・・●
   ・・〇●〇●〇●〇●〇●〇●〇●〇●
   
   3. 以降、どの手順でパターンを当てはめれば解が得られるか？
   また、別のアプローチがあるか検証する。

実行結果を基に処理の速度アップを行う

1. 処理の雰囲気から、
   n=3の時、配列数はコイン枚数×2+5あれば処理が破たんしない。
   n=3以外の時、配列数はコイン枚数×2+3あれば処理が破たんしない。
   以上のように配列数をダイエットして再帰数を抑制してみる(修正プログラムは別頁)。
   結果、n=3～7の時、5ms、6ms、13ms、33ms、305ms、で終了したのでn=8以降を試す。
   Please enter the number of Your coins(3-n)
   8
   ..OXOXOXOXOXOXOXOX.
   XOOXOXOXOXOXOXO..X.
   XOOXOXOXOX..OXOOXX.
   XOOXO..XOXXOOXOOXX.
   XOOXOOXXOXXO..OOXX.
   XOOX..XXOXXOOOOOXX.
   XOOXXXXXO..OOOOOXX.
   X..XXXXXOOOOOOOOXX.
   XXXXXXXXOOOOOOOO...
   4286ms
   
   n=8　4286ms
   ●●●●●●●●〇〇〇〇〇〇〇〇
   ●・・●●●●●〇〇〇〇〇〇〇〇●●
   ●〇〇●●●●●〇・・〇〇〇〇〇●●
   ●〇〇●・・●●〇●●〇〇〇〇〇●●
   ●〇〇●〇〇●●〇●●〇・・〇〇●●
   ●〇〇●〇・・●〇●●〇〇●〇〇●●
   ●〇〇●〇●〇●〇●・・〇●〇〇●●
   ●〇〇●〇●〇●〇●〇●〇●〇・・●
   ・・〇●〇●〇●〇●〇●〇●〇●〇●
   とりあえず、先の推測パターンと一致するか検証。
   
   ちなみに、
   n=9　268230ms
   ●●●●●●●●●〇〇〇〇〇〇〇〇〇
   ●・・●●●●●●〇〇〇〇〇〇〇〇〇●●
   ●〇〇●●●●●●〇〇・・〇〇〇〇〇●●
   ●〇〇●・・●●●〇〇●●〇〇〇〇〇●●
   ●〇〇●〇〇●●●〇〇●●〇〇・・〇●●
   ●〇〇●〇〇●●・・〇●●〇〇●〇〇●●
   ●〇〇●〇・・●〇●〇●●〇〇●〇〇●●
   ●〇〇●〇●〇●〇●〇●・・〇●〇〇●●
   ●〇〇●〇●〇●〇●〇●〇●〇●〇・・●
   ・・〇●〇●〇●〇●〇●〇●〇●〇●〇●
   
   n=10　8707475ms
   ●●●●●●●●●●〇〇〇〇〇〇〇〇〇〇
   ●・・●●●●●●●〇〇〇〇〇〇〇〇〇〇●●
   ●〇〇●●●●●●●〇・・〇〇〇〇〇〇〇●●
   ●〇〇●・・●●●●〇●●〇〇〇〇〇〇〇●●
   ●〇〇●〇〇●●●●〇●●〇〇・・〇〇〇●●
   ●〇〇●〇〇●・・●〇●●〇〇●●〇〇〇●●
   ●〇〇●〇〇●●〇●〇●・・〇●●〇〇〇●●
   ●〇〇●〇・・●〇●〇●〇●〇●●〇〇〇●●
   ●〇〇●〇●〇●〇●〇●〇●〇●・・〇〇●●
   ●〇〇●〇●〇●〇●〇●〇●〇●〇●〇・・●
   ・・〇●〇●〇●〇●〇●〇●〇●〇●〇●〇●
   
2. これ以上のnを試すにはプログラムの効率化を行うか解法パターンを見つけるしかない。従って以降は数学的解法を試してみる。
3. 数学的検証
   このゲームで「コイン(n≧3)枚ずつの時、n回で必ず交互になるか否か」を証明せよ。
   また、「必ずn回でできる場合の解法手順」を説明せよ。

JAVAプログラム(最終バージョン)

戻る