Ratsuparit

Annettuna on shakkilauta, jossa on $8 \times 8$ ruutua. Jokainen ruutu on joko tyhjä tai siinä on ratsu. Laudan kuvauksessa merkki . tarkoittaa tyhjää ruutua ja merkki * tarkoittaa ratsua.

Tehtäväsi on muodostaa ratsuista mahdollisimman monta paria, jotka uhkaavat toisiaan. Jokainen ratsu voi kuulua enintään yhteen pariin. Ratsut uhkaavat toisiaan, jos niiden vaaka- ja pystyetäisyyksistä toinen on $1$ ja toinen on $2$ (shakin sääntöjen mukaisesti).

Toteuta tiedostoon knights.py funktio count_pairs, joka antaa suurimman parien määrän.

def count_pairs(grid):
    # TODO

if __name__ == "__main__":
    grid = ["*.......",
            "..*...*.",
            "........",
            ".*......",
            "...*....",
            ".......*",
            "........",
            "......*."]

    print(count_pairs(grid)) # 3

    grid = ["*.***.**",
            "*******.",
            "*.**.**.",
            "***.****",
            "..****.*",
            "********",
            "*.******",
            "***.**.*"]

    print(count_pairs(grid)) # 25