Этюд для программиста или головоломка крисс–кросс

Итак предлагаю разобрать с вами один из этюдов. Писать будем на 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(). Все вспомогательные методы я здесь размещать не буду, желающие могут посмотреть в исходниках. Ну а главную связку представлю.

/**      *  Перебор всех слов с возвратом (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
На этом, уважаемый читатель, разрешите откланяться и еще раз спасибо за прочтение.