也許，你可以使用this algorithm來生成字謎。我認爲這個問題可以。
根據這個算法，我認爲問題出現在強大的板子N上。你的下一個單詞可以與最後一個單詞相交成負向座標，因爲填字遊戲不僅可以長到左右> & top-> bottom =>得到例外。嘗試重新計算每個單詞放置後的電路板網格，並在每次重新計算後更正電路板尺寸。並且要小心NxN網格：從words-list生成填字的可能性很低=>您可以獲得IndexOutOfRangeException。
而且，你必須檢查的地方事件：如果下一個字不相交的任何已使用的話得當，它可以相交下一步 - >下一個單詞，下一步 - >下一步 - >未來等。在您的解決方案，沒有交集的單詞可能會導致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
}
}
好吧，我發現我在其他方法中有錯誤，但是使用當前代碼 - >以上是好的我對密集填字遊戲有任何幫助嗎？ –