Java で TicTacToe ゲームを作成しています。2 次元配列を使用し、再帰を使用して勝者がいるかどうかを確認する必要があります。
勝者の非再帰チェックを簡単に実行できるように感じますが、再帰を使用する場合、再帰を使用する場合はどこから始めればよいかわかりません。そのようなアルゴリズムのプロセスを開始する場所について、誰かが私を案内してくれますか?
Java で TicTacToe ゲームを作成しています。2 次元配列を使用し、再帰を使用して勝者がいるかどうかを確認する必要があります。
勝者の非再帰チェックを簡単に実行できるように感じますが、再帰を使用する場合、再帰を使用する場合はどこから始めればよいかわかりません。そのようなアルゴリズムのプロセスを開始する場所について、誰かが私を案内してくれますか?
これに再帰を使用するのは少し無理があるように思えることに同意します。それにもかかわらず、1 つのアイデアは、勝利の定義に基づいています: X または O の 3 つが任意の方向に 1 列に並ぶことです。潜在的な開始点 (3 マスの列を開始できない中央以外の場所) を選択することから始め、機能する可能性のある方向を選択します。(動作する可能性のある方向のセットは、最初の正方形の関数です。) 再帰的な手順は次のとおりです。たとえば、特定の方向で X の行にnが必要であり、現在の位置に X がある場合は、次のようにします。その方向に 1 ステップ進み、そこからその方向に ( n - 1) を続けて探します。n = 0 のときに停止します。このプロセス全体を、すべての開始点と方向に対して、勝利を見つけるか、選択肢がなくなるまで繰り返します。
始めるには、これで十分な手がかりだと思います。
ボードが次のようになっていると仮定します。
| |
cell[0][0] | cell[1][0] | cell[2][0]
| |
------------+------------+------------
| |
cell[0][1] | cell[1][1] | cell[2][1]
| |
------------+------------+------------
| |
cell[0][2] | cell[1][2] | cell[2][2]
| |
1 つの方法は、単純に隣接するセルを再帰的に (一方向に) チェックすることです。例(疑似コード):
def checkSame (val, cellX, cellY. deltaX, deltaY):
# No winner if check value is empty.
if val == empty: return false
# Winner if we've gone off edge. No need to worry about < 0
# since one direction is always ascending but I've left it
# in anyway.
if cellX > 2 or cellY > 2: return true
if cellX < 0 or cellY < 0: return true
# No winner if piece has changed.
if cell[cellX][cellY] != val: return false
# Otherwise use recursion to check next one.
return checkSame (val, cellX + deltaX, cellY + deltaY, deltaX, deltaY)
次に、8 つの可能な開始点/方向の値を確認する必要があります。
# Check rows.
if checkSame (cell[0][0], 0, 0, 1, 0): return true
if checkSame (cell[0][1], 0, 1, 1, 0): return true
if checkSame (cell[0][2], 0, 2, 1, 0): return true
# Check columns.
if checkSame (cell[0][0], 0, 0, 0, 1): return true
if checkSame (cell[1][0], 1, 0, 0, 1): return true
if checkSame (cell[2][0], 2, 0, 0, 1): return true
# Check diagonals.
if checkSame (cell[0][0], 0, 0, 1, 1): return true
return checkSame (cell[0][2], 0, 2, 1, -1)
さて、それは再帰のかなり制限された(そして不自然な)使用ですが、あなたが言うように、とにかく再帰に適した状況ではありません。if
これを標準の 3x3 tic-tac-toe 以上に拡張する予定がない場合は、8 つのステートメントを使用する方がはるかに優れています。