Philippine Crosswords. Finalization of mobile 2D puzzles to work with color crosswords

What is the Philippine crossword.

Colored Filipino crossword puzzles are a kind of puzzles, in the grid of which a picture is encrypted using numbers. Each number located in the grid, except one, has a pair. It is necessary to pick up and connect pairs of numbers with lines so that the lines satisfy the following conditions:

- the length of each line must correspond to the numbers located at its ends;
- lines should not intersect with each other and pass through the same cells;
- lines can go in vertical and horizontal directions, can be refracted, but can not pass diagonally;
- connected pairs of numbers must be of the same color.

Since the unit does not have a pair, it is colored by default. As a result of solving a crossword puzzle, when all pairs of numbers (except for units) are connected by lines, a figure is obtained.
')

Image processing

Work began with the collection of color images in various formats. After I collected a sufficient number of images (more than 4000), the semi-manual-semi-automatic work on their processing began.

I implemented the processing procedures in C ++ using the Gdiplus library - its high-level interface allows you to read and create a file without deep knowledge of image storage formats. After reading the file for ease of manipulation, the information is presented in memory in the form of a matrix, where each element of the array stores information about the r, g, b properties of a particular pixel.

I will show an example of using a simple example. Take an image of 3x5 pixels (for a presentation at Habré, the image is scaled).



and read it with the code of the procedure below.


The result of its implementation:


Processing includes:

• Bringing all formats in png format;
  
  
• Crop. A certain number of pictures have a white field at the edges, which is not interesting to us;
  
  
• Reduction to the "pixel" view. Since the picture obtained as a result of solving the Philippine crossword is presented in the form of a grid, our picture should be no more than 100 pixels in height and width (I initially chose such a restriction on width and height, everything that more either reduced or deleted from my collections).
  
  
• “Similar colors”, which in the RGB notation differ by less than 30 at the same time by three parameters (r, g, b) - must be combined into one color, so that as a result the user can clearly distinguish colors. Otherwise, the numbers in the “similar” colors will be indistinguishable. For example, two such adjacent pixels:
  
  
  
  bring to mind:
  
  
  
  
• If possible, the picture should not be overly filled with colors - no more than 15 different colors.
  
  
• Remove duplicates. As a result of reading the image is considered a hash value and is compared with the rest. If the hash value, width, height and number of colors match, the image is considered a duplicate and is not considered further.
  

Of course, after each stage of processing it is necessary with eyes to check everything for adequacy and correct everything that turned out wrong with your hands.

Job generation

The fun begins. It is necessary for each picture to generate a task (the task is a grid with numbers, the pairs of which must be joined in the process of solving). Each task must have only one solution. It took me 3 months to write the task generation-verification algorithm. The algorithm is implemented by two main procedures:

- the task generation procedure, uses rand () internally to generate randomness;
- job verification procedure.
-
The picture is represented in memory in the form of a matrix, where each element of the array stores information about the r, g, b - properties of a particular pixel. Each of the procedures in the process of performing multiple recursive rounds of this matrix. Simply implement to get straight lines, but in this case, the crossword puzzle will be uninteresting. So that there were repeatedly curving lines in the crossword - we had to pretty much tinker.

The algorithm is cumbersome, I see no reason to provide the source code, I will give a high-level description.

For each picture, a cycle is started for N possible iterations. I will describe the iteration by pseudo code in any form:

 for(...) //    { int cnt_try = 0; // -  do { cnt_try++;  = _(); _ = _(); if(_ == 0) //    _(); }while(_ != 0 && cnt_try <= N); } 

Application coding

For the implementation of this application, I took as a basis the engine that I implemented for the black-and-white Philippine crosswords FCross, which I already described in detail earlier . Work platform - Marmalade SDK, programming language - C ++.

Finishing it for new needs, I got an application for solving colored Philippine crosswords.

Facebook integration and image hosting

I would like to give the user the opportunity to post a crossword puzzle (picture) on his Facebook wall. To do this, you need to register your application on developers.facebook.com, among other things, indicate what permissions the application will ask for from your user. For my scripts, the default permissions are enough - “public_profile”, “user_friends”. Dialogue with confirmation of additional permissions is not required for posting on the wall according to the scenario.

In this case, the Facebook authorization feature in your application will be available without having to be confirmed by the Facebook team, but if your application needs additional permissions, then they need to be installed.

The ability to post a picture is given by specifying its URL for the input parameter of the API method of publication. So you need to store the image on a public hosting, which must meet the requirements put forward by me:

- the possibility of bulk-primary initial download files;
- high availability;
- high reliability - I do not want it to close in a month;
- the URL should open exactly the png-file, and not the web-page with advertising;
- it is important that the URL is not generated by receiving some kind of hash, but so that it can be unambiguously easily matched with the name of the source image being downloaded.

Rummaging around the internet for a few minutes, I settled on Google Cloud Storage . For a fee, they cover all of these conditions. Among other things, this platform provides a command console, which simplifies the manipulation of objects. In my case - more than 4,000 images, and I used it when with one command (gsutil -m acl ch) I made all the objects available via a direct link.

So, since the URL of the image is not generated by the hash, but according to the file name, my application can always get a link to the image in runtime just before publishing. You only need to hard-code the static part of the URL path to the folder in which the target files are located.

For integration with Facebook, the Marmalade SDK s3eFacebook API included in the standard build was used .

The post publication dialog looks like this:

Summing up

As a result of this work, an application came out, which I myself play from time to time. In the process of work, the idea to quit a project repeatedly came up, but I do not regret that I brought it to a logical end.