How can I code this problem? (C++)

Question

I am writing a simple game which stores datasets in a 2D grid (like a chess board). Each cell in the grid may contain a single integer (0 means the cell is empty). If the cell contains a number > 0, it is said to be "filled". The set of "filled" cells on the grid is known as a "configuration".

My problems is being able to "recognize" a particular configuration, regardless of where the configuration of cells are in the MxN grid.

The problem (in my mind), breaks down into the following 2 sub problems:

1. Somehow "normalising" the position of a configuration (for e.g. "rebasing" its position to (0,0), such that the smallest rectangle containing all cells in the configuration has its left vertice at (0,0) in the MxN grid

2. Computing some kind of similarity metric (or maybe simply set difference?), to determine if the current "normalised" configuration is one of the known configurations (i.e. "recognized")

I suspect that I will need to use std::set (one of the few STL containers I haven't used so far, in all my years as a C++ coder!). I would appreciate any ideas/tips from anyone who has solved such a problem before. Any code snippets, pseudocode and/or links would be very useful indeed.

Answer 1

Similarity metrics are a massive area of academic research. You need to decide what level of sophistication is required for your task. It may be that you can simply drag a "template pattern" across your board, raster style, and for each location score +1 for a hit and -1 for a miss and sum the score. Then find the location where the template got the highest score. This score_max is then your similarity metric for that template. If this method is inadequate then you may need to go in to more detail about the precise nature of the game.

Answer 2

Maybe you could use some hash function to identify configurations. Since you need to recognize patterns even if they are not at the same position on the board, this hash should not depend on the position of the cells but on the way they are organized.

If you store your 2D grid in a 1D array, you would need to find the first filled cell and start calculating the hash from here, until the last filled cell.

Ex:

-----------------
|   |   |   |   |
-----------------
|   | X | X |   |
-----------------
|   |   | X |   |
-----------------
|   |   |   |   |
-----------------

----------------+---------------+---------------+----------------
|   |   |   |   |   | X | X |   |   |   | X |   |   |   |   |   |
----------------+---------------+---------------+----------------
                    |_______________________|
                                |
               Compute hash based on this part of the array

However, there are cases where this won't work, e.g. when the pattern is shifted across lines:

-----------------
|   |   |   | X |
-----------------
| X |   |   |   |
-----------------              Different configuration in 2D.
| X |   |   |   |
-----------------
|   |   |   |   |
-----------------

----------------+---------------+---------------+----------------
|   |   |   | X | X |   |   |   | X |   |   |   |   |   |   |   |
----------------+---------------+---------------+----------------
            |_______________________|
               Seems similar in 1D

So you'll need some way of dealing with these cases. I don't have any solution yet, but I'll try to find something if my schedule allows it!

After thinking a bit about it, maybe you could use two different representations for the grid: one where the lines are appended in a 1D array, and another one where the columns are appended in a 1D array. The hash would be calculated with these two representations, and that would (I think) resolve the problem evoked above.