Understanding the Crossword Puzzle Algorithm

Asked

Viewed 35 times

1

I have this algorithm below, I wanted to know if I made a correct understanding, if it is very superficial and so have something else to add.

My understanding of the algorithm is being made explicit in the comments.

 static char[][] crossword;
    static string[] words;
    static void Main(String[] args)
    {
        crossword = new char[10][];
        for (int crossword_i = 0; crossword_i < 10; crossword_i++)
        {
            crossword[crossword_i] = Console.ReadLine().ToCharArray();
        }
        words = Console.ReadLine().Split(';');

        fill(0);
        Console.WriteLine(String.Join("\n", crossword.Select(x => new string(x))));
        Console.ReadKey();
    }

    static bool fill(int p)
    {
        if (p == words.Length)
        {
            return true;
        }

        for (int i = 0; i < 10; i++)
        {
            for (int j = 0; j < 10; j++)
            {
                //se o caracter lido for == "+" ele continua
                if (crossword[i][j] == '+')
                {
                    continue;
                }
                //vai procurar a correspondencia da palavra 
                else if (findVerdical(i, j, p) || findHorizontal(i, j, p))
                {
                    return true;
                }
            }
        }
        return false;

    }

    //corresponde ao preenchimento das posições da matriz em vertial
    static bool findVerdical(int x, int y, int p)
    {

        //verifica se a subtração de 10 com o valor y for menor do que o tamanho da palavra  
        //se a condição for verdadeira. vai retornar false para poder preencher de forma horizontal
        if (10 - y < words[p].Length)
        {
            return false;
        }

        //percorre todas as palavras
        for (int i = y; i < y + words[p].Length; i++)
        {
            //verifica a correspondncia da letra com o "-"
            if (crossword[x][i] != '-' && crossword[x][i] != words[p][i - y])
            {
                return false;
            }
        }
        //crio um temporario - será usado para fazer a troca do "-" pela letra correspondente
        var tmp = new char[10];
        for (int i = y; i < y + words[p].Length; i++)
        {
            tmp[i - y] = crossword[x][i];
            crossword[x][i] = words[p][i - y];
        }


        if (fill(p + 1))
        {
            return true;
        }
        //o temporário foi preenchido com sucesso, agora vou reescrever minha matriz com a letra correspondente
        for (int i = y; i < y + words[p].Length; i++)
        {
            crossword[x][i] = tmp[i - y];
        }
        return false;
    }

    //corresponde ao preenchimento das posições da matriz em horizontal
    static bool findHorizontal(int x, int y, int p)
    {

        //
        if (10 - x < words[p].Length)
        {
            return false;
        }
        for (int i = x; i < x + words[p].Length; i++)
        {
            if (crossword[i][y] != '-' && crossword[i][y] != words[p][i - x])
            {
                return false;
            }

        }
        var tmp = new char[10];
        for (int i = x; i < x + words[p].Length; i++)
        {
            tmp[i - x] = crossword[i][y];
            crossword[i][y] = words[p][i - x];
        }

        if (fill(p + 1))
        {
            return true;
        }
        for (int i = x; i < x + words[p].Length; i++)
        {
            crossword[i][y] = tmp[i - x];
        }
        return false;
    }
  • and comments on the method findHorizontal()?

  • does basically the same thing as the "findVertical" but for another direction, the idea is the same

  • And what is your doubt?

  • If I missed something important from that code

  • In my opinion, if you want to know if mastered an algorithm is to make your own implementation from scratch without copying any code.

No answers

Browser other questions tagged

You are not signed in. Login or sign up in order to post.