What is an effective method of traversing a 2d Array vertically to programatically find an "empty" set?

Question

First off, this isn't homework ;). I'm trying to create a wordsearch game from scratch and have hit a barrier I need some guidance on.

I'm using a 2d array of chars to for the grid of a wordsearch. I'm quite comfortable with placing words in these arrays horizontally, but I'm really stuck for ideas on how to do this vertically.

This is what I have so far, you should just be able to copy/paste it and run it

import java.util.ArrayList;
import java.util.List;

public class WordGame
{
    private static List<String> words = new ArrayList<String>();
    private static int longestWordLength = 0;
    private static int padSize = 4;
    private static char[][] grid = null;

    public static void main(String[] args)
    {
        initialiseWords();
        workOutLongestWord();
        setupGrid();
        printIt();
    }

    private static void printIt()
    {
        for (int i = 0; i < grid.length; i++)
        {
            for (int j = 0; j < grid.length; j++)
            {
                System.out.print(grid[i][j]);
            }
            System.out.print("\n");
        }
    }

    private static void setupGrid()
    {
        grid = new char[longestWordLength + padSize][longestWordLength + padSize];

        for (int i = 0; i < grid.length; i++)
        {
            String w = (i >= words.size()) ? "?" : words.get(i);
            for (int j = 0; j < grid.length; j++)
            {
                grid[i][j] = (j >= w.length()) ? '?' : w.charAt(j);
            }
        }
    }

    private static void workOutLongestWord()
    {
        for (String word : words)
        {
            if (word.length() > longestWordLength)
            {
                longestWordLength = word.length();
            }
        }
    }

    private static void initialiseWords()
    {
        words.add("monkey");
        words.add("cow");
        words.add("elephant");
        words.add("kangaroo");
    }
}

Which prints out something like ...

monkey??????
cow?????????
elephant????
kangaroo????
????????????
????????????
????????????
????????????
????????????
????????????
????????????
????????????

I need to randomly pad them out on the left/right hand side, but I can do that myself.

Question : What is an effective way of attempting to place words vertically into a 2d array like the above? My initial thought was to count downwards for the required word length, breaking if anything other than a ? is found, and to keep doing this until I can find a space for the word. However this doesn't get pretty once I take into account word overlapping.

Any pointers?

Answer 1

I did a similar problem in C when implementing "Battleship". Different ships were different sizes and you couldn't have them intersect.

Once you have vertical words you will need to check if your horizontal words hit them as well.

I suggest making a "Word" class which is a thin class around String. You just need to keep track of the following.

1. x,y position / index in the world
2. What the word is
3. the length of the word ( given to you by String in Java )
4. The orientation of the word ( up down left right )

You then make a method, that validates the word placement. E.G, The whole word has to be on the board, and there isn't a collision. You can model word collision by a series of line segments. This could be done by using rect to rect collision algorithms, where one dimension is almost 1.