Думаю многим хабровчанам знакома книга «Этюды для программистов» Чарльза Уэзерелла. Если нет, то здесь можно прочитать интервью с автором и небольшой обзор книги. Мне самому совсем недавно попала данная вещь в руки, и было решено обязательно реализовать одну из задачек.
Итак предлагаю разобрать с вами один из этюдов. Писать будем на Java, поработаем с графикой и GUI + разберем алгоритм перебора с возвратом для нахождения нашего решения. Маловероятно, что статья заинтересует профи, но вот новичкам, а особенно тем, кто только изучает Java, статья может оказаться полезной.
Всем заинтересовавшимся – добро пожаловать!
Постановка задачи
Тут приведу отрывок из «Этюдов», который введет читателя в курс дела.
Многие считают кроссворды слишком трудной головоломкой, потому что отгадать слово им не под силу. Но вписывать буквы в клетки нравится. Для подобных людей существует более простая головоломка — крисс-кросс. Каждый крисс-кросс состоит из списка слов, разбитых для удобства на группы в соответствии с длиной и упорядоченных по алфавиту внутри каждой группы, а также из схемы, в которую нужно вписать слова. Схема подчиняется тому же правилу, что и в кроссворде, — в местах пересечения слова имеют общую букву, однако номера отсутствуют, поскольку слова известны заранее, требуется лишь вписать их в нужные места.
Пример такой головоломки вы можете видеть на рисунке
Мне, честно, не особо нравится вписывать буквы в клетки, поэтому наша программа будет просто выдавать уже готовую, заполненную схему + маленький бонус. Список слов будем читать из текстового файла. Если будет много желающих именно порешать такие головоломки, с радостью добавлю эту возможность.
Нус, от слов к делу – задача есть, желание есть, поехали!
Архитектура
Ну или Как будем все хранить и рисовать.
Вариантов у меня было много, на этой стадии я несколько раз переделывал все чуть ли не с нуля. Думаю найдутся те кто увидит решение по проще и изящнее, в любом случае здравая критика приветствуется.
Изначальная идея — создать класс «клетки с буквой» и класс контейнер для этих клеток «слово». Каждая «клетка с буквой» хранит в себе свой символ, плюс две логические координаты, умножая эти координаты на размер клетки (константа) без труда определяем место рисования клетки и символа. Основная сложность здесь для меня была в том, что все слова делятся на два типа: горизонтальные и вертикальные. Соответственно вся их обработка при таком подходе тоже будет иметь две версии. От этого хотелось избавиться.
Следующая мысль: у каждого слова одна координата общая для всех клеток у горизонтальных слов это Y, а у вертикальных X. Сделаем так: у нас будет «координата слова», постоянная величина для этого слова, и каждая клетка в свою очередь содержит лишь одну координату, разную у всех клеток в слове. «Фууууух, запутанно как-то», — скажете вы, но лучшего решения я не нашел, возможно в коде будет понятнее. Кстати, в конце статьи ищите сcылку на GitHub, можно будет посмотреть код проекта целиком.
Наша «клетка с буквой»
public class CharCell {
private char value;
private int variableCoord;
public final static int CELL_SIZE = 30;
public CharCell( char value, int variableCoord ) {
this.value = value;
this.variableCoord = variableCoord;
}
...
}
Наше «слово»
В этом классе хранится массив CharCell — все буквы нашего слова, координата этого слова и поле int orientation, которое как можно догадаться может иметь два значения
public class Orientation {
public final static int HORIZ = 0;
public final static int VERTIC = 1;
}
Такая вот простая и конечно небезопасная реализация перечислений, заранее прошу прощения, но не хотелось долго останавливаться на этом пункте.
public class Word {
private CharCell [] cells;
private int orientation;
private int wordCoord;
private int length;
public Word( String word, int orientation, int wordCoord, int initialVariableCoord ) {
this.orientation = orientation;
this.wordCoord = wordCoord;
this.length = word.length();
cells = new CharCell[length];
for ( int i = 0 ; i < length ; i++ ) {
cells[i] = new CharCell( word.charAt(i), initialVariableCoord + i ) ;
}
}
...
}
Как видно код создания нового слова, совершенно не зависит от его «ориентации» в пространстве, также никаких различий в обработке не будет и в других, более сложных функциях – добавления, проверки и т.д. Но обо всем по порядку, рассмотрим пока, как собственно рисуются наши буквы.
Рисование
Код рисования лежит в классе CharCell и заключен в методе showCharCell(см ниже) именно здесь у нас и идет разделение на горизонтальные и вертикальные слова.
Чтобы начать рисовать, нужно определить класс, наследующий JComponent и переопределить метод paintComponent (). Таким классом в нашей программе является класс WordArea, о котором речь пойдет чуть позже. Именно из этого класса функция showCharCell принимает Graphics2D и другие параметры. Метод paintComponent () получает один параметр типа Graphics, в котором и содержатся все методы рисования и набор установок для изображения рисунков, фигур и текста. Каждый раз когда необходимо нарисовать окно выполняется метод paintComponent () всех его компонентов.
Собственно процедура рисования нашей «клетки с буквой»
public void showCharCell ( Graphics2D g2D, Font font, FontRenderContext context, int orient, int constCoord ) {
int coordX;
int coordY;
if ( orient == Orientation.HORIZ ) {
coordX = variableCoord * CELL_SIZE;
coordY = constCoord * CELL_SIZE;
}
else {
coordX = constCoord * CELL_SIZE;
coordY = variableCoord * CELL_SIZE;
}
String s = String.valueOf(value);
Rectangle2D bounds = font.getStringBounds( s, context );
LineMetrics metrics = font.getLineMetrics( s, context );
float descent = metrics.getDescent();
float leading = metrics.getLeading();
Rectangle2D.Double rect = new Rectangle2D.Double( coordX, coordY, CELL_SIZE, CELL_SIZE );
double x = rect.getX() + (rect.getWidth() - bounds.getWidth())/2;
double y = rect.getY() + rect.getHeight() - descent - leading;
g2D.draw( rect );
g2D.drawString( s, (int)x, (int)y );
}
Метод getStringBounds()возвращает прямоугольник, ограничивающий строку, которую мы хотим нарисовать. Это нужно нам, чтобы наша буква находилась точно в середине нарисованного квадрата. Для выравнивания по ширине, сначала получаем ширину квадрата в который хотим вписать нашу букву, часть этой ширины занимает буква, следовательно размер незаполненного пространства с каждой стороны равен половине разности между шириной квадрата и шириной символа. Думаю из кода должно быть понятно. Для выравнивания по высоте вычитаем от нижней стороны нашего квадрата глубину посадки символов и интерлиньяж (descent и leading). Теперь все наши буквы аккуратно рисуются в своих клетках.
Метод класса Word, который нарисует любое слово, элементарный:
public void showWord( Graphics2D g2D, Font font, FontRenderContext context ) {
for ( int i = 0 ; i < length ; i++ ) {
cells[i].showCharCell ( g2D, font, context, orientation, wordCoord );
}
}
Пришло время коснуться самого сложного класса нашего этюда – WordArea
Как говорилось выше он является JComponent и содержит в себе немного модифицированный ArrayList<Word> mainWordArea. Это и есть наша схема слов, добавить в нее новое слово очень просто mainWordArea.add( new Word ( «Слово», Orientation.HORIZ, x, y ) ), именно так наша программа и добавляет слова в нашу схему пробуя все возможные варианты.
Ну а вот и paintComponent ()
@Override
public void paintComponent ( Graphics g ) {
Graphics2D g2D = ( Graphics2D ) g;
g2D.setRenderingHint( RenderingHints.KEY_ANTIALIASING,
RenderingHints.VALUE_ANTIALIAS_ON );
context = g2D.getFontRenderContext();
g2D.setFont( font );
Iterator<Word> wordAreaIter = mainWordArea.iterator();
while ( wordAreaIter.hasNext() )
wordAreaIter.next().showWord( g2D, font, context );
}
Просто перебираем все слова в mainWordArea, отрисовывая каждое из них.
Надеюсь у меня получилось донести до читателя логику работы программы, и мы можем идти дальше, тем более что все приготовления закончились и пришло время решать нашу головоломку!
Перебор с возвратом
Перебор с возвратом (Backtracking) — общий метод нахождения решений задачи, в которой требуется полный перебор всех возможных вариантов. Подробнее можно почитать тут. Я расскажу лишь саму идею касательно нашей программы.
Будет пытаться добавить новое слово из списка пока это возможно, как только в схему станет невозможно добавить новое слово, вернемся на шаг назад, удалив последнее добавленное слово и попробуем добавить другое. Такой алгоритм найдет нам все возможные варианты, казалось бы неплохо, но такая программа работает очень медленно, а для списка в 10 слов я так и не смог дождаться пока она выполнится.
Обратимся за помощью к нашей книге, Уэзерелл пишет:
Качество схем крисс-кросса пропорционально их «связанности», т.е., чем теснее в среднем слова переплетены с соседями, тем интереснее головоломка. Когда ваша программа заработает, позаботьтесь об увеличении связанности.
Связанность! — вот ключ к оптимизации нашей программы. Связанность будем рассчитывать как отношение числа пересечений в схеме, к ее площади. При этом перебирая все варианты, будем сразу отбрасывать потенциально не оптимальные (плохо связанные частичные решения).
На этом этапе готов представить вам собственно сам метод перебора — wordsBackTracking()
Он будет вызывать несколько других вспомогательных методов. За отклонение не оптимальных частичных решений будет отвечать метод reject(). Возможно из-за такого подхода найдется список слов, для которого программа выдаст не самое оптимальное решение, но в большинстве случаев результат довольно хорош. Определять, достигли мы решения или нет будет метод accept(). Все вспомогательные методы я здесь размещать не буду, желающие могут посмотреть в исходниках. Ну а главную связку представлю.
wordsBackTracking()
/**
* Перебор всех слов с возвратом (Backtracking)
* Составляет схему крисс-кросс
*/
private void wordsBackTracking ( ArrayWord<Word> wordArea, List<String> words ) {
if ( accept( wordArea ) ) {
ArrayWord<Word> tempWordArea = new ArrayWord<Word>( wordArea );
copyArrayWord( tempWordArea, wordArea );
allWordArea.add( tempWordArea );
mainWordArea = tempWordArea;
return;
}
if ( reject( wordArea, words ) ) return;
for ( int i = 0 ; i < words.size() ; i++ ) {
List<String> tempWords = new LinkedList<String>( words );
String newWord = tempWords.get(i);
tempWords.remove(i);
addNewWord( wordArea, tempWords, newWord );
}
}
/**
* Добавляет новое слово, если это возможно
*/
private void addNewWord ( ArrayWord<Word> wordArea, List<String> words, String newWord ) {
Word existentWord;
for ( int k = 0 ; k < wordArea.size() ; k++ ) {
existentWord = wordArea.get(k);
///сравниваем символы в новом и уже занесенном словах
for ( int i = 0 ; i < existentWord.length() ; i++ ) {
for ( int j = 0 ; j < newWord.length() ; j++ ) {
if ( existentWord.get(i).value() == newWord.charAt(j) ) {
int newOrient = invert( existentWord.orientation() );
int newWordCoord = existentWord.get(i).coord();
int initialVariableCoord = existentWord.coord() - j;
Word word = new Word (newWord,newOrient,newWordCoord,initialVariableCoord);
///если слово "проходит" проверку - добавляем его
int interCount = wordArea.intersectCount();
if ( check ( wordArea, word, existentWord.coord() ) ) {
wordArea.add ( word );
///сохраняем смещение относительно (0,0) сохранив предыдущие
int minX = wordArea.minX();
int minY = wordArea.minY();
if ( existentWord.orientation() == Orientation.HORIZ )
wordArea.setMinY( initialVariableCoord );
else wordArea.setMinX( initialVariableCoord );
///запускаем косвенную рекурсию
wordsBackTracking ( wordArea, words );
///убираем последнее добавленное слово
wordArea.remove( wordArea.size()-1 );
wordArea.reset();
wordArea.setMinX( minX );
wordArea.setMinY( minY );
wordArea.setInterCount( interCount );
}
}
}
}
}
}
wordsBackTracking принимает два аргумента: схему слов крисс-кросс(с одним словом, с несколькими или со всеми) и список еще не использованных слов. Если решение подходит, запоминаем его. Если решение не оптимально выходим из функции, сокращая дерево поиска.
Метод addNewWord() пытается добавить новое слово в схему, следя за тем, чтобы оно не нарушало правила составления кроссвордов, когда это получается, переходит на следующий уровень рекурсии снова вызывая wordsBackTracking(). Так эти две косвенно-рекурсивные функции находят вполне годные схемы. Слишком длинные списки слов, задавать не советую, но пример из книги находится на раз-два.
Чуть не забыл про обещанный бонус, если его можно так назвать: как мог увидеть внимательный читатель все наши найденные решения сохраняются, и пощелкав мышкой по фрейму можно их просмотреть. Думаю будет интересно увидеть как программа находит все более изящные решения.
А вот еще пример из 16 слов:
Спасибо за внимание!
Как и обещал ссылка на GitHub
Файл со словами words.txt
Собирать: javac CrissCrossFrame.java
Запускать: java CrissCrossFrame
На этом, уважаемый читатель, разрешите откланяться и еще раз спасибо за прочтение.
