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

Думаю многим хабровчанам знакома книга «Этюды для программистов» Чарльза Уэзерелла. Если нет, то здесь можно прочитать интервью с автором и небольшой обзор книги. Мне самому совсем недавно попала данная вещь в руки, и было решено обязательно реализовать одну из задачек.

Итак предлагаю разобрать с вами один из этюдов. Писать будем на 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 принимает два аргумента: схему слов крисс-кросс(с одним словом, с несколькими или со всеми) и список еще не использованных слов. Если решение подходит, запоминаем его. Если решение не оптимально выходим из функции, сокращая дерево поиска.
Метод addNewWord() пытается добавить новое слово в схему, следя за тем, чтобы оно не нарушало правила составления кроссвордов, когда это получается, переходит на следующий уровень рекурсии снова вызывая wordsBackTracking(). Так эти две косвенно-рекурсивные функции находят вполне годные схемы. Слишком длинные списки слов, задавать не советую, но пример из книги находится на раз-два.

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

Спасибо за внимание!

Как и обещал ссылка на GitHub
Файл со словами words.txt
Собирать: javac CrissCrossFrame.java
Запускать: java CrissCrossFrame
На этом, уважаемый читатель, разрешите откланяться и еще раз спасибо за прочтение.