在Python 2d數組中確定三行

Question

我正在使用Python中的M x N板進行井字遊戲。我試圖找到一種有效的方法來確定玩家是否贏了（連續3次，縱向，橫向或對角線方向）。遊戲的大部分3x3實現只是在每次回合後檢查所有可能的獲勝組合。這對於大規模的電路板來說似乎有點極端。

4x4的例子：（使用1和2秒，而不是XS和OS）

board = ([1,0,2,1], [0,0,0,1], [2,2,0,0], [1,0,0,1]) 
for row in board: 
    print row 

Thanks- 喬納森

Answer 1

儘管這種方法有一定的吸引力，但它可能並不是特別快。

# A bogus game with wins in several directions. 
board = (
    [1,1,2,1], 
    [0,2,1,1], 
    [2,2,2,1], 
    [1,0,0,1], 
) 

# A few convenience variables.  
n_rows = len(board)  
lft = [ [0] * i for i in range(n_rows) ] # [[], [0], [0, 0], [0, 0, 0]] 
rgt = list(reversed(lft)) 

# Create transpositions of the board to check for wins in various directions. 
transpositions = { 
    'horizontal' : board, 
    'vertical' : zip(*board), 
    'diag_forw' : zip(* [lft[i] + board[i] + rgt[i] for i in range(n_rows)]), 
    'diag_back' : zip(* [rgt[i] + board[i] + lft[i] for i in range(n_rows)]), 
} 

# Apply Jonathan's horizontal-win check to all of the transpositions. 
for direction, transp in transpositions.iteritems(): 
    for row in transp: 
     s = ''.join(map(str, row)) 
     for player in range(1,3): 
      if s.find(str(player) * 3) >= 0: 
       print 'player={0} direction={1}'.format(player, direction) 

輸出：

player=1 direction=diag_back 
player=2 direction=diag_forw 
player=2 direction=horizontal 
player=1 direction=vertical 

對角線換位背後的想法是對行的偏移，使用lft和rgt爲左右填充。例如，在添加填充（填充字符顯示爲句點，即使在實際代碼中使用了零）後，diag_forw列表看起來像這樣。

1 1 2 1 . . . 
. 0 2 1 1 . . 
. . 2 2 2 1 . 
. . . 1 0 0 1 

然後我們簡單地轉置陣列，使用zip(*foo)，這使我們能夠使用喬納森的好主意，尋找水平勝。

Answer 2

你可以看一下，如果玩家的舉動關閉遊戲（看好該行，該列和2對角線，如果他們連續檢查），這是o（x）的複雜性。假設你正在看那一排看看他是否贏了。向左看有多少連續檢查是在右邊。如果他們的總和超過x他贏了。你會在列和對角線上做同樣的事情。

Answer 3

檢查水平贏得

for row in board: 
    rowString = ''.join(row) 
    if(rowString.count('111') > 2 or rowString.count('222') > 2): 
     print "Somebody won" 

檢查垂直贏得

for col in xrange(len(board[0])): 
    colString = "" 
    for row in board: 
     colString = colString.append(row[col]) 
    if(colString.count('111') > 2 or colString.count('222') > 2): 
     print "Somebody won" 

還是難倒對角線...

Answer 4

如果你有一個董事會設置如下：

board = 
([1,0,2,0], 
[0,1,2,0], 
[0,0,0,0], 
[0,0,0,0]) 

可以將它想象爲x和y座標，從左上角開始，向下運動爲正y，向右運動爲正x。任何一位球員在board[3][3]的舉動將是一個勝利的舉措。使用Teodor Pripoae過程，我們可以構建最後一步移動的水平，垂直和對角線。水平的情況很容易。

def horizontal(board, y_coord): 
    return board[y_coord] 

垂直的情況下，需要我們從每一行選擇x_coord：

def vertical(board, x_coord): 
    return [row[x_coord] for row in board] 

對角線的情況是有點棘手。對於這個第一個函數，它計算從上到下從左到右的對角線。當y等於零時，距離基本上代表從零開始的水平距離。

def diagonal1(board, x_coord, y_coord): 
    length = len(board[0]) 
    distance = x_coord - y_coord 
    if distance >= 0: 
     return [y[x] for x, y in enumerate(board) if distance + x <= length] 
    else: 
     return [y[x] for x, y in enumerate(board) if x - distance >= 0 and x - distance <= length] 

該第二個函數計算從右到左從右到左的對角線。在此函數中，距離表示水平距離爲零時的垂直距離。

def diagonal2(board, x_coord, y_coord): 
    length = len(board[0]) 
    distance = y_coord + x_coord 
    return [y[distance - x] for x, y in enumerate(board) if distance - x <= length] 

一旦你有了這些定義，你只需要一種方法來檢查一個球員是否贏了。像這樣的東西可能會做：

def game_over(direction, number_to_win, player_number): 
    count = 0 
    for i in direction: 
     if i == player_number: 
      count += 1 
      if count = number_to_win: 
       return True 
     else: 
      count = 0 
    return False 

已經寫了這一切，好像這是矯枉過正，除非你有相當大的M和N雖然它可能比檢查每個勝利條件更加高效，但它構建整個水平方向，垂直方向和對角線方向，而不僅僅是圍繞最後一步移動的那些座標，它並不像它可能的那樣高效。

也許這是有幫助的，但似乎Brian的建議，簡單地刪除x的可能會更好。

Answer 5

我一直在軟件開發者訪談中使用這個問題的一個變種，所以我已經考慮了這個問題。這裏有一個更好的答案：它可以處理任意數量的玩家，任何平方井字遊戲網格和任何「遊程大小」。該方法非常簡單，提供了有關所有找到的序列的信息，並且是O（N），其中N是單元的數量。

# Given a square tic-tac-toe grid of any size, with any number of players, find 
# all sequences (horizontal, vertical, diagonal) of some minimum size. 

def main(): 
    raw_grid = [ 
     [1, 1, 2, 1, 0], # Zero means open spot. 
     [0, 2, 1, 1, 1], 
     [2, 2, 2, 1, 2], 
     [1, 0, 1, 1, 2], 
     [1, 0, 0, 0, 2], 
    ] 
    for run in get_runs(raw_grid, 3): 
     print run 

def get_runs(raw_grid, run_size): 
    # Offsets to find the previous cell in all four directions. 
    offsets = { 
     'h' : (0, -1), # _ 
     'v' : (-1, 0), # | 
     'f' : (-1, 1), #/
     'b' : (-1, -1), # \ 
    } 

    # Helpers to check for valid array bounds and to return a new cell dict. 
    size  = len(raw_grid) 
    in_bounds = lambda r, c: r >= 0 and c >= 0 and r < size and c < size 
    new_cell = lambda i, j, p: dict(h=1, v=1, f=1, b=1, i=i, j=j, player=p) 

    # Use the raw grid to create a grid of cell dicts. 
    grid = [] 
    for i, row in enumerate(raw_grid): 
     grid.append([]) 
     for j, player in enumerate(row): 
      # Add a cell dict to the grid (or None for empty spots). 
      cell = new_cell(i, j, player) if player else None 
      grid[i].append(cell) 
      if not cell: continue 

      # For each direction, look to the previous cell. If it matches the 
      # current player, we can extend the run in that direction. 
      for d, offset in offsets.iteritems(): 
       r, c = (i + offset[0], j + offset[1]) 
       if in_bounds(r, c): 
        prev = grid[r][c] 
        if prev and prev['player'] == cell['player']: 
         # We have a match, so the run size is one bigger, 
         # and we will track that run in the current cell, 
         # not the previous one. 
         cell[d] = prev[d] + 1 
         prev[d] = None 

    # For all non-None cells, yield run info for any runs that are big enough. 
    for cell in (c for row in grid for c in row if c): 
     for d in offsets: 
      if cell[d] and cell[d] >= run_size: 
       yield dict(
        player = cell['player'], 
        endpoint = (cell['i'], cell['j']), 
        direction = d, 
        run_size = cell[d], 
       ) 

main() 

輸出：

{'player': 1, 'direction': 'h', 'endpoint': (1, 4), 'run_size': 3} 
{'player': 2, 'direction': 'f', 'endpoint': (2, 0), 'run_size': 3} 
{'player': 2, 'direction': 'h', 'endpoint': (2, 2), 'run_size': 3} 
{'player': 1, 'direction': 'b', 'endpoint': (2, 3), 'run_size': 3} 
{'player': 1, 'direction': 'f', 'endpoint': (3, 2), 'run_size': 3} 
{'player': 1, 'direction': 'v', 'endpoint': (3, 3), 'run_size': 4} 
{'player': 2, 'direction': 'v', 'endpoint': (4, 4), 'run_size': 3}