Упорядочение трех буквенных слов в 2D-матрице таким образом, что каждая строка, столбец и диагональ образуют слово

Ответ 1

Мой подход заключается в том, чтобы сначала отфильтровать словарь, чтобы создать два новых словаря: первый содержит все однобуквенные префиксы слов (из которых, вероятно, 26), а второй содержит все двузначные префиксы слов (из которых меньше, чем 26 ^ 2, поскольку, например, слово не начинается с BB).

• Выберите слово из словаря, назовите его X. Это будет первая строка матрицы.

• Убедитесь, что X1, X2, X3 - все допустимые однобуквенные префиксы, используя тот удобный список, который вы сделали. Если да, переходите к шагу 3; в противном случае вернитесь к шагу 1.

• Выберите слово из словаря, назовите его Y. Это будет вторая строка матрицы.

• Убедитесь, что X1 Y1, X2 Y2, X3 Y3 - все допустимые двухбуквенные префиксы, используя тот удобный список, который вы сделали. Если да, переходите к шагу 5; в противном случае вернемся к шагу 3. Если это последнее слово в словаре, перейдите к шагу 1.

• Выберите слово из словаря, назовите его Z. Это будет третья строка матрицы.

• Убедитесь, что X1 Y1 Z1, X2 Y2 Z2, X3 Y3 Z3 - все слова в словаре. Если они, поздравляю, ты это сделал! В противном случае вернитесь к шагу 5. Если это последнее слово в словаре, перейдите к шагу 3.

Я закодировал это в Maple, и он работает достаточно хорошо. Я оставил его работать, чтобы найти все такие матрицы, и оказалось, что их достаточно, чтобы свернуть Maple из-за переполнения памяти.

Ответ 2

Ваш комментарий предполагает, что вы также ищете решение обратного отслеживания, которое будет неэффективным, но решает это. Псевдо-код:

solve(dictionary,matrix):
  if matrix is full:
       if validate(dictionary,matrix) == true:
            return true
        else:
            return false
  for each word in dictionary:
      dictionary -= word
      matrix.add(word)
      if solve(dictionary,matrix) == true:
          return true
      else:
          dictionary += word
           matrix.removeLast()
   return false //no solution for this matrix.

В приведенном выше псевдокоде matrix.add() добавляет данное слово в первую незанятую строку. matrix.remove() удаляет последнюю занятую строку, а validate() проверяет, является ли решение законным.

Активация: solve(dictionary,empty_matrix), если алгоритм дает true, есть решение, и входная матрица будет содержать его, иначе он будет давать false.

Вышеупомянутый псевдокод работает в экспоненциальном времени! это очень неэффективно. Однако, поскольку эта проблема напоминает (*) проблему кроссворда, которая NP-Complete, это может быть ваш лучший снимок.

(*) Исходная проблема кроссвордов не имеет диагонального условия, что эта проблема имеет и, конечно, более общая: nxm-матрица, а не только 3x3. Несмотря на то, что проблемы схожи, сокращение не появляется мне в голову, и я буду рад увидеть его, если он существует.

Ответ 3

• Вы найдете каждый уникальный набор из трех слов.
• Вы получаете все 6 возможных матриц для этих трех слов.
• Вы выполняете проверку словаря на 5 слов, которые могут быть созданы из этих матриц (3 столбца и 2 диагоналя).

Некоторые иллюстрации JavaScript.

//setup a test dictionary
var dict = [
 "MAD",
 "FAD",
 "CAT",
 "ADD",
 "DOG",
 "MOD",
 "FAM",
 "ADA",
 "DDD",
 "FDD"
];
for(var i=0; i<dict.length; i++)
 dict[dict[i]]=true;

// functions
function find(dict) {
for(var x=0; x<dict.length; x++) {
for(var y=x+1; y<dict.length; y++) {
for(var z=y+1; z<dict.length; z++) {
 var a=dict[x];
 var b=dict[y];
 var c=dict[z];
 if(valid(dict,a,b,c)) return [a,b,c];
 if(valid(dict,a,c,b)) return [a,c,b];
 if(valid(dict,b,a,c)) return [b,a,c];
 if(valid(dict,b,c,a)) return [b,c,a];
 if(valid(dict,c,a,b)) return [c,a,b];
 if(valid(dict,c,b,a)) return [c,b,a];
}
}
}
return null;
}
function valid(dict, row1, row2, row3) {
 var words = [];
 words.push(row1.charAt(0)+row2.charAt(0)+row3.charAt(0));
 words.push(row1.charAt(1)+row2.charAt(1)+row3.charAt(1));
 words.push(row1.charAt(2)+row2.charAt(2)+row3.charAt(2));
 words.push(row1.charAt(0)+row2.charAt(1)+row3.charAt(2));
 words.push(row3.charAt(0)+row2.charAt(1)+row1.charAt(2));
 for(var x=0; x<words.length; x++)
  if(dict[words[x]] == null) return false;
 return true;
}

//test
find(dict);

Ответ 4

Я не обязательно искал решение обратной связи. Мне просто поразило, что можно использовать обратное отслеживание, но решение с этим немного сложно. Однако мы можем использовать ветвь, связать и обрезать, чтобы прервать технику грубой силы.

Вместо поиска всех возможных комбинаций в матрице сначала мы выберем одну строку в качестве самой верхней строки. Используя первый символ, мы найдем подходящего соперника для 1-го столбца. Теперь, используя 2 и 3 символа строки столбца, мы найдем подходящие слова, которые могут быть установлены во второй и третьей строках.

Чтобы эффективно находить слова, начинающиеся с определенного символа, мы будем использовать сортировку radix, чтобы все слова, начинающиеся с определенного символа, были сохранены в том же списке. Это, когда мы выбрали вторую и третью строки матрицы, имеем полную матрицу. \

Мы проверим, действительна ли матрица, проверяя 2-й и 3-й столбцы, а диагонали образуют слова, которые попадают в словарь.

Как и когда мы находим, что матрица верна, мы можем остановиться. Это помогает сократить некоторые из возможных комбинаций. Однако я считаю, что это можно оптимизировать, рассмотрев еще одну строку или столбец, но тогда это будет немного сложнее. Я размещаю рабочий код ниже.

Пожалуйста, не обращайте внимание на назначение функций, так как я любительский кодер, я вообще не даю очень подходящих имен, а часть кода жестко закодирована для трех буквенных слов.

#include<iostream>
#include<string>
#include<algorithm>
#include<fstream>
#include<vector>
#include<list>
#include<set>

using namespace std;

// This will contain the list of the words read from the
// input file
list<string> words[26];

// This will contain the output matrix
string out[3];

// This function finds whether the string exits
// in the given dictionary, it searches based on the 
// first character of the string

bool findString(string in)
{
    list<string> strings = words[(int)(in[0]-'a')];
    list<string>:: iterator p;

    p = find(strings.begin(),strings.end(),in);
    if(p!=strings.end())
        return true;
}

// Since we have already chosen valid strings for all the rows
// and first column we just need to check the diagnol and the 
// 2 and 3rd column

bool checkMatrix()
{
    // Diagnol 1
    string d1;
    d1.push_back(out[0][0]);
    d1.push_back(out[1][1]);
    d1.push_back(out[2][2]);

    if(!(findString(d1)))
        return false;

    // Diagnol 2
    string d2;
    d2.push_back(out[0][0]);
    d2.push_back(out[1][1]);
    d2.push_back(out[2][2]);


    if(!(findString(d2)))
        return false;

    // Column 2
    string c2;
    c2.push_back(out[0][1]);
    c2.push_back(out[1][1]);
    c2.push_back(out[2][1]);

    if(!(findString(c2)))
        return false;

    // Column 3
    string c3;
    c3.push_back(out[0][2]);
    c3.push_back(out[1][2]);
    c3.push_back(out[2][2]);


    if(!(findString(c3)))
        return false;
    else
        return true;
    // If all match then return true
}

// It finds all the strings begining with a particular character

list<string> findAll(int i)
{
    // It will contain the possible strings
    list<string> possible;
    list<string>:: iterator it;

    it = words[i].begin();
    while(it!=words[i].end())
    {
        possible.push_back(*it);
        it++;
    }

    return possible;
}

// It is the function which is called on each string in the dictionary

bool findMatrix(string in)
{
    // contains the current set of strings
    set<string> current;

    // set the first row as the input string
    out[0]=in;
    current.insert(in);

    // find out the character for the column
    char first = out[0][0];

    // find possible strings for the column
    list<string> col1 = findAll((int)(first-'a'));
    list<string>::iterator it;

    for(it = col1.begin();it!=col1.end();it++)
    {
        // If this string is not in the current set
        if(current.find(*it) == current.end())
        {
            // Insert the string in the set of current strings
            current.insert(*it);

            // The characters for second and third rows
            char second = (*it)[1];
            char third = (*it)[2];

            // find the possible row contenders using the column string
            list<string> secondRow = findAll((int)(second-'a'));
            list<string> thirdRow = findAll((int)(third-'a'));

            // Iterators
            list<string>::iterator it1;
            list<string>::iterator it2;


            for(it1= secondRow.begin();it1!=secondRow.end();it1++)
            {
                // If this string is not in the current set
                if(current.find(*it1) == current.end())
                {

                    // Use it as the string for row 2 and insert in the current set
                    current.insert(*it1);

                    for(it2 = thirdRow.begin();it2!=thirdRow.end();it2++)
                    {
                        // If this string is not in the current set
                        if(current.find(*it2) == current.end())
                        {   

                            // Insert it in the current set and use it as Row 3
                            current.insert(*it2);

                            out[1]=*it1;
                            out[2]=*it2;

                            // Check ifthe matrix is a valid matrix
                            bool result = checkMatrix();

                            // if yes the return true
                            if(result == true)
                                return result;

                            // If not then remove the row 3 string from current set
                            current.erase(*it2);
                        }
                    }
                    // Remove the row 2 string from current set
                    current.erase(*it1);
                }
            }
            // Remove the row 1 string from current set
            current.erase(*it);
        }
    }
    // If we come out of these 3 loops then it means there was no 
    // possible match for this string
    return false;           
}

int main()
{
    const char* file = "input.txt";
    ifstream inFile(file);

    string word;

    // Read the words and store them in array of lists
    // Basically radix sort them based on their first character
    // so all the words with 'a' appear in the same list 
    // i.e. words[0]

    if(inFile.is_open())
    {
        while(inFile.good())
        {
            inFile >> word;
            if(word[0] >= 'a' && word[0] <= 'z')
            {
                int index1 = word[0]-'a';
                words[index1].push_back(word);
            }
        }
    }
    else
        cout<<"The file could not be opened"<<endl;


    // Call the findMatrix function for each string in the list and
    // stop when a true value is returned

    int i;
    for(i=0;i < 26;i++)
    {
        it = words[i].begin();
        while(it!=words[i].end())
        {
            if(findMatrix(*it))
            {
                // Output the matrix
                for(int j=0;j<3;j++)
                    cout<<out[j]<<endl;

                // break out of both the loops
                i=27;
                break;
            }
            it++;
        }
    }

    // If i ==26 then the loop ran the whole time and no break was
    // called which means no match was found

    if(i==26)
        cout<<"Matrix does not exist"<<endl;

    system("pause");
    return 0;
}

Я проверил код на небольшом наборе строк, и он отлично работал.