也许，您可以使用此算法生成填字游戏。我认为这个问题可以。
根据这个算法，我认为问题出在强板 N 中。你的下一个单词可以与最后一个单词相交成负坐标，因为填字游戏不仅可以增长 left->right & top->bottom=>你会得到例外。尝试在每个单词放置后重新计算您的棋盘网格，并在每次重新计算后纠正棋盘大小。并且要小心 NxN 网格：从单词列表生成填字游戏的可能性很低=>您可以获得 IndexOutOfRangeException。
此外，您必须检查 place 事件：如果下一个单词没有与任何已使用的单词正确相交，它可以与 next->next word、next->next->next 等相交。在您的解决方案中，没有交集的单词可能导致 StackOverflow 异常或无限循环。
我的链接中的算法首先提供了排序单词列表。但我试图自己解决你的问题。代码如下所示。我的算法在链接中没有使用排序作为示例，但它使用 2 个递归而不是 1 个。此外，我没有包括网格重新计算，因为坐标在我的和您的解决方案中可能具有不同的含义。
public class Crossword
{
List<string> words = new List<string>();//for words
List<string> nomatchWords = new List<string>();//for words those have no match with others
List<string> usedWords = new List<string>();//for words we already used
char[,] renderResult;//your result as grid of words. You can draw it in WindowsFormsApp, WPF, etc.
//a grid.
//3 values of int[]:
//[0]==horizontal/vertical word(1/0)
//[1]==beginning (number of the first letter for horizontal axis)
//[2]==beginning(number of the first letter for vertical axis)
List<int[]> Grid = new List<int[]>();
int HorizontalSize=17;//size of renderResult. I left it as a default for this example. Its calculation depends on your algoritm for rendering
int VerticalSize=17;
public Crossword()
{
FillWords(this.words);//fill the list of words
}
//just for example; it can be reading from file etc.
void FillWords(List<string> words)
{
words.Add("alphabet");
words.Add("gramin");//may intersect the first at 'a'
words.Add("asturias");//may intersect the first or second at 'a'
words.Add("fitness");//may intersect all words
words.Add("shit");//? too difficult to calculate where it can place in the crossword. Lets do it by the algorithm
words.Add("programmer");//? you can watch it in debug how my recursion works
}
/// <summary>
/// the main method. Here we render all words in your words-list.
/// </summary>
/// <param name="crossword"></param>
public void Generate(Crossword crossword, DataGridView dgvr)
{
List<int[]> letterPosition=new List<int[]>();//can be empty because words may unmatch
//place EACH word in the crossword
while (words.Count != 0)//if words.Count=0, all words are placed (but there's also can be words with no match)
{
string currentWord = words[0];
Grid.Add(new int[3] { 1, 0, 0 });//new grid position for this word
if (usedWords.Count == 0)//this is the first word
{
usedWords.Add(currentWord);
crossword.Place(currentWord, Grid[0], letterPosition, 0);//place it as a new word
words.RemoveAt(0);
}
else//not the first word=> place the new word in position relative to any of used words
SolveCrossword(currentWord, letterPosition, 0);
PrintCrossword(????);//just for my app, do your logic here
}
//the step with nomatch words. Words that can be intersected with the others words properly will appear in crossword solution. Completely nomatch will not appear.
foreach(string currentWord in nomatchWords)
SolveCrossword(currentWord,letterPosition,0);//process NomatchWords like words
//HOW TO CHECK: try to place as word-list any list of words
}
/// <summary>
/// solution of crossword
/// </summary>
/// <param name="currentWord">the word that we try to place</param>
/// <param name="letterPosition">positions of letter where current word can intersect with the other</param>
/// <param name="intersectWord">the number of intersect word</param>
void SolveCrossword(string currentWord, List<int[]>letterPosition, int intersectWord)
{
if (usedWords.Count - intersectWord > 0)//we must check the intersection with all this words=>SolveCrossword checks the intersection from the last used word to first
//the other order will cause generation from the last words=>crossword will look like a tree instead of sharp
{
try
{
if (MatchWords(usedWords[intersectWord], currentWord, letterPosition))//no matches for its word with last word
{//usedWords.Count - 1 -
int positionCounter = 0;
if (this.Place(currentWord, Grid[intersectWord], letterPosition, positionCounter) == false)//no places for this word related to last placed word=> it's temporarily unmatched
{
letterPosition.Clear();
SolveCrossword(currentWord, letterPosition, ++positionCounter);//we're here because there's no valid intersections between current words=> lets seek the others
}
if (words.Count != 0)
words.RemoveAt(0);//backtrack will end when we'll find the correct position of word
return;
}
else
{
letterPosition.Clear();
SolveCrossword(currentWord, letterPosition, intersectWord + 1);
}
//if we're here, the intersection was not found=>it is nomatch word. It can be correct or completely nomatch word but we'll figure it out at last step
nomatchWords.Add(currentWord);
words.RemoveAt(0);
}
catch//we've got an exception if unchecked positions number->0
{
letterPosition.Clear();
SolveCrossword(currentWord, letterPosition, intersectWord + 1);
}
}
}
//how to find matches. Doesn't matter, you can use your own method to solve this
static bool MatchWords(string newword, string matchedword, List<int[]> letterPosition)
{
for (int i = 0; i < newword.Length; i++)
for (int j = 0; j < matchedword.Length; j++)
if (newword[i] == matchedword[j])
letterPosition.Add(new int[2]{i,j});//we need ALL matches, not only FIRST!<= it may cause problems with size of crossword and bug count of unmatched words
if (letterPosition.Count != 0)
return true;
else
return false;
}
/// <summary>
/// This is how to place words into crossword grid
/// </summary>
/// <param name="newword">our word</param>
/// <param name="letterPosition">Letter Positions list</param>
/// <param name="el">the number of element of LetterPositions. If current intersection is not valid, we move to next</param>
/// <returns>true if sucsess</returns>
bool Place(string newword, int[] intersectedWordGrid, List<int[]> letterPosition, int el)//
{
//placing newword related to lastword (setting up the last Grid element)
//try
//{
if (Grid.Count > 1)
{
if (intersectedWordGrid[0] == 1)//last word is horizontal=>we need vertical
{
Grid[Grid.Count - 1][0] = 0;
Grid[Grid.Count - 1][1] = intersectedWordGrid[1] - letterPosition[el][1];
Grid[Grid.Count - 1][2] = intersectedWordGrid[2] + letterPosition[el][0];
}
else//vertical=>horizontal
{
Grid[Grid.Count - 1][0] = 1;
Grid[Grid.Count - 1][1] = intersectedWordGrid[1] + letterPosition[el][0];
Grid[Grid.Count - 1][2] = intersectedWordGrid[2] - letterPosition[el][1];
}
usedWords.Add(newword);
}
//TODO: recalculate rendering grid for crossword (if you use another mechanic you're welcome)
//I use default boundaries of size 17x17
//try to render: if crossword with these Grid positions of words is valid=>good
if (Render())//renderResult now contains the current solution of crossword
{
letterPosition.Clear();
return true;
}
else//crossword is not valid with this grid
Place(newword, intersectedWordGrid, letterPosition, ++el);
return true;
}
//rendering your crossword
bool Render()
{
if (renderResult == null)
renderResult = new char[HorizontalSize, VerticalSize];
int[] renderword = Grid[Grid.Count - 1];//for each Grid coordinates
{
if (usedWords.Count != 0)
{
string currentword = usedWords[usedWords.Count-1];
//usedWords.RemoveAt(0);
int i=0, j = 0;//need i & j because changing grid coordinates may cause mistakes in other words positions
try
{
//rresultTempCopy = renderRes;
if (CheckWordsInSolution(currentword, renderResult, renderword))
for (int k = 0; k < currentword.Length; k++)//word were checked and it's valid=>write it to board
{
renderResult[HorizontalSize / 2 + renderword[1] + i, VerticalSize / 2 + renderword[2] + j] = currentword[k];
if (renderword[0] == 1)
j++;
else
i++;
}
else
{
usedWords.RemoveAt(usedWords.Count - 1);
return false;
}
}
catch
{
usedWords.RemoveAt(usedWords.Count - 1);
return false;
}
}
}
//we're here=>no mistakes, this is a valid result
return true;//sucsess
}
bool CheckWordsInSolution(string currentword, char[,] solutionTable, int[] wordCoordinates)
{
int i = 0, j = 0;
for (int k = 0; k < currentword.Length; k++)
//validation
if ((renderResult[HorizontalSize / 2 + wordCoordinates[1] + i, VerticalSize / 2 + wordCoordinates[2] + j] == '\0' ||//must be empty place for each letter
renderResult[HorizontalSize / 2 + wordCoordinates[1] + i, VerticalSize / 2 + wordCoordinates[2] + j] == currentword[k])//or the same letter
//we can use other rules, it depends on your type of crossword
//&& ((i == 0 && renderResult[HorizontalSize / 2 + wordCoordinates[1] + i - 1, VerticalSize / 2 + wordCoordinates[2] + j] == '\0') == false ||//before the beginning of word must be empty place
// (j == 0 && renderResult[HorizontalSize / 2 + wordCoordinates[1] + i, VerticalSize / 2 + wordCoordinates[2] + j - 1] == '\0') == false)
//&& ((i == k && renderResult[HorizontalSize / 2 + wordCoordinates[1] + i + 1, VerticalSize / 2 + wordCoordinates[2] + j] == '\0') == false ||//after the end of word must be empty place
// (j == k && renderResult[HorizontalSize / 2 + wordCoordinates[1] + i, VerticalSize / 2 + wordCoordinates[2] + j + 1] == '\0') == false)
)
{
if (wordCoordinates[0] == 1)
j++;
else
i++;
}
else
return false;
return true;
}
void PrintCrossword(???)
{
//draw your crossword here
}
}