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