Faculty computer science and technologies
Department of Software Engineering
Speciality Software Engineering
Japanese crosswords. Solution algorithm
Nowadays there are a lot of different puzzles that allow you to have fun and enjoy your time. Among them, Japanese puzzles especially stand out: kakuro, sudoku and, of course, Japanese crosswords. Even as a child, I liked solving Sudoku and I always looked at the Japanese crossword puzzles located in the same magazines with bewilderment. They were very complex and incomprehensible to me, although I tried to understand them. Since I couldn’t figure it out, I left them. And he returned to them 10 years later, when he was already at the university. During the summer holidays I had a lot of free time and I decided to try to figure it out again and this time it worked. Since that time they are probably the most beloved puzzles.
Among the masters of our university there are several people who covered this topic in their individual section [,]. Moreover, Nina Avci did it very well, talking about general description crossword puzzles, the history of their origin, general methods and principles of solution. She also covered the features of black and white and color crosswords. However, the solution algorithm and methods themselves were not described in detail, so in this section I want to describe them formally, in a form in which they can be used to write a program for solving Japanese crossword puzzles as a person.
Designing a software model
In order to describe in detail the algorithm for solving Japanese crossword puzzles, you first need to briefly describe the software model and how it works. A Japanese crossword puzzle consists of a main field on which there are cells that can have 3 states: filled, empty and undefined. This field is divided into rows and columns, next to which there are numbers indicating the number of cells that must be filled in. Based on this, a class diagram was developed, shown in Figure 1.
Figure 1 - Class diagram
The algorithm for solving the Japanese crossword will not be applied to the entire crossword at once, but one by one for rows and columns, because in essence there are no significant differences between them. Consequently, the solution algorithm is reduced to the analysis of one line of cells and the corresponding numbers that determine the shading.
The Nonogram class has a queue of line numbers for analysis. After each analysis of the line, the method returns the numbers of the modified cells so that they can be added to the queue for analysis, since when modifying the cells, some changes could appear that would advance the solution.
It should be noted that the developed program does not implement all solution methods as a human. Only methods that work with outer groups and empty spaces are implemented. Other methods are described in detail in.
The source code of the program can be obtained from .
Method Crossing extreme boundaries
Each number group in the line is analyzed and the rightmost and leftmost boundaries of the number group are found. If the difference between the right and left borders is greater than or equal to zero, then you can fill the cells located between them (inclusive). It is worth noting that, as can be seen from the figure, groups that intersect only with themselves are shaded in the final line, so cell No. 6 is not shaded, since in different positions (left and right) it belongs to different numerical groups.
Figure 2 - Example of line analysis using intersections of extreme boundaries
Method Pushing off walls
The outermost non-empty intervals are analyzed. If there are filled cells at a distance of a number group from the edge, then you can color the cells, starting with the shaded one and up to the cell equal to the size of the number group.
If the number of shaded cells is equal to the size of the numerical group, then the numerical group can be crossed out, and after the group the cell (the minimum space between the groups of cells) can be crossed out.
Figure 3 - Example of line analysis using wall repulsions
Method Unreachable
Extreme numerical groups are analyzed. If the distance from the beginning of an undefined fragment of a line to the first filled cell is less than or equal to the outermost numerical group, then it is necessary cross out the cells that the number group does not reach.
It is also necessary to consider the case if there is one uncrossed group in the line. In this case, it is necessary to cross out all the cells that are further from the filled cells by the length of the number group.
Japanese crosswords(scanwords) are encoded images. Player Challenge and Goal logic game- solve this image.
The coding goes like this. Let's say we have an image:
For each line, we count the lengths of the shaded segments and write these numbers next to the corresponding stripes:
Now we repeat the same operation for the scanword columns and write the corresponding sets of numbers above the columns:
Now we remove the image and leave only the numbers. This is a ready-made Japanese crossword puzzle:
The player's task is to reconstruct the picture using only numbers.
General logic and tactics for solving Japanese crosswords
The logic is very simple. You need to find horizontal lines or vertical columns where you can draw some conclusion about which cells are shaded and which are not shaded. You display these logical conclusions with labels. As you receive more and more new clues, you move further and further until the crossword puzzle is completely solved.
Let's now look at some techniques
Where to start solving a Japanese crossword puzzle
At first, the scanword is not filled in. For now you only know the numbers. Let's see what you can do in this situation.
The simplest techniques: solving at first sight
As you have seen, there are times when you can definitely tell how a row is filled. For example:
can be filled in only one way - all cells are painted over.
A slightly less obvious case:
turns out to be just as simple and unambiguous:
But such situations do not occur often.
Partial solution of the crossword puzzle at a glance
Often a row or column cannot be fully figured out right away, but we can still draw some conclusions about how it is filled.
Let's look at an example:
There are three possible filling options:
As you can see, in all these options the third cell is painted over. From this we can conclude: “We don’t know exactly how this row is filled, but the third cell in it is definitely filled”:
A similar approach works in more complex logical problems. Example:
The following options are possible here:
and we can conclude that there are as many as four filled cells in the scanword:
We have not solved the series completely, but we have received quite a bit of information. Let's now see how to use it and continue solving it.
How to continue solving a crossword puzzle using incomplete information.
So. Do you already know something about how to clarify these conclusions and get closer to a complete solution?
Let's introduce one more notation. We will denote with the symbol “✕” those positions that we know for sure that they are not shaded.
Such information is also very valuable when solving.
You know something is painted over
If you already know that some cell in a row/column is shaded, then you can often conclude that some cells are definitely not shaded.
The simplest case is when there is only one strip in a row. Let's say you have this situation:
We already know that one cell must be painted over. And we are left with only three options:
That is, we can say with confidence that the two outermost cells on each side are definitely not painted:
If there is more than one colored stripe in a row/column, then the situation becomes more complicated, but even here a conclusion can be drawn.
Consider this example:
At first glance, the shaded cell could be part of either of the two stripes, and we cannot say anything definite. But if you look closely, it becomes clear that a strip of two cells cannot be located to the right of the shaded cell. After all, then they will stick together and there will no longer be two cells in the strip. This means that the rightmost cell is definitely empty:
And applying the knowledge from the previous presentation, we can draw a conclusion about two more cells:
And this is already very good.
You know something is not painted over
At the previous step, we began to see cells that we know for sure that they are not painted over. This is very useful information and very easy to use.
Very often you can infer other unfilled cells. Let's look at an example:
Here all the strips have a length of 2, which means none of them can fit to the right of an unfilled cell. This means that the rightmost cell is not painted over.
And of course, we can draw a conclusion about two more cells, using the techniques described above (by considering all the options for the location of the shaded stripes, and highlighting the cells that turn out to be shaded in any case):
We found out the color of three cells in the scanword puzzle.
Let's consider another logical technique.
Unfilled cells divide the line/column into segments, and quite often it is possible to determine which segments contain which stripes. Look at the example:
For convenience, I designated the segments with letters of the Latin alphabet.
It is clear that segment A is empty, since it cannot contain a segment of four shaded cells. Conclusion one:
Two two-cell segments cannot fit into segment D (otherwise they will “stick together”). This means that each of our three segments occupies one of the three remaining segments. We can draw the following conclusions about the first two segments:
Overall, we have made good progress.
By combining these logical techniques you can solve any Japanese crossword puzzle. Or rather, any crossword puzzle on this site, since there are unsolvable ambiguous Japanese crosswords. But all the scanwords on this site have been checked and are not only solvable, but also allow for a step-by-step solution.
Japanese crosswords
A Japanese crossword is a puzzle in which an image is encrypted using numbers. The purpose of the puzzle is full recovery this image.
Japanese crosswords are divided into two types - black and white and color. In black and white crosswords, the image contains only two colors - black (which is what we draw with) and white (the background color). In color crosswords, the image is created using several colors on a white background.
The field of a Japanese crossword puzzle is lined with horizontal and vertical lines of different thicknesses. The thickest lines separate the central part (the field for the picture) from the numbers. Using thinner lines, the field is divided into groups of 5 cells (both horizontally and vertically) - this is done solely for convenience (it is more convenient to count the width/height of groups of cells). The image itself in the Japanese crossword is formed by painting individual cells (the central part) in the desired color. An unpainted cell is considered white.
The numbers indicated on the left and top of the crossword puzzle describe groups of colored cells (consecutive, without gaps) horizontally and vertically, respectively. Moreover, the order of these numbers describes the order of arrangement of these groups, but where each group begins and ends is not known (in fact, determining their position is the task of the puzzle). Each individual number denotes a separate group of a given size (i.e., number 5 denotes a group of five cells shaded in a row, 1 - a group of one single shaded cell). In black and white crosswords we always paint the cell black, in color crosswords we always paint the cell with the color with which the number is marked. Between groups of the same color there must be at least one unshaded cell (just otherwise they would be considered one group), between groups different colors There may not be any empty cells.
| on a note | The main requirement for Japanese crosswords is that the crossword must have a single logical solution, achievable without various “guessing” (trial and error). But, unfortunately, quite often you can find crosswords that have several solutions, or crosswords that cannot be solved by purely analytical methods. Sometimes there are even crosswords that have errors (or rather typos), which make the crossword completely unsolvable. For this reason, we recommend that beginners do not pay attention to cheap newspapers/magazines with Japanese crosswords, and be very careful about Japanese crosswords in newspapers that do not specialize in this type of crosswords, because Errors are very common in such publications. We would also like to note that for all crossword puzzles located on our website, we guarantee that they do not contain errors and that they all have exactly one solution, achievable without “guessing.” |
How to solve Japanese crosswords
The solutions to color crosswords and black and white crosswords are slightly different (since in black and white crosswords you do not need to take into account the color of the cells, the rules are a little simplified) - so for now we will talk exclusively about black and white crosswords.
When solving Japanese crosswords, a person considers each row/column separately, constantly moving on to the next columns and rows. In this case, the solution process in each row/column is reduced to:
- Determining the cells that will definitely be painted over (for any possible arrangement of groups) - we paint them over.
- Determining cells in which the presence of shaded cells is impossible - such cells are crossed out with a cross (sometimes a thick dot is used instead of a cross).
- Determining numbers whose position has already been calculated - usually these numbers are crossed out.
Thus, marks gradually appear on the field, which at the next step help to calculate new marks, then again and again, until the crossword puzzle is completely solved (it is worth noting that if at least one mark was placed incorrectly, this can lead to to a deadlock solution).
Example solution
So, let's try to solve the simplest black and white crossword puzzle:
 | Here we have a simple crossword puzzle measuring 9x9 cells. We will gradually solve this crossword puzzle, explaining each step. To avoid confusion, we will mark new notes in blue. |
 | First, let's see if there are lines in the crossword puzzle that should be completely filled in. It turns out that there is - in our case it is the number 9 in the fourth line. Because The width of the crossword puzzle is exactly 9 cells - which means that all the cells in this line must be filled in. At the same time, we cross out the number 9 itself so that it does not distract us. |
 | By analogy, we are looking for columns that should be completely filled in. |
 | Let's look at the third line. Let's remember a small rule that will help us a lot - if there is only one number next to a row or column and it is more than half the length, then you can paint over several cells in the middle. In our case, these are the central five cells. Why? No matter how you place a group of seven cells in nine cells, the five central ones will always be shaded (to calculate this, you can subtract the value of the number from the width of the crossword puzzle - we get the number 2, which means the number of “unknown” cells on the left and right, and paint over the remaining central five cells). |
 | Now we can mark with crosses (or dots) the cells that clearly cannot be painted over. Let's look at the first line - it is completely guessed, because... We already have one colored cell, and there shouldn’t be more colored cells in it. This means that all other cells are marked with crosses. Similarly in the sixth and seventh lines. Don't forget to cross out the numbers in the solved lines. |
 | In the fifth line we have one filled cell, and so. in this line there is nothing else except single cells; we can mark the cells to the left/right of the solved one with crosses. We cannot cross out numbers, because... Although we guessed one number, we don’t know exactly which one. The situation is similar in the eighth line. Also in the ninth line we can say for sure that the first two cells and the last two will definitely not be painted over. Why? It’s just that we have already solved one cell in this line, and the only number in this line, three, must be part of this shaded cell. |
 | Now let's look at the first column - just like in the previous step, we have only one number in this column - two, and one solved cell. Accordingly, the first two and last four cells will definitely not be painted over. The situation is similar in the second and last four columns. |
 | You can notice that there are very few empty cells left in the central five columns, even moreover, their number exactly corresponds to the numbers indicated above. This means that all these cells can be painted over. |
 | Moving down to the lines, we can see that the second and last two lines have already been solved. And in the fifth line we can put crosses to the left and right of the solved cells, because There is nothing except single cells in this line. |
 | Now we can see that in the fifth line there are only two free cells left, just for the two remaining ones. (it is worth noting that the fifth line could have been solved from the very beginning, since five single cells of the same color can be arranged in nine cells in only one possible way) |
 | Moving on to the columns, we see that the first and last columns have already been solved. All that remains is to color the last cells in the second and eighth columns, and... Congratulations! The crossword puzzle is completely solved! |
In a Japanese crossword, the picture is encrypted using numbers located to the left and top of the grid. Each number indicates how many cells in a row need to be shaded in that row or column. Let's consider specific example Japanese crossword solutions:
First you need to find the most big numbers, which are more than half the length of the row or column in which this figure is located. In this example, these are 8 and 10 (first and second row) and 7 (second and ninth column). The second line is filled in completely, since the number 10 corresponds to the length of the line. For convenience, you can mark this line as guessed; to do this, click on the number 10 and it will turn gray. The first line contains the number 8, which means that in any case 6 cells in the center of the line will be filled in. This statement is verified as follows: suppose that 8 cells are located at the beginning of the line, then at the end of the line there will be 2 unshaded cells, and now suppose that these 8 cells are located at the end of the line, then the first 2 cells will remain unshaded. This means that by leaving 2 unshaded cells at the beginning and end of the line, we take both cases into account and boldly paint over the remaining cells. We do the same with the second and ninth columns, only here we know that the second cell is filled in. i5; Therefore, at the bottom of the column we leave 3 cells unpainted, and at the top we paint over all the cells up to the already known second cell. Now let's mark the last two cells in the second and ninth columns with crosses, since they cannot be painted over. Look for yourself, 6 out of 7 cells are shaded, which means the remaining cell will be either at the beginning or at the end of these 6 shaded cells.
Now let's color the cells in 3-8 columns. The first cells in them are painted over, which means that all that remains is to paint over the remaining cells, in accordance with the topmost number, and put a cross at the end, as shown in the figure below.
In the third and fourth lines everything is clear, we paint over the first and last cells. In the first and ninth columns, cross out the 5 bottom cells, since there cannot be filled cells there. In the sixth and seventh lines, all that remains is to limit the second and ninth cells with crosses. In the tenth line we paint over the 2 central cells and limit them at the top with crosses.
Let's pay attention to the third and eighth columns. It remains to paint a block of two cells, so we mark the fifth cells with a cross. Then in the fifth line we paint over the first and last cells. Now let's look at the first and last columns, they have blocks of four filled cells, so we cross out the first cells in these columns. In the first line we paint over the remaining cells. In the second and ninth columns, blocks of seven filled cells have formed, so we put crosses in the remaining cells.
In the third and eighth columns we paint over the ninth cells. Then in the ninth line we got two blocks of one cell each, which means we mark the remaining cells with crosses. In the eighth line there is only one option for the location of the blocks, so we simply paint them in order. The third and eighth columns have been solved, so we put crosses in the last cells. And now in the last 77th line there is nothing left to do but paint over the remaining cells. In the fifth and sixth columns, color in the fifth cells. Then the fifth line will be solved completely.
In Japanese puzzles, unlike other crosswords, not words, but images are encrypted. When solving it, you need to reconstruct the picture using the numbers that are written to the left of the lines above the columns. The numbers in the Japanese crossword grid show how many groups of black cells are in the corresponding row or column and how many merged black cells each group contains.
For example, a set of numbers 4, 1, and 3 in a Japanese crossword puzzle grid means that there are three groups in this row: the first of four, the second of one, and the third of three black cells. Groups are separated by at least one empty square. Empty cells can also be at the edges of the rows. When solving a Japanese crossword puzzle, you need to determine the placement of these groups of cells.
And now on simple example Let's look at how to solve Japanese crosswords.
The algorithm for solving the Japanese crossword puzzle is as follows. The easiest way to start solving a Japanese crossword is with those lines that are completely filled in. In our example, there are only three such lines of 9 cells each (Fig. 1).
Now let's pay attention to the second line, consisting of two groups of 4 cells. IN in this case The space between groups will appear in the 5th column. After this, in the 1st and 9th columns of the Japanese crossword puzzle, we have 4 cells filled in, which is what we need according to the conditions.
All other cells in these columns of the Japanese crossword definitely turn out to be unshaded. We mark them with crosses (Fig. 2). Next, in the line with the number 7, we paint over all seven remaining cells. In the middle column the beginning of the group was formed - 4 out of 7 required by the condition. Let's complete this group.
Continuing the solution of the Japanese crossword puzzle, we note that the line with the number 1 already has a cell; All others are marked with a cross. In our Japanese crossword, in the line with the number 3, the second and eighth cells must remain free, and in the line with groups 2-2, the third and seventh cells will definitely be filled in (Fig. 3).
Next, we complete columns 3 and 7, connect three cells from the line with the number 5, paint over the two remaining cells in the line with the number 3. Now all that remains is to paint the first cells in the second and eighth column, and the Japanese crossword puzzle is ready (Fig. 4) .
We wish you good luck in solving Japanese crossword puzzles!
