考虑以下字母排列:

    B
   O A
  N R I
 D E N T

从最上面的字母开始，选择下面两个字母之一，Plinko 风格，直到到达底部。无论您选择什么路径，您都会创建一个四个字母的单词:BOND、BONE、BORE、BORN、BARE、BARN、BAIN 或 BAIT。 DENT 读取底部的事实只是一个很好的巧合。

我想帮助找出可以设计这种布局的算法，其中从顶部到底部的每条可能路径都会从(提供的)字典中生成一个不同的词。程序的输入是一个起始字母(本例中为 B)和一个字长 n(本例中为 4)。它会返回构成这种布局的字母，或者一条消息说这是不可能的。它不必是确定性的，因此它可能会使用相同的输入生成不同的布局。

到目前为止，我还没有想到比蛮力方法更好的方法。也就是说，对于为布局底部选择字母的所有 26^[(n+2)(n-1)/2] 方法，检查是否所有可能的 2^ (n-1) 路径给出字典中的单词。我考虑过某种前缀树，但路径可以交叉和共享字母这一事实让我很困惑。我对 Python 最熟悉，但至少我只是喜欢能解决这个问题的算法或方法的想法。谢谢。

最佳答案

假设底部的 V W X Y Z 实际上是完整的单词。

    B
   A O
  I R N
 T N E D
V W X Y Z

我们可以使用如此严格的启发式方法实现回溯搜索，任何错误的路径似乎都不太可能走得太远。

将以相同字母开头的所有 n 大小的单词插入一个简单的树中，如下所示。现在执行深度优先搜索，断言以下内容:每个后续级别都需要一个额外的“共享”字母，意味着该级别上的 p(letter) 实例，并额外要求它们的两个子级是相同的字母(例如，第 2 级括号中的两个 R 可能是“共享”字母，因为它们的子级相同)。

什么是p(letter)？当然是帕斯卡三角!根据 Plinko 板，n choose r 恰好是这个简单树的相关级别所需的字母实例数。在第 3 层，如果我们选择了 R 和 R，我们将需要 3 个 N 和 3 个 Es 表示该级别上的“共享”字母。并且 3 个 N 中的每一个都必须具有相同的子字母(在本例中为 W,X)，并且 3 个 E 中的每一个也必须具有相同的子字母(X,Y) .

                     B
            /                 \
          A                     O
      /       \             /       \   
     I        (R)         (R)        N
    / \       / \         / \       / \
   T  (N)   (N)  E      (N)  E     E   D
  V W W X   W X X Y     W X X Y   X Y Y Z

4 W's, 6 X's, 4 Y's 

更新

出于好奇，这里有一些 Python code :)

from itertools import combinations
from copy import deepcopy

# assumes words all start
# with the same letter and
# are of the same length
def insert(word, i, tree):
  if i == len(word):
    return
  if word[i] in tree:
    insert(word, i + 1, tree[word[i]])
  else:
    tree[word[i]] = {}
    insert(word, i + 1, tree[word[i]])

# Pascal's triangle
def get_next_needed(needed):
  next_needed = [[1, None, 0]] + [None] * (len(needed) - 1) + [[1, None, 0]]

  for i, _ in enumerate(needed):
    if i == len(needed) - 1:
      next_needed[i + 1] = [1, None, 0]
    else:
      next_needed[i + 1] = [needed[i][0] + needed[i+1][0], None, 0]
  return next_needed

def get_candidates(next_needed, chosen, parents):
  global log
  if log:
    print "get_candidates: parents: %s" % parents
  # For each chosen node we need two children.
  # The corners have only one shared node, while
  # the others in each group are identical AND
  # must have all have a pair of children identical
  # to the others' in the group. Additionally, the
  # share sequence matches at the ends of each group.
  #    I       (R)     (R)      N
  #   / \      / \     / \     / \
  #  T  (N)  (N)  E  (N)  E   E   D

  # Iterate over the parents, choosing
  # two nodes for each one
  def g(cs, s, seq, i, h):
    if log:
      print "cs, seq, s, i, h: %s, %s, %s, %s, %s" % (cs, s, seq, i, h)

    # Base case, we've achieved a candidate sequence
    if i == len(parents):
      return [(cs, s, seq)]
    # The left character in the corner is
    # arbitrary; the next one, shared.
    # Left corner:
    if i == 0:
      candidates = []
      for (l, r) in combinations(chosen[0].keys(), 2):
        _cs = deepcopy(cs)
        _cs[0] = [1, l, 1]
        _cs[1][1] = r
        _cs[1][2] = 1
        _s = s[:]
        _s.extend([chosen[0][l], chosen[0][r]])
        _h = deepcopy(h)
        # save the indexes in cs of the
        # nodes chosen for the parent 
        _h[parents[1]] = [1, 2]
        candidates.extend(g(_cs, _s, l+r, 1, _h))
        _cs = deepcopy(cs)
        _cs[0] = [1, r, 1]
        _cs[1][1] = l
        _cs[1][2] = 1
        _s = s[:]
        _s.extend([chosen[0][r], chosen[0][l]])
        _h = deepcopy(h)
        # save the indexes in cs of the
        # nodes chosen for the parent
        _h[parents[1]] = [1, 2]
        candidates.extend(g(_cs, _s, r+l, 1, _h))
      if log:
        print "returning candidates: %s" % candidates
      return candidates
    # The right character is arbitrary but the
    # character before it must match the previous one.
    if i == len(parents)-1:
      l = cs[len(cs)-2][1]
      if log:
        print "rightmost_char: %s" % l
      if len(chosen[i]) < 2 or (not l in chosen[i]):
        if log:
          print "match not found: len(chosen[i]) < 2 or (not l in chosen[i])"
        return []
      else:
        result = []
        for r in [x for x in chosen[i].keys() if x != l]:
          _cs = deepcopy(cs)
          _cs[len(cs)-2][2] = _cs[len(cs)-2][2] + 1
          _cs[len(cs)-1] = [1, r, 1]
          _s = s[:] + [chosen[i][l], chosen[i][r]]
          result.append((_cs, _s, seq + l + r))
        return result

    parent = parents[i]
    if log:
      print "get_candidates: g: parent, i: %s, %s" % (parent, i)
    _h = deepcopy(h)
    if not parent in _h:
      prev = _h[parents[i-1]]
      _h[parent] = [prev[0] + 1, prev[1] + 1]
    # parent left and right children
    pl, pr = _h[parent]
    if log:
      print "pl, pr: %s, %s" % (pl, pr)
    l = cs[pl][1]
    if log:
      print "rightmost_char: %s" % l
    if len(chosen[i]) < 2 or (not l in chosen[i]):
      if log:
        print "match not found: len(chosen[i]) < 2 or (not l in chosen[i])"
      return []
    else:
      # "Base case," parent nodes have been filled
      # so this is a duplicate character on the same
      # row, which needs a new assignment
      if cs[pl][0] == cs[pl][2] and cs[pr][0] == cs[pr][2]:
        if log:
          print "TODO"
        return []
      # Case 2, right child is not assigned
      if not cs[pr][1]:
        candidates = []
        for r in [x for x in chosen[i].keys() if x != l]:
          _cs = deepcopy(cs)
          _cs[pl][2] += 1
          _cs[pr][1] = r
          _cs[pr][2] = 1
          _s = s[:]
          _s.extend([chosen[i][l], chosen[i][r]])
          # save the indexes in cs of the
          # nodes chosen for the parent
          candidates.extend(g(_cs, _s, seq+l+r, i+1, _h))
        return candidates
      # Case 3, right child is already assigned
      elif cs[pr][1]:
        r = cs[pr][1]
        if not r in chosen[i]:
          if log:
            print "match not found: r ('%s') not in chosen[i]" % r
          return []
        else:
          _cs = deepcopy(cs)
          _cs[pl][2] += 1
          _cs[pr][2] += 1
          _s = s[:]
          _s.extend([chosen[i][l], chosen[i][r]])
          # save the indexes in cs of the
          # nodes chosen for the parent
          return g(_cs, _s, seq+l+r, i+1, _h)
    # Otherwise, fail 
    return []

  return g(next_needed, [], "", 0, {})

def f(words, n):
  global log
  tree = {}
  for w in words:
    insert(w, 0, tree)

  stack = []
  root = tree[words[0][0]]
  head = words[0][0]
  for (l, r) in combinations(root.keys(), 2):
    # (shared-chars-needed, chosen-nodes, board)
    stack.append(([[1, None, 0],[1, None, 0]], [root[l], root[r]], [head, l + r], [head, l + r]))

  while stack:
    needed, chosen, seqs, board = stack.pop()
    if log:
      print "chosen: %s" % chosen
      print "board: %s" % board
    # Return early for demonstration
    if len(board) == n:
      # [y for x in chosen for y in x[1]]
      return board

    next_needed = get_next_needed(needed)
    candidates = get_candidates(next_needed, chosen, seqs[-1])
    for cs, s, seq in candidates:
      if log:
        print "  cs: %s" % cs
        print "  s: %s" % s
        print "  seq: %s" % seq
      _board = board[:]
      _board.append("".join([x[1] for x in cs]))
      _seqs = seqs[:]
      _seqs.append(seq)
      stack.append((cs, s, _seqs, _board))

"""
    B
   A O
  I R N
 T N E D
Z Y X W V
"""
words = [
  "BONDV",
  "BONDW",
  "BONEW",
  "BONEX",
  "BOREW",
  "BOREX",
  "BAREW",
  "BAREX",
  "BORNX",
  "BORNY",
  "BARNX",
  "BARNY",
  "BAINX",
  "BAINY",
  "BAITY",
  "BAITZ"]
N = 5
log = True

import time
start_time = time.time()
solution = f(list(words), N)
print ""
print ""
print("--- %s seconds ---" % (time.time() - start_time))
print "solution: %s" % solution
print ""
if solution:
  for i, row in enumerate(solution):
    print " " * (N - 1 - i) + " ".join(row)
  print ""
print "words: %s" % words

关于python - 如何从字典中构建比蛮力更好的 Plinko 单词板？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/54271178/