логика для кроссворда

Question

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

0 1 0 0 0 0 0 0 1 0 0
0 1 0 1 1 1 1 1 1 1 1
0 1 0 1 0 0 1 0 1 0 1
0 S 1 1 0 1 1 1 1 0 1
0 1 0 0 1 0 1 0 1 0 0
1 1 1 1 1 1 1 S 1 1 0
0 0 0 0 1 0 1 0 0 0 0
0 0 0 0 1 0 0 0 0 0 0

, рассматривая каждый столбец / строку как один из возможных ответов.Есть ли способ проанализировать этот файл и пометить ответы, не используя gazilion, если для каждого поля?Остальная логика выглядит следующим образом:
- на основе проанализированного файла создается кроссворд.
- пользователь выбирает ответы из списков возможностей
- пользователь нажимает на первый блок ответа и, если длина ибуквы выбранного ответа и совпадения ответов - поля обновляются

Я полагаю, игровая доска должна храниться в 2d массиве, и в каждом ответе должны быть индексы полей?

Answer 1

Конструкция кроссворда в основном NP-Complete (т.е. nxn доска из 1 с и 0 с и заданный набор, из которого можно выбрать ответы).Посмотрите на: http://en.wikipedia.org/wiki/List_of_NP-complete_problems, который просто упоминает об этом.В классической книге Гэри и Джонсона также есть упоминание об этом, в котором говорится, что Точное покрытие на 3 комплекта может быть уменьшено до этого.

Таким образом, вам, вероятно, придется использовать некоторую обратную трассировку / эвристику для заполнения сетки.

Возможно, какой-то отчет по проекту двух студентов из колледжа Дартмута поможет вам: Генератор кроссвордов .Он содержит некоторую эвристику, которую вы могли бы использовать.

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