ruby – 4×4字母网格 – 单词生成器 – 与朋友争夺

那么,现在的算法是：

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,5,6],[1,3,7],[2,1,8,9],9,10],7,10,11],[4,12,13],13,14],[5,11,14,15],[6,[8,[9,[10,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,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