private.py

# ugly bruteforce algorithm it seems that it's O(m * n^3) where m is some
# integer representing the number of moves.

from pprint import PrettyPrinter
import copy

n = int(raw_input())
matrix = []

for _ in range(n):
    matrix.append(list(raw_input()))


class Game(object):
    def __init__(self, matrix):
        self.matrix = matrix
        self.score = 0
        self.pp = PrettyPrinter()
        self.movesList = []

    def move(self):
        self.count = 1
        x, y = self.currentBestMove()
        print x, y
        self.movesList.append(str(x) + ' ' + str(len(self.matrix) - 1 - y))
        self.eliminate(x, y)
        self.score += self.triangularNumber()
        self.applyGravity()
        self.checkEmptyColumn()

    def checkEmptyColumn(self):
        for i in range(len(self.matrix)-1):
            Empty = True
            for j in range(len(self.matrix)):
                if self.matrix[j][i] is not None:
                    Empty = False
                    break
            if Empty:
                # The column i is empty
                for j in range(len(self.matrix)):
                    self.matrix[j][i], self.matrix[j][i+1]\
                        = self.matrix[j][i+1], self.matrix[j][i]

    def triangularNumber(self):
        return (self.count * (self.count + 1)) / 2

    def applyGravity(self, value=True):
        if not value:
            return
        didSomething = False
        for i in range(len(matrix)-1, 0, -1):
            for j in range(len(matrix)):
                if self.matrix[i][j] is None and\
                   self.matrix[i-1][j] is not None:
                    self.matrix[i][j], self.matrix[i-1][j]\
                        = self.matrix[i-1][j], self.matrix[i][j]
                    didSomething = True
        self.applyGravity(didSomething)

    def eliminate(self, x, y, myCell=-1):
        if myCell == -1:
            myCell = self.matrix[y][x]
        self.matrix[y][x] = None
        p = 1
        # checking right
        try:
            while myCell == self.matrix[y][x+p]:
                self.matrix[y][x+p] = None
                self.count += 1
                self.eliminate(x+p, y, myCell)
                p += 1
        except:
            pass
        p = 1
        # checking left
        try:
            while myCell == self.matrix[y][x-p] and x-p >= 0:
                self.matrix[y][x-p] = None
                self.count += 1
                self.eliminate(x-p, y, myCell)
                p += 1
        except:
            pass

        p = 1
        # checking up
        try:
            while myCell == self.matrix[y-p][x] and y-p >= 0:
                self.matrix[y-p][x] = None
                self.count += 1
                self.eliminate(x, y-p, myCell)
                p += 1
        except:
            pass

        p = 1
        # checking down
        try:
            while myCell == self.matrix[y+p][x]:
                self.matrix[y+p][x] = None
                self.count += 1
                self.eliminate(x, y+p, myCell)
                p += 1
        except:
            pass

    def currentBestMove(self):
        maxScore = 0
        bestX = 0
        bestY = 0
        for i in range(len(self.matrix)):
            for j in range(len(self.matrix)):
                if self.matrix[i][j] is not None:
                    self.currScore = 1
                    self.copyMatrix = copy.deepcopy(self.matrix)
                    self.thisScore(j, i)
                    if self.currScore > maxScore:
                        bestX = j
                        bestY = i
                        maxScore = self.currScore

        return bestX, bestY

    def thisScore(self, x, y, myCell=-1):
        if myCell == -1:
            myCell = self.copyMatrix[y][x]
        self.copyMatrix[y][x] = None
        p = 1
        # checking right
        try:
            while myCell == self.copyMatrix[y][x+p]:
                self.copyMatrix[y][x+p] = None
                self.currScore += 1
                return self.thisScore(x+p, y, myCell)
                p += 1
        except:
            pass
        p = 1
        # checking left
        try:
            while myCell == self.copyMatrix[y][x-p] and x-p >= 0:
                self.copyMatrix[y][x-p] = None
                self.currScore += 1
                return self.thisScore(x-p, y, myCell)
                p += 1
        except:
            pass

        p = 1
        # checking up
        try:
            while myCell == self.copyMatrix[y-p][x] and y-p >= 0:
                self.copyMatrix[y-p][x] = None
                self.currScore += 1
                return self.thisScore(x, y-p, myCell)
                p += 1
        except:
            pass

        p = 1
        # checking down
        try:
            while myCell == self.copyMatrix[y+p][x]:
                self.copyMatrix[y+p][x] = None
                self.currScore += 1
                return self.thisScore(x, y+p, myCell)
                p += 1
        except:
            pass

myGame = Game(matrix)
myGame.move()
myGame.move()
myGame.move()
# while True:
#    lastScore = len(set(myGame.movesList))
#    myGame.move()
#    if len(set(myGame.movesList)) == lastScore:
#        myGame.score -= 1
#        break
#    print myGame.score
print myGame.score
print myGame.movesList