Я работаю над кроссворд-проблемой, но я не знаю, как разработать алгоритм.
Например:
Таким образом, задача алгоритма состоит в том, чтобы сделать правильные слова, которые хранятся в словаре.
app → lapp → leapp → lecapp → .... → lappe → eappc → ... → appl → apple (правильный ответ)
Какое наилучшее решение для этого алгоритма?
Возможно, вас заинтересует исследовательская работа в Google Google "Всемирная самая быстрорастущая программа скриншотов" от Appel и Jacobson (1988). Алгоритмы выделены в псевдокоде, поэтому требуется небольшая работа, чтобы сформировать это в пригодную для использования форму и склеить все вместе; однако программа, составленная авторами, отлично работает.
Сохраните словарь как дерево, например:
*
|
+----+----+
| |
A* B
| |
+--+--+ E*
| | |
P S +-+-+
| | | |
P* K* A E*
| |
+-+-+ +-+-+
| | | |
E L D* N*
| |
A E*
|
L*
Спасибо paxdiablo за то, что мое дерево стало более читаемым.
В этом дереве есть слова a, app, апелляция, apple, ask, bead, bean, be и пчела. Узлы, отмеченные звездочкой, указывают: "Если бы я остановился здесь, это было бы допустимым словом", например, "e" ниже "b" для "be".
Когда вы найдете письмо, которое не знаете, используйте подстановочный знак (т.е. выберите всех детей и запишите все пути).
Вы сказали кроссворд, но тогда ваши "письма... для слов", казалось, указывали на "Скраббл". Это тоже сработает. Не самый быстрый, но достаточно быстрый.
Спасибо Андреасу за то, что он напомнил нам, что это называется trie.
Если вы хотите сказать, что "вторая буква - это P", вы должны начинать с корня node и принимать каждую ветвь (которая будет представлять собой каждую букву в алфавите, считая ее правильным словарем), а затем "P" и затем продолжайте оттуда.
Я на самом деле написал кроссворд раньше (загадочный, но теория позади конструкции идентична).
У меня была база данных слов и их подсказок, которые можно было отсортировать по используемым временам (так что я бы не стал получать дубликаты кроссвордов при последующих прогонах).
Первое, что вам нужно сделать, - это разработать свои шаблоны (черные, где вы не можете помещать буквы и белые, где можете). Попытка вставить слова в сетку при создании рисунка "на лету" очень трудоемка и подвержена ошибкам. Если вы посмотрите на большинство кроссвордов, они, как правило, следуют определенным правилам, чтобы облегчить это. Такие вещи, как быть симметричными вокруг одной из диагоналей и запрещать квадрат из четырех белых клеток (чтобы облегчить задачу выбора подходящих слов).
После того, как у вас есть шаблон, вы начинаете находить слова в нем. Таким образом, вы бы знали, что "приложение" стало началом слова и сможет ограничить ваши поисковые запросы теми, кто начинается с "приложения", а не с каждым словом, в котором есть "приложение". Аналогично для слов, где вы знаете буквы в любых позициях. Гораздо проще находить слова с буквами в известных положениях, чем оценивать эти буквы в любой начальной позиции в пределах слова.
Моя работа была написана в оболочке script (верьте или нет) и используя словарь, который пришел из Linux в качестве инструмента поиска слов. Если вы знаете, что у вас есть 5-буквенное слово, начинающееся с "приложения", его довольно легко использовать:
grep '^app..$' words.txt
чтобы получить список всех допустимых возможностей.
И, поскольку каждое слово было найдено, оно было скопировано в файл clues.txt, содержащий как слово, так и несколько возможных подсказок. Фактическим форматом было использование {count, word, clue}, где одно и то же слово может существовать на нескольких строках с другим ключом - это разрешало прокручивание grep через sort, чтобы менее используемые слова/подсказки перемещались в начало ( всякий раз, когда использовалось слово/ключ, его счет увеличивался, что уменьшало вероятность использования в следующий раз).
После того, как этот файл был приличным размером, программа сначала использовала его для поиска слов, и только если он не был найден, он вернется к файлу слов (без ключа), где потребуется ручное вмешательство.
На самом деле это оказалось неплохо при выполнении задания. Это было не ослепительно быстро, но мне не нужно было генерировать его каждые три секунды - это было для рассылки новостей сообщества раз в неделю.
Теперь, когда вы изменили вопрос на вариант Scrabble, это намного сложнее.
Вы должны учесть буквы, которые у вас есть, буквы на доске и тот факт, что вам нужно еще много мест, которые вы должны оценить. Это делает метод грубой силы намного сложнее.
То, что я сделал бы в качестве начального разреза, - это выбрать возможности (начальную позицию и направление на доске), выбранные случайным образом, а затем использовать тот же алгоритм, что и для варианта кроссворда, чтобы найти все слова, которые могут там поместиться. Затем, если у вас есть буквы, чтобы удовлетворить это слово, сохраните его (вместе со своим счетом) в списке.
Имейте в виду, что вам нужно следить за тем, чтобы вмешиваться в другие слова на доске.
Я продолжал бы изучать возможности, пока один из:
Последнее, что важно - если вы играете новичком, вы не хотите исчерпывающе изучать миллионы возможностей.
Затем выберите лучший вариант из своего списка (или, может быть, не самый лучший, если вы играете на уровне начинающего) - все зависит от того, насколько вы хотите, чтобы компьютер был).
Стивен А. Гордон написал интересную статью о том, как искать возможные шаги Scrabble (tm я guess) (см. Gordon paper на GADDAG), Хотя существует большой разрыв между поиском ходов и победой в Scrabble - как упоминается в документе - это не относится к исходному вопросу.
В случае, если вам будет очень полезно просто перейти к чтению некоторого кода, есть хороший игрок с открытым исходным кодом, Quackle.
В большинстве работ Scrabble говорится о поиске всей доски для лучшего слова для игры. Но для решения вашей проблемы, как указано, существует довольно простой алгоритм.
Сначала вы знаете, что слово, которое вы хотите, содержит "приложение", и вы знаете, что самое большое слово, которое вы можете сделать, это семь букв (3 буквы уже на доске и 4 в вашем лотке). Итак, выполните поиск в базе данных с помощью инструкции sql, например:
Выберите слово из словаря, где слово LIKE '% app%' и len (word) <= 7
Затем поместите все семь букв в массив {l, e, c, r, a, p, p}
Прочитайте каждое слово из базы данных по одному за раз. Затем посмотрите на каждый символ словаря и посмотрите, существует ли он в массиве. Если первая буква слова слова находится в массиве, удалите этот элемент в массиве и перейдите к следующей букве словаря.
Если в массиве не найдено слова слова словаря, тогда слово не подходит, поэтому переходите к следующему слову.
Если вы просмотрели все буквы в словаре, и все они были найдены в массиве, тогда слово квалифицируется, и поэтому вы пишете его в списке.
Обратите внимание, причина, по которой вы помещаете свои плитки в массив, заключается в том, что, как только вы сопоставляете букву словаря с фрагментом в вашем массиве, вам нужно удалить эту письмо из дальнейшего рассмотрения, удалив этот элемент в массив.
Так, например, база данных словарей возвращает слово "апелляция". Первые четыре буквы находятся в вашем массиве, и эти элементы удаляются, оставляя в массиве только {l, c, r}. Когда вы ищете пятую букву "а", вы ее не найдете, поэтому слово дисквалифицировано.
Слово "яблоко" будет квалифицироваться, оставив {c, r} в вашем массиве.
Очень легко закодировать это на любом языке. Однако это не самый быстрый способ сделать это. Я ищу более быстрый способ сам!
Если вы пытаетесь создать индекс слов, чтобы вы могли попытаться "решить" (или создать) кроссворды, я думаю, вы начнете со словаря слов, индексированных по длине. Затем вы создадите еще один словарь словарей словарей... первый индекс - общей длиной слова, а второй - по длине, затем по буквенной позиции и, наконец, буквой (шесть буквенных слов со второй буквой "i" например).
После того, как вы построили этот индекс, вы можете выразить каждый шаг в попытке установить или решить головоломку с точки зрения заданных операций, выполняемых над ними. (Например, 8-буквенное слово, начинающееся с "w" и заканчивающееся "k", будет пересечением всех 8 буквенных слов, начинающихся с "w", и всех тех, которые заканчиваются на "k" --- что, неудивительно, будет включать "домашнюю работу" "). Разумеется, построение индексированной структуры данных, которую я описал, позволит значительно более эффективный поиск возможных совпадений, будет выполняться линейным сканированием только глобального списка слов или даже линейного сканирования разделенных длиной списков).
Как только у вас будет эта базовая структура данных, остальная часть программы, по-видимому, будет генерации и обхода дерева (с возвратом, конечно). Создайте программу, которая генерирует каждую возможность (используя описанную структуру данных), и всякий раз, когда она "застревает", она возвращается назад, пока не найдет новые возможности.
Как подразумевается paxdiablo, вам придется включить большой пул "слов" для генератора, чтобы иметь разумные шансы на создание завершенного "решения". Любой, кто испытывает кроссворды, понимает, что они позволяют сеттерам брать довольно много свобод (например, частое использование точек компаса, архаичных терминов и поэтических контрактов), чтобы получить себя от горба как бы.
Я лично не написал генератор кроссвордов. Я написал криптограммные решатели, которые использовали аналогичную, но гораздо более простую структуру индексирования. (Чтобы найти каждое слово, которое zyzxw может быть в криптограмме, вы "абстрагируете" его в шаблон: abacd. Ваш словарь содержит каждое слово, индексированное его абстракцией, и вы можете легко найти, что "каждый" соответствует "zyzxw" ). В этом случае линейный поиск по спискам, начинающимся с каждой абстракции, достаточно быстр, даже если вы соглашаетесь узнать, что "uvz" с "zyzxw" действительно может быть "тем"... например). Я также написал простую игру "Jotto", которая не имеет никакого преимущества при индексировании: линейное сканирование через несколько тысяч 5 или 6 буквенных слов на каждом шаге устранения, который занимает гораздо меньше секунды на моем старом 6 Mhz XT в предыстории современных компьютерных вычислений).
Ищите диссертацию доктора философии "На пути к совершенной игре из шрамов" Брайана Шеппарда (автор Maven). Это информативное и очень интересное. Но и очень долго.
Если я правильно понял вопрос (вы начинаете w hint letters, подстроку слова и пытаетесь изменить порядок букв, чтобы получить правильное слово), вот еще одно решение:
Вы можете начать, возвращаясь назад. У вас уже есть слова в словаре, и вам нужно показать часть слова (подстроку) и список букв из слова, чтобы люди могли их упорядочить. Принимая во внимание все это, вы начинаете со слова из словаря и создаете график слов из 1 расстояния редактирования.
Пример
Начните с яблока и продолжайте удалять письмо. Вот небольшой график (для которого я не рисовал все ребра, чтобы уменьшить беспорядок):
яблоко → апелляция → обезьяна → ...
 \nbsp                              \
   \_- > appl → app → ...
Когда вы удаляете письмо, вы помещаете его в список подсказок.
подсказки: l, p
подсказки: l, e
Поскольку игрок использует буквы из списка для формирования исходного слова, вы принимаете только правильные записи, которые являются узлами, которые приводят к предыдущему родительскому. Вы просто проходите график назад, чтобы найти исходное слово.
Пример
Если слово - это приложение и подсказки: l, p
Если пользователь дает вам l: appl, вы переходите в приложение node, которое заявл.
Если пользователь дает вам e: appe, вы переходите в приложение node, которое Примените в этом случае.
Любая другая буква, которую вводит пользователь, вы запрещаете, оставаясь при текущем node.
То, что вы ищете, - это возможность для вашего анаграмма-решателя найти "подстановочные" письма, чтобы увидеть, что над словами он может делать с помощью дополнительных букв. У меня есть анаграммный решатель, который я написал, который делает это точно. Одна важная вещь, которую я обнаружил, чтобы сделать это, а также скорость решателя - предопределить, сколько букв и баллов каждого слова в вашей таблице слов.
Для экземпляра Таблица должна быть структурирована следующим образом
word | a | b | c | d | e | f | g | h | i | j | k | l | m | n | o | p | q | r | s | t | u | v | w | x | y | z | score
-------------------------------------------------------------------------------------------------------------
test | 0 | 0 | 0 | 0 | 1 | 0 | 0 | h | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 2 | 0 | 0 | 0 | 0 | 0 | 0 | 4
Как вы можете видеть, есть отдельный столбец для слова, буквы и того, сколько из этого письма они содержат, и оценка этого слова. Я создал это раньше времени с помощью отдельного script, который просто запускался для каждого слова и заполнял его для меня, пока это не было сделано.
Вот script, который я написал, чтобы рассчитать, сколько букв было в каждом слове, а также счет и обновлена каждая запись. Вы должны начать с таблицы, в которой есть только слова, прежде чем вы сможете запустить этот script. После того, как вы запустите его, вы закончите и не должны запускать его снова, если вы не добавите новые слова.
<?
include('/includes/connect.php');
$sql = "SELECT * FROM SOWPODS WHERE word LIKE 'z%' ORDER BY word ASC";
$result = mysql_query($sql);
while($row = mysql_fetch_array($result)) {
$string = $row['word'];
$rowwordid = $row['ID'];
echo $thisword = strtoupper($row['word']);
echo " - ";
for ($ii = 0; $ii < strlen($string); ++$ii) {
$thisletter = strtolower($string{$ii});
if ($thisletter == 'a') {
$a = $a+1;
} elseif ($thisletter == 'b') {
$b = $b+1;
} elseif ($thisletter == 'c') {
$c = $c+1;
} elseif ($thisletter == 'd') {
$d = $d+1;
} elseif ($thisletter == 'e') {
$e = $e+1;
} elseif ($thisletter == 'f') {
$f = $f+1;
} elseif ($thisletter == 'g') {
$g = $g+1;
} elseif ($thisletter == 'h') {
$h = $h+1;
} elseif ($thisletter == 'i') {
$i = $i+1;
} elseif ($thisletter == 'j') {
$j = $j+1;
} elseif ($thisletter == 'k') {
$k = $k+1;
} elseif ($thisletter == 'l') {
$l = $l+1;
} elseif ($thisletter == 'm') {
$m = $m+1;
} elseif ($thisletter == 'n') {
$n = $n+1;
} elseif ($thisletter == 'o') {
$o = $o+1;
} elseif ($thisletter == 'p') {
$p = $p+1;
} elseif ($thisletter == 'q') {
$q = $q+1;
} elseif ($thisletter == 'r') {
$r = $r+1;
} elseif ($thisletter == 's') {
$s = $s+1;
} elseif ($thisletter == 't') {
$t = $t+1;
} elseif ($thisletter == 'u') {
$u = $u+1;
} elseif ($thisletter == 'v') {
$v = $v+1;
} elseif ($thisletter == 'w') {
$w = $w+1;
} elseif ($thisletter == 'x') {
$x = $x+1;
} elseif ($thisletter == 'y') {
$y = $y+1;
} elseif ($thisletter == 'z') {
$z = $z+1;
}
}
$scorea = $a*1;
$scoreb = $b*4;
$scorec = $c*4;
$scored = $d*2;
$scoree = $e*1;
$scoref = $f*4;
$scoreg = $g*3;
$scoreh = $h*3;
$scorei = $i*1;
$scorej = $j*10;
$scorek = $k*5;
$scorel = $l*2;
$scorem = $m*4;
$scoren = $n*2;
$scoreo = $o*1;
$scorep = $p*4;
$scoreq = $q*10;
$scorer = $r*1;
$scores = $s*1;
$scoret = $t*1;
$scoreu = $u*2;
$scorev = $v*5;
$scorew = $w*4;
$scorex = $x*8;
$scorey = $y*3;
$scorez = $z*10;
$totalscore = $scorea + $scoreb + $scorec + $scored + $scoree + $scoref + $scoreg + $scoreh + $scorei + $scorej + $scorek + $scorel + $scorem + $scoren + $scoreo + $scorep + $scoreq + $scorer + $scores + $scoret + $scoreu + $scorev + $scorew + $scorex + $scorey + $scorez;
$SQL_update_count = "UPDATE TWL06 SET a = '$a', b = '$b', c = '$c', d = '$d', e = '$e', f = '$f', g = '$g', h = '$h', i = '$i', j = '$j', k = '$k', l = '$l', m = '$m', n= '$n', o = '$o', p = '$p', q = '$q', r = '$r', s = '$s', t = '$t', u = '$u', v = '$v', w = '$w', x = '$x', y = '$y', z = '$z', score = '$totalscore' WHERE ID = '$rowwordid'";
echo "<br>";
$result_update_count = mysql_query($SQL_update_count);
$a = 0;
$b = 0;
$c = 0;
$d = 0;
$e = 0;
$f = 0;
$g = 0;
$h = 0;
$i = 0;
$j = 0;
$k = 0;
$l = 0;
$m = 0;
$n = 0;
$o = 0;
$p = 0;
$q = 0;
$r = 0;
$s = 0;
$t = 0;
$u = 0;
$v = 0;
$w = 0;
$x = 0;
$y = 0;
$z = 0;
}
?>
После этого все, что вам нужно сделать, это сделать script, который подсчитывает буквы в столбцах и сопоставляет их с буквами, которые вы ему даете. Сначала вам придется взорвать письма и узнать, сколько из них у вас есть. Затем запустите оператор sql, который найдет эти количества букв или меньше.