c

Question

所以我在 c 中做了一个回溯算法，我得到一个 txt 文件，每行都填满了单词，另一个 txt 文件只有一个方形纵横字谜的黑色方块的坐标。我知道我的实现非常简单，但我只想拥有准系统算法，以便稍后通过约束满足、前向检查等使其更快

但是我不知道如何让基本代码在没有分段错误和错误解决方案的情况下工作！蚂蚁的建议会很有帮助！

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#define MAX_WORDS 150000
#define MAX_DIMENSION 200
#define MAX_BLACK_SQUARES 250


int is_valid_word(char *word, int dimension, char crossword[MAX_DIMENSION][MAX_DIMENSION])
{
int i, j, k;
int word_length = strlen(word);

// check if word is too long
if (word_length > dimension)
{
    return 0;
}

// check if word overlaps existing letters
for (i = 0; i < dimension; i++)
{
    for (j = 0; j < dimension; j++)
    {
        if (crossword[i][j] != '_')
        {
            for (k = 0; k < word_length; k++)
            {
                if ((i + k < dimension && crossword[i + k][j] != '_' && crossword[i +   k][j] != word[k]) ||
                    (j + k < dimension && crossword[i][j + k] != '_' && crossword[i][j + k] != word[k]))
                {
                    return 0;
                }
            }
        }
    }
}

    return 1;
}

int solve_crossword(int dimension, char crossword[MAX_DIMENSION][MAX_DIMENSION], char           words[MAX_WORDS][30], int num_words, int word_index)
{
    int i, j, k;
    if (word_index >= num_words)
    {
    // all words have been placed, so return true
    return 1;
}
// try placing the current word horizontally
for (i = 0; i < dimension; i++)
{
    for (j = 0; j < dimension - strlen(words[word_index]); j++)
    {
        if (crossword[i][j] != '#')
        {
            // try placing the word here
            int is_valid = 1;
            for (k = 0; k < strlen(words[word_index]); k++)
            {
                if (crossword[i][j + k] != '_' && crossword[i][j + k] != words[word_index][k])
                {
                    is_valid = 0;
                    break;
                }
            }
            if (is_valid)
            {
                // place the word
                for (k = 0; k < strlen(words[word_index]); k++)
                {
                    crossword[i][j + k] = words[word_index][k];
                }
                // recursive call to place the next word
                if (solve_crossword(dimension, crossword, words, num_words, word_index + 1))
                {
                    return 1;
                }
                // backtrack by removing the word
                for (k = 0; k < strlen(words[word_index]); k++)
                {
                    crossword[i][j + k] = '_';
                }
            }
        }
    }
}

// try placing the current word vertically
for (i = 0; i < dimension - strlen(words[word_index]); i++)
{
    for (j = 0; j < dimension; j++)
    {
        if (crossword[i][j] != '#')
        {
            // try placing the word here
            int is_valid = 1;
            for (k = 0; k < strlen(words[word_index]); k++)
            {
                if (crossword[i + k][j] != '_' && crossword[i + k][j] != words[word_index][k])
                {
                    is_valid = 0;
                    break;
                }
            }
            if (is_valid)
            {
                // place the word
                for (k = 0; k < strlen(words[word_index]); k++)
                {
                    crossword[i + k][j] = words[word_index][k];
                }
                // recursive call to place the next word
                if (solve_crossword(dimension, crossword, words, num_words,word_index + 1))
                {
                    return 1;
                }
                // backtrack by removing the word
                for (k = 0; k < strlen(words[word_index]); k++)
                {
                    crossword[i + k][j] = '_';
                }
            }
        }
    }
}

// if we get here, we were unable to place the word in either direction
return 0;
}

int main()
{
    // open dictionary file
FILE *dict_file = fopen("dicts/EvenMoreWords.txt", "r");
if (dict_file == NULL)
{
    printf("Unable to open dict.txt\n");
    return 1;
}

// read dictionary into array
char words[MAX_WORDS][30];
int num_words = 0;
char buffer[30];
while (fgets(buffer, 30, dict_file) != NULL)
{
    int word_length = strlen(buffer);
    if (buffer[word_length - 1] == '\n')
    {
        buffer[word_length - 1] = '\0';
    }
    strcpy(words[num_words], buffer);
    num_words++;
}
fclose(dict_file);

// open crossword file
FILE *crossword_file = fopen("crosswords/c1.txt", "r");
if (crossword_file == NULL)
{
    printf("Unable to open crossword.txt\n");
    return 1;
}

// read dimensions and black squares
int dimension, i, j, width, height;
fscanf(crossword_file, "%d", &dimension);


// initialize crossword
char crossword[MAX_DIMENSION][MAX_DIMENSION];
while (fscanf(crossword_file, "%d %d", &width, &height) != EOF)
{
    crossword[width - 1][height - 1] = '#';
}
printf("\n\n\n");
for (i = 0; i < dimension; i++)
{
    for (j = 0; j < dimension; j++)
    {
        if (crossword[i][j] != '#')
        {
            crossword[i][j] = '_';
            printf("%c  ", crossword[i][j]);
        }
        else
        {
            printf("%c  ", crossword[i][j]);
        }
    }
    printf("\n");
}
printf("\n\n\n");

// solve crossword
if (solve_crossword(dimension, crossword, words, num_words, 0))
{
    // print solution
    for (i = 0; i < dimension; i++)
    {
        for (j = 0; j < dimension; j++)
        {
            printf("%c ", crossword[i][j]);
        }
        printf("\n");
    }
}
else
{
    printf("Unable to find a solution\n");
}

return 0;

}