JOIN
 Problem Statement
Contest: Marathon Match 5
Problem: Linez

### Problem Statement

Linez is a single-player board game played on a 9x9 grid. On each turn, the player must move one of the numbers on the board to an empty cell where a clear path (consisting of horizontally connected or vertically connected empty cells) exists between the new position and the old. If five or more same numbers are aligned in a row, column, or diagonal, they will be removed from the board. The player will gain 10+k*(k-5)/2 points (k being the number of removals) and can make another move. Otherwise, three more numbers will be placed onto the board at randomly chosen positions before the player can move again. The objective is to score as many points as possible before the whole board fills up. (An online version of the Linez game is available at http://linez.varten.net/.)

Your task is to write a class to play the Linez game. The method nextMove will be given the board configuration and the next three numbers. board will contain 9 Strings representing the rows of the board from top to bottom. Each element will contain 9 characters. Each character will be '1' to '7' representing the number on that cell, or '.' if that position is unoccupied. nextThree will contain 3 characters. Each element of nextThree will be '1' to '7' representing the number to be added to the board next turn. The return value of nextMove must contain 4 characters, the first two representing the original position of the number to be moved, the next two representing the target position. For example, to move the number "4" from "I8" to "F6" as shown below, return "I8F6".

You will have a total of 20 seconds for each test case. The memory limit is 64MB. Your final score will be the mean score on all the test cases.

### Definition

 Class: Linez Method: nextMove Parameters: String[], String Returns: String Method signature: String nextMove(String[] board, String nextThree) (be sure your method is public)

### Notes

-Each number of nextThree will be chosen uniformly between 1 and 7, inclusive.
-Each empty cell has an equal probability to be chosen when the next number is added to the board.
-If your solution crashes, runs out of time, or tries to make an invalid move it will receive the points it has made so far for that test case.

### Examples

0)

`board:{  ".........",  ".....4...",  ".........",  "......5..",  ".........",  ".........",  "......3..",  ".........",  "........."}nextThree:  "545"`
1)

`board:{  ".........",  ".........",  ".......5.",  "3........",  ".........",  ".........",  ".........",  "....7....",  "........."}nextThree:  "773"`
2)

`board:{  "..6.....4",  ".........",  ".........",  ".........",  ".........",  "...1.....",  ".........",  ".........",  "........."}nextThree:  "154"`
3)

`board:{  ".........",  ".........",  ".........",  ".........",  "7........",  ".........",  ".........",  ".........",  "..6....2."}nextThree:  "563"`
4)

`board:{  ".6.......",  ".....6...",  ".4.......",  ".........",  ".........",  ".........",  ".........",  ".........",  "........."}nextThree:  "745"`
5)

`board:{  ".........",  ".........",  ".6.4.....",  "........6",  ".........",  ".........",  ".........",  ".........",  "........."}nextThree:  "151"`
6)

`board:{  ".........",  ".........",  "......3..",  "..3......",  ".........",  ".........",  "..2......",  ".........",  "........."}nextThree:  "455"`
7)

 `board:{  ".........",  ".........",  ".....1...",  ".........",  ".6.......",  "......5..",  ".........",  ".........",  "........."}nextThree:  "527"`
8)

 `board:{  ".2.......",  ".........",  ".........",  ".........",  "...6.....",  ".........",  ".......1.",  ".........",  "........."}nextThree:  "564"`
9)

 `board:{  "........2",  ".........",  ".........",  ".........",  ".....2...",  ".........",  ".........",  "....5....",  "........."}nextThree:  "624"`

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2010, TopCoder, Inc. All rights reserved.