create a Crossword puzzle

Write a function that helps solve word search puzzles. Your function should search a 2-dimensional array of characters to find a specified word. If the word is found, the function should return the indices of the first character of the word and the direction of the word in the puzzle (e.g. across, down, diagonals, and their reverses). If the word is not found, the function should return values indicating that fact, such as -1 for all return values.

Ive worked on this for hours but I still have barely any progress. I tried experimenting with strfind and ismember but the word im searching for is not the same size as the array that contains the characters, so i dont get the specific row and i have no clue how to look for the direction. any help is appreciated

Answer 1

[Image Analyst]

John: Try this. Perhaps this is Walter's idea. It's a start. You can finish it by doing the diagonals.

% Create sample array of characters
m = char(randi([65, (65+25)], 100,100));
[rows, columns] = size(m)
% Define what words you want to search for
wordList = {'BA', 'FW', 'ST', 'XV'} % Whatever.....
% Go down rows looking for the words in the word list.
for row = 1 : rows
  thisRow = m(row, :);
  for w = 1 : length(wordList)
    columnLocation = strfind(thisRow, wordList{w});
    if ~isempty(columnLocation)
      fprintf('Found %s in row %d, column %d.\n', wordList{w}, row, columnLocation);
    else
      fprintf('Did not find %s in row %d.\n', wordList{w}, row);
    end
  end
end

% Go down columns looking for the words in the word list.
for col = 1 : rows
  thisRow = m(:, col)';  % Need to transpose
  for w = 1 : length(wordList)
    rowLocation = strfind(thisRow, wordList{w});
    if ~isempty(rowLocation)
      fprintf('Found %s in column %d, row %d.\n', wordList{w}, col, rowLocation);
    else
      fprintf('Did not find %s in column %d.\n', wordList{w}, col);
    end
  end
end
% Now do the same both diagonals in both directions, +45 and -45.

Answer 2

[Image Analyst]

for a word search puzzle (not a crossword puzzle) I'd have at least 4 nested for loops. One over rows, one over columns, and one over angles. For each character, for each angle, extract a complete line through every place in the array that it can. Like horizontal, vertical, and two diagonals. Then on those 4 strings, use strfind() to search it for all unused words.

for row = 1 : rows
    for col = 1 : columns
        for angles = 1 : 4 % vertical, horizontal, +45 and -45
             thisString = extractString(row, column, angle);
             for w = 1 : numWords
                  foundIt = strfind(thisString, words{w});
             end
        end
    end
end

There are some (or a lot of) details for you to work out but that's how I'd approach it.

Answer 3

[Walter Roberson]

You do not need 4 nested loops. You only need unnested loops.

You can split the matrix into rows and columns easily enough using mat2cell(). You can also split into diagonals and anti-diagnonals using diag(). (For more examples showing diag on a matrix see http://www.mathworks.com/matlabcentral/answers/241511-my-work-is-feature-extraction-for-character-recognition-i-have-to-split-100-100-binary-image-into-di)

For any one extracted vector of characters, you can use strfind() of both the forward word and the reverse word. If there is a match then your knowledge of the section you are examining together with the direction will allow you to find the index of the first character; return it and the direction.

If you want to get fancier or more efficient, pull out a "zig-zag scan" routine from the File Exchange and use it against the character array padded on all sides with a character known not to appear in the search string (could even be space). You can search the resulting character vector of all the diagonal elements with a single strfind() (and search for the reversed word with a second strfind() call). The rest is just book-keeping about converting the indices located to original matrix positions.

[Image Analyst]

Yes, that's a more clever solution than I though of. Less redundant since my method would search the same line multiple times unnecessarily. I was just kind of replicating how I do it visually when I'm looking for a word. If I don't see it right away then I resort to a character by character 2-D scan. But a computer can do it more efficiently.

[John Do]

Could you explain this with code?

[Walter Roberson]

for diagnumber = -15 : +15
  locations = strfind( targetword, diag(letters_matrix, diagnumber).' );
  if ~isempty(locations)
     found the word! figure out where it was at this point
     break;   %we are done
  end
end