我正在尝试制作一种算法来填充方阵中给定单词的列表，其中字母数量等于矩阵大小。
这里的诀窍是你应该能够连接每个单词（每个字母与他后面的字母在同一个单词中）并且在连接结束时应该清除板。（每个单词都是独立的 - 不与其他单词连接）。
您可以连接一个单词：如果它的字母是邻居 - （邻居可以是：左、右、上、下、左上、右上、左下、右下）。你应该按顺序连接字母，不能跳过字母。（就像在纸上画一条线而不移除铅笔）并且在连接一个单词时你不能超越另一个单词的其他字母。
当一个单词连接起来时，它就会从板上删除——并且其字母上方的每个字母都会掉下来取而代之（例如：字母不能飞）。每个都将落在另一个之上，而不是在矩阵中的相同位置。
单词不必在第一次看板时就全部连接起来 - 所以：它们应该是可连接的，而其他单词是连接的 - 然后它的字母将是邻居。
这是董事会应该是什么样子的一个例子：
图像中的板是由我编写的算法生成的，它在 1-10 秒内生成一个 5X5 板，这对于计算机来说太多了。我遇到的问题是 7X7 和更大的板需要“无限”时间才能生成，但我无法生成任何 7X7 板。
另一个注意事项：一块板不应该遵循在所有板上重复的模式，并且最好不要遵循模式。
我在互联网上搜索了几天，找不到解决此类问题的文章。启动代码时我的 CPU 使用率约为 1.1%。我不知道为什么要花很多时间。
我正在使用递归算法，这是控制世代的主要功能：
public void Build()
{
// Sort words from The longest to the shortest
sortWords();
//convert list of words to string
string words = ListToString(this.words);
// Get The Result of the generation function.
bool result = Generate(words, null);
}
private Random random = new Random();
private bool Generate(string words, Word word)
{
// If [words = null], Then The function failed to generate a board from no words.
if (words == null)
return false;
// If got to the end of the words, Then succedd to fill all words in the board
if (words.Length == 0)
return true;
// If Got [" "] blank letter, Then should switch to the next word.
if (words[0].ToString() == " ")
{
board.changedWord(); // Delegate: Update UI
return Generate(words.Substring(1, words.Length - 1), null);
}
// If [word = null], Then we are creating a new word
if (word == null)
word = new Word(board);
// Check If there is a group of letters that can't connect with other letters
// and they cann't contain any word in them.
if (board.isLocked(minInString(words)))
return false;
// Store all available legal neighbours to the previus added letter
List<Location> neighbours = new List<Location>();
if (word.Length == 0) { // This is a new word -> Any Cell would be legal
neighbours = board.FreeLocations();
}
else { // This word is in progress. Neighbours rules should be applied
neighbours = board.Neighbours(word.Letters.Last().Location);
}
if (neighbours.Count == 0) { // If found no neighbours, Then cant continue with the current word
return false;
}
int index = 0; // Shoiuld hold letter index in word - has nothing to do right now. initail value [0].
while (neighbours.Count > 0)
{ // Try each one of the suggested neighbours
// Get a random neighbour from available legal neighbours
int randLocationIndex = random.Next(neighbours.Count);
Location location = neighbours[randLocationIndex];
// If word wasn't added to the words, add it!
if (!board.Words.Contains(word))
board.Words.Add(word);
// Add the current letter to the related word in board
board.Add(new Letter(word, location, words[0].ToString(), index), word);
if (!word.isValid()) {
// Check if current word can be connected,
//Its own letters doesn't make any problem to each other.
board.Remove(word.Letter(word.Length - 1));
neighbours.RemoveAt(randLocationIndex);
continue;
}
if (!board.Solved()) {
// Check if the board is solvable [Gravity cases]
// -> Check each word that devides the connection between current word, that its connectable
board.Remove(word.Letter(word.Length - 1));
neighbours.RemoveAt(randLocationIndex);
continue;
}
// Try the letters after me.
bool result = Generate(words.Substring(1, words.Length - 1), word);
// If all words after this, succeded, then me and sons succeded, return true.
if (result == true)
return true;
else { // Remove added point from word's path, Remove it from available neighbours
board.Remove(word.Letter(word.Length - 1));
neighbours.RemoveAt(randLocationIndex);
}
}
// If Current Word has added no letters to board: then remove it from board
// we dont need any empty useless word in the board.
if (word.Length == 0) {
//board.CancelWord(); Delegate: Update Board UI
board.Words.Remove(word);
}
// Tryed all sugested neighbours for current letter, all of them has failed
// retuen false - Thats a fail :(
return false;
}
我可以读/写 c#、C++、C、Java、Swift 和 Objective-C。