我正在使用Python中的M x N板进行井字游戏。我试图找到一种有效的方法来确定玩家是否赢了（连续3次，纵向，横向或对角线方向）。游戏的大部分3x3实现只是在每次回合后检查所有可能的获胜组合。这对于大规模的电路板来说似乎有点极端。在Python 2d数组中确定三行
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- 乔纳森
尽管这种方法有一定的吸引力，但它可能并不是特别快。
# 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)，这使我们能够使用乔纳森的好主意，寻找水平胜。
你可以看一下，如果玩家的举动关闭游戏（看好该行，该列和2对角线，如果他们连续检查），这是o（x）的复杂性。假设你正在看那一排看看他是否赢了。向左看有多少连续检查是在右边。如果他们的总和超过x他赢了。你会在列和对角线上做同样的事情。
检查水平赢得
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"
还是难倒对角线...
如果你有一个董事会设置如下：
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的可能会更好。
我一直在软件开发者访谈中使用这个问题的一个变种，所以我已经考虑了这个问题。这里有一个更好的答案：它可以处理任意数量的玩家，任何平方井字游戏网格和任何“游程大小”。该方法非常简单，提供了有关所有找到的序列的信息，并且是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}
检查所有组合可以是矫枉过正，但它仍然是在O（M×N个）可行的，因为任何给定的正方形是不超过恒定数量的可能的一员赢得的弦乐。此外，这种检查很可能会花费足够长的时间才能被用户察觉。话虽如此，你可以打败这是你注意的举动，如特奥多所言。 – Brian 2010-07-22 16:55:42
@Brian，Teodore。同意，在传统的tic tac toe游戏中，只需要检查选定的方块可能取得的胜利就会更有意义。我实际上使用这个来试图确定Xs（no Os）的最大数量，它可以在没有胜利的情况下在板上。我正在迭代填充板（MxN位二进制数）并确定它是否成功。我认为井字问题会给我一些算法思想，而不必解释太多。 – Jonathan 2010-07-22 17:04:36
在这种情况下，Teodor的建议将会奏效，尽管您可以通过跳过八个方向中的三个方向的测试来稍微提高速度。顺便说一下，我的直觉是，通过从一个完整的xs板开始并尽可能少地移除，可能更容易解决这个问题。 – Brian 2010-07-22 17:26:31