## Hoeveel sprongen heeft een paard minstens nodig om van de ene hoek
## van een schaakbord naar de diagonaal tegenovergestelde hoek te springen?

buren = {"a1":["c2", "b3"],
"b1":["d2", "c3", "a3"],
"c1":["e2", "a2", "d3", "b3"],
"d1":["f2", "b2", "e3", "c3"],
"e1":["g2", "c2", "f3", "d3"],
"f1":["h2", "d2", "g3", "e3"],
"g1":["e2", "h3", "f3"],
"h1":["f2", "g3"],
"a2":["c3", "c1", "b4"],
"b2":["d3", "d1", "c4", "a4"],
"c2":["e3", "a3", "e1", "a1", "d4", "b4"],
"d2":["f3", "b3", "f1", "b1", "e4", "c4"],
"e2":["g3", "c3", "g1", "c1", "f4", "d4"],
"f2":["h3", "d3", "h1", "d1", "g4", "e4"],
"g2":["e3", "e1", "h4", "f4"],
"h2":["f3", "f1", "g4"],
"a3":["c4", "c2", "b5", "b1"],
"b3":["d4", "d2", "c5", "a5", "c1", "a1"],
"c3":["e4", "a4", "e2", "a2", "d5", "b5", "d1", "b1"],
"d3":["f4", "b4", "f2", "b2", "e5", "c5", "e1", "c1"],
"e3":["g4", "c4", "g2", "c2", "f5", "d5", "f1", "d1"],
"f3":["h4", "d4", "h2", "d2", "g5", "e5", "g1", "e1"],
"g3":["e4", "e2", "h5", "f5", "h1", "f1"],
"h3":["f4", "f2", "g5", "g1"],
"a4":["c5", "c3", "b6", "b2"],
"b4":["d5", "d3", "c6", "a6", "c2", "a2"],
"c4":["e5", "a5", "e3", "a3", "d6", "b6", "d2", "b2"],
"d4":["f5", "b5", "f3", "b3", "e6", "c6", "e2", "c2"],
"e4":["g5", "c5", "g3", "c3", "f6", "d6", "f2", "d2"],
"f4":["h5", "d5", "h3", "d3", "g6", "e6", "g2", "e2"],
"g4":["e5", "e3", "h6", "f6", "h2", "f2"],
"h4":["f5", "f3", "g6", "g2"],
"a5":["c6", "c4", "b7", "b3"],
"b5":["d6", "d4", "c7", "a7", "c3", "a3"],
"c5":["e6", "a6", "e4", "a4", "d7", "b7", "d3", "b3"],
"d5":["f6", "b6", "f4", "b4", "e7", "c7", "e3", "c3"],
"e5":["g6", "c6", "g4", "c4", "f7", "d7", "f3", "d3"],
"f5":["h6", "d6", "h4", "d4", "g7", "e7", "g3", "e3"],
"g5":["e6", "e4", "h7", "f7", "h3", "f3"],
"h5":["f6", "f4", "g7", "g3"],
"a6":["c7", "c5", "b8", "b4"],
"b6":["d7", "d5", "c8", "a8", "c4", "a4"],
"c6":["e7", "a7", "e5", "a5", "d8", "b8", "d4", "b4"],
"d6":["f7", "b7", "f5", "b5", "e8", "c8", "e4", "c4"],
"e6":["g7", "c7", "g5", "c5", "f8", "d8", "f4", "d4"],
"f6":["h7", "d7", "h5", "d5", "g8", "e8", "g4", "e4"],
"g6":["e7", "e5", "h8", "f8", "h4", "f4"],
"h6":["f7", "f5", "g8", "g4"],
"a7":["c8", "c6", "b5"],
"b7":["d8", "d6", "c5", "a5"],
"c7":["e8", "a8", "e6", "a6", "d5", "b5"],
"d7":["f8", "b8", "f6", "b6", "e5", "c5"],
"e7":["g8", "c8", "g6", "c6", "f5", "d5"],
"f7":["h8", "d8", "h6", "d6", "g5", "e5"],
"g7":["e8", "e6", "h5", "f5"],
"h7":["f8", "f6", "g5"],
"a8":["c7", "b6"],
"b8":["d7", "c6", "a6"],
"c8":["e7", "a7", "d6", "b6"],
"d8":["f7", "b7", "e6", "c6"],
"e8":["g7", "c7", "f6", "d6"],
"f8":["h7", "d7", "g6", "e6"],
"g8":["e7", "h6", "f6"],
"h8":["f7", "g6"]
}

start = "a8"
doel = "h1"       # probeer ook eens "f2", "a7"

wachtrij = [start, 0]
geplaatst_in_wachtrij = [start]


gevonden = False
while not gevonden:
    vakje = wachtrij.pop(0)
    aantal_sprongen = wachtrij.pop(0)
    # print (vakje, aantal_sprongen)        # helpt om te zien wat er gebeurt
    if vakje == doel:
        gevonden = True
    else:
        for buur in buren[vakje]:
            if buur not in geplaatst_in_wachtrij:
                wachtrij.append(buur)
                wachtrij.append(aantal_sprongen + 1)
                geplaatst_in_wachtrij.append(buur)

print (f"Het vakje {doel} wordt na {aantal_sprongen} sprongen bereikt!")