Black has been defeated and the white army has won, but unfortunately the white king has been killed in the fight, and so the white queen is looking for a new mate. She is unsure whom of the knights to marry and has decided to visit them all. Afterwards she plans to see the bishop to arrange for the marriage.
Given a chessboard with the current situation, find the shortest number of moves such that the queen visits every knight and, finally, visits the bishop.
The queen visits by standing on one of the (at most) eight neighbouring squares and she does not necessarily have to move between two visits. For each move the queen can go an arbitrary number of squares in one of the eight directions (horizontal, vertical or diagonal). No move may pass through or stop at a non-empty square.
2
.......Q
...P.P..
...PNP..
..NP.P..
........
........
..B.....
........
B.P.....
..P.....
PPP..N..
........
........
.N...Q..
........
........
Scenario #1:
h8h2e5d4b2
Scenario #2:
impossible