My iteration is taking forever. Looking for a better way

Question

Given a set of sixteen letters and an English dictionary file, need to find a solution where those sixteen letters can fit into a 4x4 grid so that a valid word can be read across each row, and down each column.

My current solution:

1) Get a list of all of the possible 4-letter words that can be made with those letters (anagram generator) and assign them to an array.

2) Loop through each word, trying it in every row, while checking that the correct number of each letter is used.

3) Checking if the word created in each column exists in the anagram array.

The logic works, but it's been running over an hour and I'm on word 200 of the 400+ array of anagrams. Any suggestions?

namespace GridWords
{
    class Program
    {
        static void Main(string[] args)
        {
            string[] words = new string[] { "zoon", "zonk", "zone", "zona", "zoea", "zobo", "zero", "zerk", "zeal", "zack", "rore", "roon", "rook", "rood", "rone", "role", "roke", "roed", "rode", "rock", "roch", "robe", "roar", "roan", "road", "rhea", "rend", "redo", "reck", "rear", "rean", "real", "reak", "read", "raze", "rare", "rank", "rand", "rana", "rale", "rake", "rade", "rack", "rach", "race", "raca", "orzo", "orra", "orle", "ordo", "orca", "oral", "orad", "ooze", "oner", "once", "oleo", "olea", "olde", "okra", "okeh", "ohed", "odor", "odea", "odal", "odah", "oche", "obol", "oboe", "nork", "noob", "nook", "nolo", "nole", "noel", "node", "nock", "nerk", "nerd", "neck", "near", "neal", "naze", "nark", "nare", "nard", "narc", "nala", "nada", "nach", "nabk", "nabe", "lorn", "lore", "lord", "loor", "loon", "look", "lone", "loke", "lode", "loco", "lock", "loch", "loca", "lobo", "lobe", "loan", "load", "leno", "lend", "lehr", "lech", "lear", "lean", "leak", "lead", "lazo", "laze", "larn", "lark", "lare", "lard", "lank", "lane", "land", "lana", "lakh", "lake", "laer", "lade", "lack", "lace", "krab", "kore", "kora", "kond", "kolo", "kola", "kohl", "koel", "kobo", "koan", "knob", "knar", "khor", "khan", "kern", "kerb", "keno", "kbar", "karn", "kara", "kaon", "kane", "kana", "kale", "kaed", "kade", "horn", "hore", "hora", "hoon", "hook", "hood", "honk", "hone", "hond", "holk", "hole", "hold", "hoke", "hoer", "hoed", "hock", "hobo", "hoar", "hero", "hern", "herl", "herd", "herb", "hend", "helo", "held", "heck", "hear", "heal", "head", "haze", "haro", "harn", "harl", "hark", "hare", "hard", "hank", "hand", "halo", "hale", "hake", "haka", "haen", "haed", "hade", "hack", "haar", "eorl", "eoan", "enol", "elan", "ecod", "echo", "ecad", "ebon", "earn", "earl", "eard", "each", "dzho", "drek", "drab", "doze", "dorr", "dork", "dore", "door", "dool", "dook", "doob", "done", "dona", "dole", "doer", "doen", "doek", "dock", "doab", "dhal", "dhak", "dern", "deco", "deck", "dear", "dean", "deal", "daze", "darn", "darl", "dark", "dare", "darb", "dank", "dale", "dahl", "dace", "daal", "czar", "cred", "cran", "crab", "coze", "corn", "cork", "core", "cord", "coon", "cool", "cook", "conk", "cone", "cond", "cole", "cold", "cola", "coke", "coho", "coed", "code", "coda", "coal", "clon", "clod", "clan", "clad", "chon", "chez", "cher", "char", "chao", "chal", "chad", "cero", "carr", "carn", "carl", "cark", "care", "card", "carb", "cane", "calo", "calk", "cake", "cade", "caba", "broo", "brod", "brer", "bren", "bred", "bran", "brae", "brad", "bozo", "born", "bork", "bore", "bord", "bora", "boor", "boon", "bool", "book", "booh", "bonk", "bone", "bond", "bona", "bolo", "bole", "bold", "bola", "boko", "boke", "boho", "bode", "bock", "boar", "boak", "bloc", "bled", "blah", "blae", "blad", "bhel", "berk", "bend", "beck", "bear", "bean", "beak", "bead", "barn", "bark", "bare", "bard", "bank", "bane", "band", "banc", "balk", "bale", "bald", "bake", "bael", "bade", "back", "bach", "baal", "azon", "azan", "arna", "arle", "ared", "area", "arco", "arch", "arba", "arar", "arak", "anoa", "ankh", "ance", "anal", "aloe", "alod", "alec", "albe", "alba", "alar", "alan", "alae", "aked", "ahed", "aero", "aeon", "adze", "acre", "acne", "ache", "acer", "aced", "able", "abed", "abac" };
            char[] letters = new char[] { 'a', 'a', 'b', 'c', 'd', 'e', 'h', 'k', 'l', 'n', 'o', 'o', 'o', 'r', 'r', 'z' };
            for (int z = 0; z < words.Length; z++)
            {
                Console.WriteLine(z);
                for (int y = 0; y < words.Length; y++)
                {
                    bool letterCountCorrect0 = true;
                    char[] wordLetters0 = words[z].ToCharArray().Concat(words[y].ToCharArray()).ToArray();
                    for (int a = 0; a < wordLetters0.Length; a++)
                    {
                        if (countInstances(wordLetters0, wordLetters0[a]) != countInstances(letters, wordLetters0[a]))
                        {
                            letterCountCorrect0 = false;
                            break;
                        }
                    }
                    if (y != z && letterCountCorrect0)
                    {
                        for (int x = 0; x < words.Length; x++)
                        {
                            bool letterCountCorrect1 = true;
                            char[] wordLetters1 = words[z].ToCharArray().Concat(words[y].ToCharArray()).Concat(words[x].ToCharArray()).ToArray();
                            for (int a = 0; a < wordLetters0.Length; a++)
                            {
                                if (countInstances(wordLetters0, wordLetters0[a]) != countInstances(letters, wordLetters0[a]))
                                {
                                    letterCountCorrect1 = false;
                                    break;
                                }
                            }
                            if (x != y && x != z && letterCountCorrect1)
                            {
                                for (int w = 0; w < words.Length; w++)
                                {
                                    bool letterCountCorrect2 = true;
                                    char[] wordLetters2 = words[z].ToCharArray().Concat(words[y].ToCharArray()).Concat(words[x].ToCharArray()).Concat(words[w].ToCharArray()).ToArray();
                                    for (int a = 0; a < wordLetters0.Length; a++)
                                    {
                                        if (countInstances(wordLetters0, wordLetters0[a]) != countInstances(letters, wordLetters0[a]))
                                        {
                                            letterCountCorrect2 = false;
                                            break;
                                        }
                                    }
                                    if (w != x && w != y && w != z && letterCountCorrect2)
                                    {
                                        char[] row1 = words[z].ToCharArray();
                                        char[] row2 = words[y].ToCharArray();
                                        char[] row3 = words[x].ToCharArray();
                                        char[] row4 = words[w].ToCharArray();
                                        char[] wordLetterArray = row1.Concat(row2).Concat(row3).Concat(row4).ToArray();
                                        Array.Sort(wordLetterArray);
                                        if (wordLetterArray == letters)
                                        {
                                            string col1 = new string(new char[] { row1[0], row2[0], row3[0], row4[0] });
                                            if (col1 != words[z] && col1 != words[y] && col1 != words[x] && col1 != words[w])
                                            {
                                                string col2 = new string(new char[] { row1[1], row2[1], row3[1], row4[1] });
                                                if (col2 != words[z] && col2 != words[y] && col2 != words[x] && col2 != words[w])
                                                {
                                                    string col3 = new string(new char[] { row1[2], row2[2], row3[2], row4[2] });
                                                    if (col3 != words[z] && col3 != words[y] && col3 != words[x] && col3 != words[w])
                                                    {
                                                        string col4 = new string(new char[] { row1[3], row2[3], row3[3], row4[3] });
                                                        if (col4 != words[z] && col4 != words[y] && col4 != words[x] && col4 != words[w])
                                                        {
                                                            if (words.Contains<String>(col1.ToLower()) && words.Contains<String>(col2.ToLower()) && words.Contains<String>(col3.ToLower()) && words.Contains<String>(col4.ToLower()))
                                                            {
                                                                Console.WriteLine(new string(row1) + " " + new string(row2) + " " + new string(row3) + " " + new string(row4));
                                                                //Console.WriteLine(col1.ToString() + " " + col2.ToString() + " " + col3.ToString() + " " + col4.ToString());
                                                            }
                                                        }
                                                    }
                                                }

                                            }
                                        }
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }

        private static int countInstances(char[] arrToSearch, char charToFind)
        {
            int count = 0;
            for (int x = 0; x < arrToSearch.Length; x++)
            {
                if (arrToSearch[x] == charToFind)
                {
                    count++;
                }
            }
            return count;
        }
    }
}

Here is an example, as requested:

Given the letters "N, O, O, and T" find a solution where these letters fit into a 2x2 grid so that when read across and down, English words can be created. The answer would be:

T O
O N

Except this problem is for a 4x4 grid.

UPDATE: Thanks for your help, but I'm an idiot. I didn't fix my copy/pasted variables (which, I suppose, goes back to the guy who suggested I refactor). Also, the way I was comparing arrays was faulty. Fixed these issues and ran against known working word list, worked like a charm. Ran again against my original data, took 13 seconds. No results. Thanks again for your help.

UPDATE 2: Since I don't have enough rep to answer my own question, here is my working code (...code deleted...see dasblinklight's answer below)

UPDATE 3: Please see dasblinkenlight's answer below. Much more elegant, fewer loops. Thanks!

Answer 1

Use a backtracking algorithm.

Start by reading my series of articles on how to use a backtracking algorithm to solve the graph colouring problem:

http://blogs.msdn.com/b/ericlippert/archive/tags/graph+colouring/

You do not have exactly the same problem, but it is very close.

Here's what you do. Suppose the grid is

11 12 13 14
21 22 23 24
31 32 33 34
41 42 43 44

You start with your sixteen letters: IDNVJGIEKGEESSSO, say.

make a guess as to what goes in 11. Say, I.

That now constrains what can possibly go in 12 and 21. Only those letters from words that begin with I and have a second letter from the remaining letters DNVJGIEKGEESSSO can be in 12 and 21. That enormously constrains the problem.

Now make a guess for 12. Say, D. That then constrains 13 and 22, further constraining the problem.

Now make a guess for 21, say, N, which constrains 22 (again) and 31.

Now make a guess for 22. It can't be V, J or G because no words begin NV, NJ or NG. Maybe it is I...

Keep doing that until you either find a solution, or you end up in a situation where there is no possible solution. If there is a solution, you're done. If there is no possible solution given the guesses you've made, you must backtrack to the previous guess and make a different guess until all possible guesses are exhausted. Then backtrack again. And so on. The key is to lower the number of possibilities for each guess quickly.