4

我正在尝试创建一个基于 4x4 字母网格的单词生成器（如下）。

与朋友争夺

以下是规则：

  • 字母不能重复
  • 单词必须由相邻的字母组成
  • 单词可以水平，垂直或对角向左，向右或上下形成

目前，我输入 16 个字符并遍历字典中的每个单词，确定该单词是否可以用网格上的字母拼写。 

#!/usr/bin/ruby

require './scores'   # alphabet and associated Scrabble scoring value (ie the wordValue() method)
require './words.rb' # dictionary of English words (ie the WORDS array)

# grab users letters
puts "Provide us the 16 letters of your grid (no spaces please)"
word = gets.chomp.downcase

arr = word.split('')

# store words that can be spelled with user's letters
success = []

# iterate through dictionary of words
WORDS.each do |w|

    # create temp arrays
    dict_arr = w.split('')
    user_arr = arr.dup
    test = true

    # test whether users letters spell current word in dict
    while test
        dict_arr.each do |letter|
            if (user_arr.include?(letter))
                i = user_arr.index(letter)
                user_arr.delete_at(i)
            else
                test = false
                break
            end
        end

        # store word in array
        if test 
            success << w
            test = false
        end
    end

end

# create hash for successful words and their corresponding values
SUCCESS = {}

success.each do |w|
  score = wordValue(w)
  SUCCESS[w] = score
end

# sort hash from lowest to smallest value
SUCCESS = SUCCESS.sort_by {|word, value| value}

# print results to screen
SUCCESS.each {|k,v| puts "#{k}:  #{v}"}

然而，这种方法没有考虑棋盘上棋子的位置。 你会建议我如何寻找可以根据它们在 4x4 网格中的位置创建的单词？

对于上图中的棋盘游戏，我运行 Ubuntu 的 VM 需要大约 1.21 秒来计算 1185 个可能的单词。我在 /usr/share/dict/words 中使用 Ubunut 提供的词典

4

4 回答 4

3

不要遍历单词并搜索它们的存在，而是遍历网格上的每个图块并找到源自该图块的所有单词。

首先，将您的字典编译成trie。尝试在执行前缀匹配字符串比较方面是有效的，这将很快对我们有用。

要在棋盘中查找单词，请对 16 个图块中的每一个执行以下步骤，从 . 的空字符串开始prefix。

  1. 将当前图块的值添加到prefix.
  2. 检查我们的 trie 是否包含任何以prefix.
  3. 如果是，则分支搜索：对于与该图块相邻的每个合法（未访问）图块，返回步骤 1（递归）。
  4. 如果不匹配，请停止此搜索分支，因为没有匹配的单词。
于 2012-09-03T02:08:42.503 回答
1

我会创建一个代表整个董事会的简单图表。字母将是顶点。如果板上的两个字母彼此靠近，我会在它们的顶点之间创建一条边。很容易找出输入是否有效。您只需检查图中是否有匹配的路径。

于 2012-09-02T16:02:36.653 回答
0

我原来的答案不是你想要的。我正在创建网格中所有“单词”的列表，而不是搜索您已经从字典中识别的单词。现在我编写了一个函数，它在网格中搜索特定的单词。它以递归方式工作。

所以，现在算法是：

1) 从用户那里获取 16 个字母
2) 在字典中搜索包含这些字母的所有单词
3) 使用这些单词中的每一个调用 is_word_on_board 以查看是否有匹配项

#!/usr/bin/ruby

# This script searches a board for a word
#
# A board is represented by a string of letters, for instance, the string
# "abcdefghijklmnop" represents the board:
#
#    a b c d
#    e f g h
#    i j k l
#    m n o p
#
# The array ADJACENT lists the cell numbers that are adjacent to another
# cell.  For instance ADJACENT[3] is [2, 6, 7].  If the cells are numbered
#
#     0  1  2  3
#     4  5  6  7
#     8  9 10 11
#    12 13 14 15

ADJACENT = [
    [1, 4, 5],
    [0, 2, 4, 5, 6],
    [1, 3, 5, 6, 7],
    [2, 6, 7],
    [0, 1, 5, 8, 9],
    [0, 1, 2, 4, 6, 8, 9, 10],
    [1, 2, 3, 5, 7, 9, 10, 11],
    [2, 3, 6, 10, 11],
    [4, 5, 9, 12, 13],
    [4, 5, 6, 8, 10, 12, 13, 14],
    [5, 6, 7, 9, 11, 13, 14, 15],
    [6, 7, 10, 14, 15],
    [8, 9, 13],
    [8, 9, 10, 12, 14],
    [9, 10, 11, 13, 15],
    [10, 11, 14]
]

# function:  is_word_on_board
#
# parameters:
#   word   - word you're searching for
#   board  - string of letters representing the board, left to right, top to bottom
#   prefix - partial word found so far
#   cell   - position of last letter chosen on the board
#
# returns true if word was found, false otherwise
#
# Note:  You only need to provide the word and the board.  The other two parameters
# have default values, and are used by the recursive calls.

# set this to true to log the recursive calls
DEBUG = false

def is_word_on_board(word, board, prefix = "", cell = -1)
    if DEBUG
        puts "word = #{word}" 
        puts "board = #{board}"
        puts "prefix = #{prefix}"
        puts "cell = #{cell}"
        puts
    end

    # If we're just beginning, start word at any cell containing
    # the starting letter of the word
    if prefix.length == 0
        0.upto(15) do |i|
            if word[0] == board[i]
                board_copy = board.dup
                newprefix = board[i,1]

                # put "*" in place of letter so we don't reuse it
                board_copy[i] = ?*

                # recurse, and return true if the word is found
                if is_word_on_board(word, board_copy, newprefix, i)
                    return true
                end
            end
        end

        # we got here without finding a match, so return false
        return false
    elsif prefix.length == word.length
        # we have the whole word!
        return true
    else
        # search adjacent cells for the next letter in the word
        ADJACENT[cell].each do |c|
            # if the letter in this adjacent cell matches the next
            # letter of the word, add it to the prefix and recurse
            if board[c] == word[prefix.length]
                newprefix = prefix + board[c, 1]
                board_copy = board.dup

                # put "*" in place of letter so we don't reuse it
                board_copy[c] = ?*

                # recurse, and return true if the word is found
                if is_word_on_board(word, board_copy, newprefix, c)
                    return true
                end
            end
        end

        # bummer, no word found, so return false
        return false
    end
end

puts "Test board:"
puts
puts "  r u t t"
puts "  y b s i"
puts "  e a r o"
puts "  g h o l"
puts

board = "ruttybsiearoghol"

for word in ["ruby", "bears", "honey", "beast", "rusty", "burb", "bras", "ruttisbyearolohg", "i"]
    if is_word_on_board(word, board)
        puts word + " is on the board"
    else
        puts word + " is NOT on the board"
    end
end

运行此脚本会产生以下结果：

Test board:

  r u t t
  y b s i
  e a r o
  g h o l

ruby is on the board
bears is on the board
honey is NOT on the board
beast is on the board
rusty is NOT on the board
burb is NOT on the board
bras is on the board
ruttisbyearolohg is on the board
i is on the board
于 2012-09-02T19:04:25.503 回答
0

我碰巧有一个我不久前写的 Boggle 求解器。它遵循 Cheeken 的大纲。它的调用方式略有不同（您提供单词列表文件和带有 4x4 网格的文本文件作为参数），但我认为它值得分享。另请注意，它将“Q”视为“QU”，因此其中有一些额外的逻辑。

require 'set'

def build_dict(dict, key, value)
  if key.length == 0
    dict[:a] = value
  else
    if key[0] == "q"
      first = key[0..1]
      rest = key[2, key.length - 1]
    else
      first = key[0]
      rest = key[1, key.length - 1]
    end

    dict[first] = {} unless dict.has_key? first
    build_dict(dict[first], rest, value)
  end
end

dict = {}
#parse the file into a dictionary
File.open(ARGV[0]).each_line do |line|
  real_line = line.strip
  build_dict(dict, real_line, real_line)
end

#parse the board
board = {}
j = 0
File.open(ARGV[1]).each_line do |line|
  line.chars.each_with_index do |l, i|
    board[[j, i]] = l
  end
  j += 1
end

#(0..3).each{|r| puts (0..3).map{|c| board[[r, c]]}.join}

#how can i get from one place to another?
def get_neighbors(slot, sofar)
  r, c = slot
  directions =
   [
    [r+1, c],
    [r+1, c+1],
    [r+1, c-1],
    [r, c+1],
    [r, c-1],
    [r-1, c],
    [r-1, c+1],
    [r-1, c-1]
   ]
  directions.select{|a| a.all?{|d| d >= 0 && d <= 3} && !sofar.include?(a)}
end

#actual work
def solve(board, slot, word_dict, sofar)
  results = Set.new
  letter = board[slot]
  letter = "qu" if letter == "q"
  stuff = word_dict[letter]
  return results if stuff.nil?
  if stuff.has_key? :a
    results << stuff[:a] if stuff[:a].length > 2
  end
  unless stuff.keys.select{|key| key != :a}.empty?
    get_neighbors(slot, sofar).each do |dir|
      results += solve(board, dir, stuff, sofar.clone << slot)
    end
  end
  results
end

#do it!
results = Set.new
all_slots = (0..3).to_a.product((0..3).to_a)
all_slots.each do |slot|
  results += solve(board, slot, dict, slot)
end

puts results.sort
于 2012-09-03T02:20:54.697 回答