algorithm - 所有可能的井字游戏获胜组合

Question

我参加了一次面试，被问到一个看似简单的算法问题:“编写一个算法，返回井字游戏所有可能的获胜组合。”我仍然想不出一种有效的方法来处理这个问题。是否有一种标准算法或通用算法应该应用于我不知道的类似问题？

Answer 1

这是实际上对于蛮力来说足够简单的问题之一，虽然您可以使用组合数学、图论或许多其他复杂的工具来解决它，但我实际上对申请人认识到存在更简单的方法(至少对于这个问题而言)。

只有 3⁹，即 19,683 种可能的放置组合 x , o或 <blank>在网格中，但并非所有这些都有效。

首先，有效的游戏位置是 x 之间的差值。和 o计数不超过 1，因为它们必须交替移动。

另外，不可能出现双方三连的状态，所以也可以打折扣。如果两人连成三局，那么他们中的一人将在前步中获胜。

实际上还有另一个限制，即一方不可能在没有共同单元的情况下以两种不同的方式获胜(同样，他们本可以在前一步中获胜)，这意味着:

XXX
OOO
XXX

无法实现，而:

XXX
OOX
OOX

可以。但我们实际上可以忽略这一点，因为如果没有公共(public)单元格就无法在不违反“最大差一”规则的情况下以两种方式获胜，因为为此你需要六个单元格，而对手只有三个。

所以我会简单地使用蛮力，对于计数之间差异为零或一的每个位置，检查双方的八种获胜可能性。假设他们中只有一个获胜，那就是合法的获胜游戏。

---

下面是 Python 中的概念证明，但首先是 time 的输出在进程上运行时将输出发送到 /dev/null显示它有多快:

real    0m0.169s
user    0m0.109s
sys     0m0.030s

代码:

def won(c, n):
  if c[0] == n and c[1] == n and c[2] == n: return 1
  if c[3] == n and c[4] == n and c[5] == n: return 1
  if c[6] == n and c[7] == n and c[8] == n: return 1

  if c[0] == n and c[3] == n and c[6] == n: return 1
  if c[1] == n and c[4] == n and c[7] == n: return 1
  if c[2] == n and c[5] == n and c[8] == n: return 1

  if c[0] == n and c[4] == n and c[8] == n: return 1
  if c[2] == n and c[4] == n and c[6] == n: return 1

  return 0

pc = [' ', 'x', 'o']
c = [0] * 9
for c[0] in range (3):
  for c[1] in range (3):
    for c[2] in range (3):
      for c[3] in range (3):
        for c[4] in range (3):
          for c[5] in range (3):
            for c[6] in range (3):
              for c[7] in range (3):
                for c[8] in range (3):
                  countx = sum([1 for x in c if x == 1])
                  county = sum([1 for x in c if x == 2])
                  if abs(countx-county) < 2:
                    if won(c,1) + won(c,2) == 1:
                      print " %s | %s | %s" % (pc[c[0]],pc[c[1]],pc[c[2]])
                      print "---+---+---"
                      print " %s | %s | %s" % (pc[c[3]],pc[c[4]],pc[c[5]])
                      print "---+---+---"
                      print " %s | %s | %s" % (pc[c[6]],pc[c[7]],pc[c[8]])
                      print

---

正如一位评论者所指出的，还有一个限制。给定棋盘的获胜者的单元格不能少于失败者，因为这意味着失败者刚刚移动，尽管事实上获胜者已经在最后一步中获胜。

我不会更改代码以考虑到这一点，但检查谁拥有最多单元格(最后移动的人)并确保获胜线属于他们是一件简单的事情。