My iteration lasts forever. Look for the best way

Question

For a set of sixteen letters and an English dictionary file, it is necessary to find a solution in which these sixteen letters can fit into a 4x4 grid so that a reliable word can be read on each line and down for each column.

My current solution:

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

2) Scroll through each word, trying it on each line, checking that the correct number of each letter is used.

3) Checking for the presence of a word created in each column in the anagram array.

Logic works, but it works for more than an hour, and I am in the word 200 out of 400 + anagrams array. 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 in which these letters fit into a 2x2 grid, so that when reading through and down, English words can be created. The answer will be as follows:

 TO ON 

Except for this problem for a 4x4 grid.

UPDATE: Thanks for your help, but I'm an idiot. I have not fixed my copied / pasted variables (which, I suppose, goes back to the guy who suggested me refactoring). Also, the wrong way to compare arrays. Fixed these problems and worked against a well-known list of working words, worked like a charm. Ran again against my original data, took 13 seconds. No results. Thanks again for your help.

UPDATE 2: Since I do not have enough answers to answer my own question, here is my working code (... the code has been deleted ... see dasblinklight answer below)

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

Answer 1

You do not need to insert seven levels, you only need five: four loops to try all four-sided combinations of words that correspond to a 16-letter set, and an additional cycle to check four vertical combinations, the implied choice of horizontal words.

You need an effective way to manage the set of letters that you are currently using. One way to deal with it is to create an array of counters, for example:

 static readonly int[] Counts = new int[256]; static void Add(string s) { foreach (var c in s) { Counts[c]++; } } static bool Sub(string s) { var res = true; foreach (var c in s) { res &= --Counts[c] >= 0; } if (!res) { Add(s); } return res; } 

Sub(string) tries to “subtract” the word from the counts and returns true if it succeeds. Add(string) adds the word back to the counters.

Now you can write a four-position nested skeleton of your code, for example:

 foreach (var w0 in Words) { if (!Sub(w0)) continue; foreach (var w1 in Words) { if (!Sub(w1)) continue; foreach (var w2 in Words) { if (!Sub(w2)) continue; foreach (var w3 in Words) { if (!Sub(w3)) continue; // Check if the w0..w3 combination yields four valid words // when you read it vertically, and restore the state Add(w3); } Add(w2); } Add(w1); } Add(w0); } 

Checking vertical words adds a fifth and final level of nesting. I converted the words to a hash set to speed up validation:

 var allExist = true; for (var i = 0; allExist && i != 4; i++) { vert[0] = w0[i]; vert[1] = w1[i]; vert[2] = w2[i]; vert[3] = w3[i]; allExist = Words.Contains(new string(vert)); } if (allExist) { found = true; Console.WriteLine(w0); Console.WriteLine(w1); Console.WriteLine(w2); Console.WriteLine(w3); Console.WriteLine(); } 

You can find this program on pastebin . It ends in a few minutes on my computer without creating a solution. I confirmed that I find solutions when they exist, although (when you comment on Words and Letters and uncomment the last two lines, the program finds both a valid combination and its transposed image).

Answer 2

Use a reverse tracking algorithm.

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

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

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

Here is what you do. Suppose the grid

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

You start with your sixteen letters: for example, IDNVJGIEKGEESSSO.

make an assumption about what happens at 11. Say I.

Now this limits what can go to 12 and 21. Only those letters from words that begin with me and have a second letter from the remaining letters DNVJGIEKGEESSSO can be at 12 and 21. This makes the problem extremely difficult.

Now make an assumption for 12. Say, D. This limits 13 and 22, which further holds back the problem.

Now make an assumption for 21, say, N, which limits 22 (again) and 31.

Now make an assumption for 22. It cannot be V, J or G, because not a word begins with NV, NJ or NG. Maybe it's me ...

Continue to do this until you find a solution, or you find yourself in a situation where there is no possible solution. If there is a solution, everything is ready. If there are no possible solutions, given your guesses, you should go back to the previous assumption and make another assumption until all possible guesses are exhausted. Then back off again. Etc. The key is to quickly reduce the number of possibilities for each hypothesis.

Answer 3

The most important thing is to reduce the investment, if possible.

If this is not possible, you should at least try to tear out as many heavy objects as possible from the loops.
The first thing that comes to my mind is all things. Pre-calculate word.ToCharArray() for each word in words and save the new char[][] wordCharacterArrays array in them. Then you save a lot of calculations.

Also print all col1.ToLower() , etc. only under each definition, for example

  string col1 = new string(new char[] { row1[0], row2[0], row3[0], row4[0] }); string col1Lower = col1.ToLower(); 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] }); string col2Lower = col2.ToLower(); 

etc. and reuse these values ​​later to save a ton of repetitive calculations here.

Answer 4

When it comes to things, it's just a permutation of 16 characters. This way you will have some character order

  abcd efgh ijkl mnop 

The square here, in fact, is almost incorrect. In addition to each of the four letter groups, the nth character of each group must also form a word. Therefore, instead of trying to put letters in squares, which would be a waste of time, instead, you could start forming permutations based on input, and similar things can be parallelized. Given your set of anagrams, this is a quick set operation to find those permutations that do not contain anagram grouping. Once a candidate is found, you can check the nth characters for words. Continue this way until the nth character matches.

Once a match is found, you can write the string to a 2d array.