非標準フィールドで三目並べの勝利をチェックする簡単なアルゴリズム

言語を習い始めたばかりの若いプログラマーが、言語の構文よりも困難を引き起こすという問題に直面しました。 教師が特定の言語で構文と概念を説明する場合、自分でアルゴリズムを発明する必要があります。 ルールの例外は、アルゴリズムを教える大学の専門技術専門分野のみです。



解決アルゴリズムは非常に単純であるという事実にもかかわらず、多くの人は問題の解決にアプローチする方法を知りません。 三目並べゲームで勝利をチェックする例を考えますが、6x6のフィールドと4番目に等しい値が連続して入力されます。



実際、ここでは、定数を使用した変数の代わりに、ユニバーサルアルゴリズムを示します。 また、このチェックが実行される言語とは実質的に無関係です。 初心者のプログラマーはまず問題をグラフィカルに解決し、次にそれを別の言語に翻訳することをお勧めします。 このアルゴリズムを作成するには、ケージ内のシートとペンが適しています。



したがって、6x6フィールドがあります。







連続して満たされた要素のブロックは、勝つのに十分であり、4番目に等しくなります。







私は、この問題を解決する方法がはるかに明確になったと考えています。



実際、2つの独立したタスクを解決する必要があります。

1. 4x4ブロックで完了したすべてのシーケンスを見つけます。
2. 6x4の正方形ですべての4x4の正方形を見つけます。

1. 4x4ブロックで完了したすべてのシーケンスを見つける

なぜ4x4ブロックをチェックするのですか？ すべてがシンプルで、必要な次元の対角線は2つだけです。



バイナリロジック（1＆1 = 1および1＆0 = 0）を使用すると、ループチェックを簡単に行うことができます。 これを行うには、対角線ごとに1つの変数が必要です。 torightをブール変数とし、上から下、右へ対角線をチェックした結果を書き込みます。 そして、左上から右下に向かって対角線を確認します。



これらの変数の値を最初にtrueに設定します。 次に、対角線の各セルを記号「X」または「O」と比較します。 もちろん、2回の呼び出しでこれを行うか、すべてを「X」と比較するか、すべてを「O」と比較します。



各対角セルをシンボルと比較し、結果（true）または（false）を取得します。 次に、結果と私たちの権利の間の論理演算（＆）。 この操作の結果は、再び右に書かれます。 何らかの段階で結果が得られた場合（false）、それ以降のすべてのtorightは常に等しくなります（false）。 これは、論理演算のルール（1＆0 = 0）に従います。



Javeでこれを書いてみましょう。

boolean checkDiagonal(char symb) { boolean toright = true; //    1 for (int i=0; i<4; i++) { //   0  3 toright = toright & (map[i][i] == symb); } //    (true),        symb if (toright) return true; //   (false),     ,   symb return false; }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

実際にこの行で

 toright = toright & (map[i][i] == symb))
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

そして、すべてのロジックがあります。



短いエントリは次のようになります。

 toright &= (map[i][i] == symb))
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

条件の2つの結果のみが取得されます。

 toright = toright & 0  toright = toright & 1
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

対角線が2つの場合、完全な関数コードは次のようになります。

 /**   */ boolean checkDiagonal(char symb) { boolean toright, toleft; toright = true; toleft = true; for (int i=0; i<4; i++) { toright &= (map[i][i] == symb); toleft &= (map[4-i-1][i] == symb); } if (toright || toleft) return true; return false; }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

完全なアナログは、垂直と輪郭をチェックするために行われ、サイクルのみが変更されます。

 /**      */ boolean checkLanes(char symb) { boolean cols, rows; for (int col=0; col<4; col++) { cols = true; rows = true; for (int row=0; row<4; row++) { cols &= (map[col][row] == symb); rows &= (map[row][col] == symb); } //         //    ,   //     . if (cols || rows) return true; } return false; }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

実際、これは4x4ブロックのソリューションです。 コードからわかるように、別のブロックでは、ループ内の4を別の番号に変更するか、番号ではなく変数名を記述するだけです。 そして、この変数をグローバルな可視性と関数への受け渡しの両方にすることができます。例えば次のように：

 boolean checkLanes(char symb, int block)…..
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

2. 6x4の正方形内のすべての4x4の正方形を見つける

実際、それほど多くはありません。 位置の[0,0]、[1,0]、および[2,0]から開始し、正方形の最初の行、[0,1]、[1,1]、および[2,1]の2番目の行、[0,2] 、[1,2]および[2,2]は3番目です。 さらに、4x4の正方形は6x4の正方形の境界を越えます。



この座標のソートは、サイクルで実行できます。

 boolean checkWin(char symb) { for (int col=0; col<3; col++) { for (int row=0; row<3; row++) { //         , //  ,    ,  //      if (checkDiagonal(symb, col, row) || checkLanes(symb, col, row)) return true; } } //     . 4-  //   .    . return false; }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

ここでは、適切なオフセットで4x4の正方形をチェックする必要があるため、checkDiagonalおよびcheckLanesメソッドをわずかに変更する必要があります。

 int size = 6; //    int block = 4; //   boolean checkLanes(char symb, int offsetX, int offsetY) { boolean cols, rows; for (int col=offsetX; col<block+offsetX; col++) { cols = true; rows = true; for (int row=offsetY; row<block+offsetY; row++) { cols &= (map[col][row] == symb); rows &= (map[row][col] == symb); } if (cols || rows) return true; } return false; }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

初心者のプログラマには、自分でcheckDiagonalコードを変更することをお勧めします。 これにより、それがどのように機能するかをよりよく理解できます。



そしてもう一つのヒント。 現在、ネットワーク上にはさまざまな言語のさまざまなアルゴリズムの実装が膨大にあります。 考え方を学びたい場合は、言語に縛られていないソリューション（アルゴリズム）の原則を正確に見てください。 既製のソリューションでは、最適なソリューションを選択する方法をすばやく学ぶことはできません。 多くの場合、問題を解決する原理を理解することなく、既成のソリューションをある言語から別の言語に書き換えることができます。 どこかでこれはあなたを助けますが、どこかでそれはロジックを変えない限りプログラムのさらなる開発を不可能にするかもしれません。



まず、自分で小切手を書くことをお勧めします。 ゲームテンプレートはここから入手できます 。 この記事で説明した関数ヘッダーは既にあります。 コードの一部をテンプレートにコピーし、わずかに変更します。 ここで、Javaで完全に機能するコードをダウンロードできます。 この記事に基づいて関数を記述した後、それを見ることをお勧めします。