4x4 Grid of Letters - Word Generator - Fighting Friends

Question

I am trying to create a word generator based on a 4x4 grid (below).

Here are the rules:

• Letters cannot be repeated
• Words must be formed by adjacent letters
• Words can be formed horizontally, vertically, or diagonally from left, right, or up and down.

I am currently taking a 16-character input and loop through each word in the dictionary, determining whether this word can be written in letters on a grid.

#!/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 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}"} 

However, this approach does not take into account the position of the tiles on the board. How would you advise me to look for words that can be created based on their location in a 4x4 grid?

For the board game in the image above, it takes about 1.21 seconds for my Ubuntu virtual machine to calculate 1185 possible words. I use a dictionary of words provided with Ubunut in / usr / share / dict / words

Answer 1

My original answer was not what you wanted. I created a list of all the “words” in the grid, instead of looking for words that you already defined from the dictionary. Now I have written a function that searches for a grid for a specific word. It works recursively.

So now the algorithm:

1) Receive 16 letters from the user
2) A search dictionary for all words with these letters
3) Call is_word_on_board with each of these words to find out if you have a match

 #!/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: # # abcd # efgh # ijkl # mnop # # 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 " rutt" puts " ybsi" puts " earo" puts " ghol" 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 

Running this script gives the following results:

 Test board: rutt ybsi earo ghol 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 

Answer 2

Instead of repeating the words and looking for their presence, go through each plate on the grid and find all the words arising from this tile.

First compile the dictionary into trie . Traffic jams are effective in performing string comparisons mapped to prefixes, which will be useful to us in the near future.

To find words inside the board, follow these steps for each of the 16 snippets, starting with the empty line for prefix .

• Add the current tile value to prefix .
• Check if our trie contains words starting with prefix .
• If so, open the search: for each legal (invisible) tile that is next to that tile, return to step 1 (recursion).
• If this does not match, stop this search branch because there are no matching words.

Answer 3

I would create a simple graph representing the entire board. Letters will be vertices. If two letters are next to each other on the board, I would create an edge between their vertices. It would be very easy to find out if the entry is valid. You just need to check if the corresponding path exists in the chart.

Answer 4

I seem to have a Boggle solver that I wrote some time ago. This follows from Cheken's plan. It gets called a little differently (you supply a word list file and a text file with a 4x4 grid as arguments), but I decided it was worth it. Also note that it refers to “Q” as “QU”, so there is additional logic for this.

 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