Jewels

This task should be coded in Lua or Python (3.6.9, pypy). Feel free to try earlier Lua puzzles to get quickly acquainted with the language. You may also read brief intro to Lua with links to documentation and tools.

Ah that game called "Match 3" or "3-in-a-row" or some word related to Jewels... Probably millions of people play various versions of it on their mobile phones nowadays. We are going goo.

The goal is to write a small function in Lua which suggests which move could be made for given placement of "jewels" on the board. The problem is accompanied by "challenge" - so you can try various algorithms in order to improve the overall score.

Gameplay

Square Board of N*N size is filled with symbols (jewels) of 7 types. On every move you are to swap two adjacent symbols (either horizontally or vertically) so that at least one line of 3 or more "jewels" is formed (either horizontally or vertically also).

Such "matching" line (or more than one) are "exploded" leaving empty spaces and then "shakedown" happens - all jewels above (upper, vertically) the empty spaces slide down. After this some more lines may be formed accidentally, they are "exploded" also. So there may be several "cascades" in one move.

When there is no more lines of 3 or more, the move is completed and we calculate points for it, depending on how many "jewels" were removed in all "cascades". Only 1 point is scored for single line of 3, 2 points for 4 and 4 for 5 "jewels" - and so on:

points = 2 ^ (jewels_removed - 3)

After the move is completed, empty spaces are refilled by random jewels again.

Let's see a small example:

E G A C C B G D   E G A C C B G D   E G A C C * G D
E D C C G D E C   E D C C G D E C   E D C C G * E C
D B G E E A C F   D B G E A * C F   D B G E A * C F
A F B D G E A C   A F B D G * A C   A F B D G B A C
F A F C G E C G   F A F C G * C G   F A F C G D C G
C G C D D F B E   C G C D D F B E   C G C D D F B E
F F E F A D G E   F F E F A D G E   F F E F A D G E
F A A D E D G B   F A A D E D G B   F A A D E D G B

On the first move player decides to swap E which is 5-th in 3-rd row to the right. This explodes vertical line of three E-s in the 5-th column, letters B and D above them slide down. Thre new letters are filled, say A, F, C.

E G A C C A G D   E G A C C A G D   E G A * * * G D
E D C C G F E C   E D C C G F E C   E D C C C * E C
D B G E A C C F   D B G E A C C F   D B G C G * C F
A F B D G B A C   A F B D G B A C   A F B E A A A C
F A F C G D C G   F A F C G F C G   F A F D G F C G
C G C D D F B E   C G C * * * B E   C G C C G C B E
F F E F A D G E   F F E F A * G E   F F E F A B G E
F A A D E D G B   F A A D E * G B   F A A D E F G B

On the second move it is possible to swap down the letter D which is 6th in the 5-th row. This explodes five letters D, and after remaining letters slide down, there are also line of C and line of A to explode. After sliding lone G down once more the three G are also exploded - hence the total score for that move is 2048 unless I'm mistaken.

For larger example please see this "paste".

Technical details

Write a function in Lua which takes the 2D array as argument and returns three values col, row and dir - i.e. column and row of the jewel to swap - and direction of the swap. Two moves mentioned above would be represented as 5, 3, 'R' and 6, 5, 'D' in that format.

In case when you want to stop (e.g. not seeing any good move) return Q as direction - e.g. 1, 1, Q.

Your function will be applied to 4 games, on fields of various sizes (N = 8, 11, 12, 13). The goal is to maximize the total score. The function is its simplest way is like this

-- lua version                          optional "guru" versions:
function suggest(board)         |
    return 1, 1, 'R'            |       function suggest(board, boardNo, move, elapsed)
end                             |

-- python version               |
def suggest(board):             |       def suggest(board, boardNo, move, elapsed)
    return 1, 1, 'R'            |

Make sure it is called suggest. The board parameter is array of N rows, each represented as the array of N characters (single letter strings), e.g.

{{'E', 'G', ...}, {'E', 'C', ...}, ...}

If you need more control over execution process, accept 3 more parameters to your function - board number (from 1 to 4), move number (starts from 1) and time elapsed in seconds.

You can create additional functions and set any global variables.

Any of the games won't run longer than for 1000 moves. Moves without score will result in error. Execution time limit is 1 second. If you hit the limit try reducing your search depth or improve in some other way.

Supplying jewels to fill the board after each move is based on reproducible sequence of random values, hence the same algorithms should always yield the same score (unless algorithm itself contains randomness). Process of filling will never itself create lines of 3 or more.