所有可能的Tic Tac Toe获胜组合

Question

我接受了一次采访,我被问到一个看似简单的算法问题:"编写一个算法,将所有可能的获胜组合归还给我." 我仍然无法找到一种有效的方法来处理这个问题.是否有一个标准算法或常见的应用于我不知道的类似问题？

Answer 1

这是一个对蛮力来说实际上很简单的问题之一,虽然你可以使用组合学,图论或其他许多复杂的工具来解决它,但实际上我会对申请人留下深刻的印象,他们认识到这是一种更简单的方法(至少对于这个问题).

仅存在3个⁹,或载置的19683个可能的组合x,o或<blank>在网格,而不是所有这些都是有效的.

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

此外,它是不可能有一国两边一排有三个,所以他们可以打折为好.如果两者都有三个连续,那么其中一个将在前一个移动中获胜.

实际上还存在另一个限制,即如果没有共同的单元格,一方可能以两种不同的方式获胜(同样,他们会在之前的一次移动中获胜),这意味着:

XXX
OOO
XXX

无法实现,同时:

XXX
OOX
OOX

可.但是我们实际上可以忽略这一点,因为如果没有违反"一个最大差异"规则就没有共同单元就没有办法赢得两种方式,因为你需要六个单元格,而对手只有三个单元格.

所以我只是使用蛮力,并且对于每个位置,其中差值为零或计数之间的一个,检查双方的八个获胜可能性.假设他们中只有一人获胜,这是一场合法的胜利游戏.

下面是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

正如一位评论者指出的那样,还有一个限制因素.一个特定董事会的赢家不能拥有比失败者更少的细胞,因为这意味着失败者只是移动了,尽管胜利者已经在最后一步获胜.

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