给定一组16个字母和一个英文字典文件,需要找到一个解决方案,其中这16个字母可以放入4×4网格中,以便可以在每行和每列下读取有效字.
我目前的解决方案
1)获取可以用这些字母(anagram generator)制作的所有可能的4个字母单词的列表,并将它们分配给数组.
2)循环遍历每个单词,在每一行中尝试它,同时检查每个单词的正确数量是否被使用.
3)检查anagram数组中是否存在每列中创建的单词.
逻辑工作,但它已经运行了一个多小时,我在400字节的字谜词200.有什么建议？
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','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]))
{
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]))
{
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;
}
}
}
这是一个例子,按要求：
给定字母“N,O,O和T”找到一个解决方案,其中这些字母适合2×2网格,以便在横向和向下阅读时,可以创建英文单词.答案是：
T O O N
除了这个问题是4×4网格.
更新：谢谢你的帮助,但我是个白痴.我没有修复我的复制/粘贴变量(我想,这可以追溯到那个建议我重构的人).此外,我比较数组的方式是错误的.修正了这些问题,并针对已知的工作单词列表,像魅力一样工作.再次对着我的原始数据,花了13秒.没有结果.再次感谢你的帮助.
更新2：由于我没有足够的代表回答我自己的问题,这是我的工作代码(…代码已删除…请参阅下面的dasblinklight的答案)
更新3：请参阅下面的dasblinkenlight的答案.更优雅,更少的循环.谢谢！
解决方法
您不需要嵌套七个级别,您只需要五个：四个循环来尝试所有适合16个字母集的单词组合,以及一个额外的循环来检查选择所暗示的四个垂直组合横向的话.
您需要一种有效的方法来管理您当前使用的字母集.处理它的一种方法是创建一个计数器数组,如下所示：
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)尝试从计数中“减去”该单词,如果成功则返回true.添加(字符串)将单词添加回计数.
现在您可以编写代码的四向嵌套框架,如下所示：
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);
}
垂直单词的检查会添加第五个和最后一个嵌套级别.我将单词转换为哈希集以加快检查：
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();
}
您可以找到this program on the pastebin.它可以在我的计算机上完成几分钟而无需生成解决方案.我确认它找到了存在的解决方案(但是当您注释掉单词和字母并取消注释最后两行时,程序会找到有效组合及其转置图像).
