아마도 십자말 생성에 this algorithm을 사용할 수 있습니다. 나는이 문제에 대해 괜찮을 것이라고 생각한다.
이 알고리즘에 따르면, 문제는 강력한 보드 N에 있습니다. 크로스 워드 퍼즐이 왼쪽 -> 오른쪽으로 자랄 수 있기 때문에 다음 단어가 마지막 단어를 음수 좌표와 교차시킬 수 있음> & 상단 -> 하단 => 예외를 잡아라. 각 단어 배치 후에 보드 격자를 다시 계산하고 각 재 계산 후에 보드 크기를 수정하십시오. 그리고 NxN 그리드에주의하십시오 : words-list에서 십자말을 생성 할 가능성은 낮습니다 => IndexOutOfRangeException을 얻을 수 있습니다.
또한 은이어야합니다. 다음 단어가 이미 사용 된 단어와 제대로 교차하지 않으면 다음 단어>, 다음 단어>, 다음 단어>, 다음 단어 등이 교차 할 수 있습니다. 교차가없는 단어는 StackOverflow 예외 또는 무한 루프를 유발할 수 있습니다.
내 링크의 알고리즘은 단어 목록을 정렬하는 첫 단계에서 제공됩니다. 하지만 당신의 문제를 직접 해결하려고 노력했습니다. 코드는 아래와 같습니다. 내 알고리즘은 링크에서 예제로 정렬을 사용하지 않지만 1 대신 2 회 재귀를 사용합니다. 좌표가 솔루션 내에서 다른 의미를 가질 수 있기 때문에 그리드 재 계산을 포함하지 않았습니다.
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
}
}
OK 내가 다른 방법으로 실수를 한 것을 발견하지만, 현재 코드 -> 위, 내가 조밀 한 크로스 워드 퍼즐 큰 문제가 어떤 도움 OK인가? –