Connect-three puzzle solveability

Question

私は正方形のグリッドを使用するカジュアルなconnect-threeタイプのゲームを書いています。プレイヤーは行や列をスライドさせ（本質的に1Dで回転させる）、同じタイプの少なくとも3つのブロックを合わせてマッチさせる。

遊びが進むにつれて難易度が上がるため、新しいマッチを生むような動きがない点があります（私はそれを確認しました）。

brute-forceメソッド（少なくともO（N^2）時間です）を使用する以外に、可能な動きを探すより高速な方法がありますか？

Answer 1

あなたはOでそれを行うことができます（N（M）をログ）Nは、ボード上の位置の数であるとMが使用可能な形状の数です：

1. O （Nログ（M））：各点について（O（N））、その行と列（O（ログ（M））のために使用可能な形状のマップを更新
   
2. 。 O（N log（M））：各点（O（N））の場合は、同様の形状が縦、横、または斜めに1つ隣にあるかどうかを確認してください（O（1））。有効な移動が利用可能であるかどうかを見るために「3つを接続する」行/列マップ（O（log（M）））。

それが不必要（2行目の形状を、以下までチェックしないと、2列目に、右への形状は左のチェックしない）のチェックを繰り返さないように、あなたはまた、上記の方法で改善することができますしかし、大きなOのコストは同じです。

各移動の後、変更された行/列のマップを更新するだけで、変更された図形を確認するだけで済みます。最悪のケースは、ボード全体がクリアされているため、この改善のための大きなOのコストも同様です。