Study for a programmer or a crisscross puzzle

I think many habrovchanam familiar book "Etudes for Programmers" by Charles Wetherell. If not, here you can read an interview with the author and a small review of the book. I myself most recently got this thing in my hands, and it was decided to implement one of the tasks.

So I propose to disassemble with you one of the etudes. We will write in Java, work with graphics and GUI + and analyze an iteration algorithm with a return to find our solution. It is unlikely that the article will interest the pros, but for beginners, and especially for those who are just learning Java, the article may be useful.
All interested - welcome!

Formulation of the problem

Here I will give an excerpt from "Etudes", which will introduce the reader to the picture.

Many consider crossword puzzles to be too difficult a puzzle, because they cannot guess the word. But like letters in cells like. For such people, there is a simpler puzzle - criss-cross. Each criss-cross consists of a list of words, divided for convenience into groups according to length and ordered alphabetically within each group, as well as from the scheme into which the words should be written. The scheme follows the same rule as in a crossword puzzle - at the intersection of the word have a common letter, but the numbers are missing, because the words are known in advance, you only need to enter them in the right places.

An example of such a puzzle you can see in the picture.

Honestly, I don’t really like to write letters into the cells, so our program will simply issue a ready-made, completed scheme + a small bonus. The list of words will be read from a text file. If there are many who want to solve such puzzles, I will gladly add this opportunity.
Nous, from words to deeds - the task is there, the desire is there, let's go!

Architecture

Well, or How will we all store and draw .
I had a lot of options, at this stage I reworked everything almost from scratch several times. I think there will be those who see the solution easier and more elegant, in any case, sensible criticism is welcome.
The original idea is to create a class “cells with a letter” and a class container for these cells “word”. Each “cell with a letter” stores its own symbol, plus two logical coordinates, multiplying these coordinates by the cell size (constant) can easily determine the place where the cell and symbol are drawn. The main difficulty here for me was that all words are divided into two types: horizontal and vertical. Accordingly, all their processing with this approach will also have two versions. I wanted to get rid of it.
The next thought: each word has one coordinate common to all cells of horizontal words, Y, and vertical X. Let's do this: we will have a “word coordinate”, a constant value for this word, and each cell in turn contains only one coordinate , different for all cells in the word. “Fuuuuuh, somehow intricate,” you will say, but I haven’t found a better solution, maybe it will be clearer in the code. By the way, at the end of the article look for a link on GitHub , you can see the project code in its entirety.
')

Our "letter cell"

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; } ... } 

Our "word"

This class contains the CharCell array — all the letters of our word, the coordinate of this word, and the int orientation field, which, as you might guess, can have two values

 public class Orientation { public final static int HORIZ = 0; public final static int VERTIC = 1; } 

Such is the simple and certainly unsafe implementation of transfers, I apologize in advance, but I did not want to dwell on this point for a long time.

 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 ) ; } } ... } 

As you can see, the code for creating a new word does not depend at all on its “orientation” in space, nor will there be any differences in processing in other, more complex functions — additions, checks, etc. But first things first, let's consider for now how our letters are actually drawn.

Drawing

The drawing code lies in the CharCell class and is enclosed in the showCharCell method (see below) it is here that we divide the horizontal and vertical words.
To start drawing, you need to define a class that inherits JComponent and override the paintComponent () method. Such a class in our program is the WordArea class, which will be discussed later. It is from this class that the showCharCell function takes Graphics2D and other parameters. The paintComponent () method gets one parameter of the type Graphics , which contains all the drawing methods and a set of settings for the image drawings, shapes and text. Every time the window needs to be drawn, the paintComponent () method of all its components is executed.

Actually the procedure of drawing our "cell with a letter"

 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 ); } 

The getStringBounds () method returns a rectangle bounding the string we want to draw. We need this so that our letter is exactly in the middle of the drawn square. To align with the width, first we get the width of the square in which we want to enter our letter, a part of this width is occupied by a letter, hence the size of the empty space on each side is half the difference between the width of the square and the width of the character. I think the code should be clear. To align height, we subtract the landing depth of symbols and leading ( descent and leading ) from the bottom side of our square. Now all our letters are carefully drawn in their cells.
A Word class method that will draw any word elementary:

 public void showWord( Graphics2D g2D, Font font, FontRenderContext context ) { for ( int i = 0 ; i < length ; i++ ) { cells[i].showCharCell ( g2D, font, context, orientation, wordCoord ); } } 

It's time to touch the most difficult class of our etude - WordArea
As mentioned above, it is a JComponent and contains a slightly modified ArrayList <Word> mainWordArea . This is our word scheme; adding a new word to it is very simple to mainWordArea.add (new Word (“Word”, Orientation.HORIZ, x, y)) , this is how our program adds words to our scheme, trying all possible options.
Well, here is 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 ); } 

Just go through all the words in mainWordArea , rendering each one of them.

I hope I managed to convey to the reader the logic of the program, and we can go further, especially since all the preparations are over and it's time to solve our puzzle!

Enumeration Return

Backtracking is a general method for finding solutions to a problem in which a complete search of all possible options is required. You can read more here . I will tell only the very idea about our program.
It will try to add a new word from the list as long as possible, as soon as it becomes impossible to add a new word to the scheme, go back a step, delete the last added word and try to add another. Such an algorithm will find us all possible options, it would seem not bad, but such a program works very slowly, and for a list of 10 words I could not wait until it was executed.
Turning to our book for help, Weatherell writes:

The quality of the criss-cross schemes is proportional to their “connectedness”, that is, the closer the words are intertwined with their neighbors, the more interesting the puzzle. When your program runs, take care of increased connectivity.

Connected! - that's the key to optimizing our program. The connection will be calculated as the ratio of the number of intersections in the scheme, to its area. In doing so, going through all the options, we will immediately discard potentially non-optimal (poorly coupled partial solutions).
At this stage, I am ready to present you with the actual brute force method itself - wordsBackTracking ()
It will call several other helper methods. The reject () method will be responsible for the deviation of non-optimal partial solutions. Perhaps because of this approach, there is a list of words for which the program will not produce the most optimal solution, but in most cases the result is quite good. The accept () method will determine whether we have reached a decision or not. I will not post all auxiliary methods here, anyone can look at the source code. Well, I will introduce the main bundle.

wordsBackTracking takes two arguments: a criss-cross word scheme (with one word, several or all), and a list of words that have not yet been used. If the solution is right, remember it. If the solution is not optimally exit the function, reducing the search tree.
The addNewWord () method tries to add a new word to the scheme, making sure that it does not violate the rules of creating crossword puzzles, when it turns out, it moves to the next level of recursion again calling wordsBackTracking () . So these two indirectly recursive functions find quite suitable schemes. Too long lists of words, I do not advise you to ask, but the example from the book is once or twice.

I almost forgot about the promised bonus, if you can call it that: as a attentive reader could see, all our found solutions are saved, and by clicking the mouse on the frame you can view them. I think it will be interesting to see how the program finds more and more elegant solutions.
Here is another example of 16 words:

Thanks for attention!

As promised link to github
File with words words.txt
Collect: javac CrissCrossFrame.java
Run: java CrissCrossFrame
On this, dear reader, allow me to bow out and thank you again for reading.