Q Q _ Q _ _ _ _ _ Q _ _ Q _ _ _ _ Q _ _ _ Q _ _ Q Q _ Q _ _For the non blocking version, I found the following solution:
Q Q _ _ _ _ _ _ _ Q _ Q _ _ _ _ _ _ _ _ _ _ Q _ _ _ _ Q _ _ _ _ _ _ _ Q _ _ Q _ _ _ _ _ Q _ _ _ QBoth of the above solutions are optimal in the sense that solutions on smaller boards do not exist. For the Heawood graph, I found the following solutions for the blocking and nonblocking variants of the problem.
Blocking:
Q Q _ _ _ _ _ _ _ _ _ _ Q _ Q _ _ _ _ _ Q Q _ Q _ Q _ Q Q _ _ _ _ _ Q _ Q _ _ _ _ _ _ _ _ _ _ Q QNonblocking:
Q Q _ _ _ _ _ _ _ _ _ _ _ _ Q _ _ _ _ Q _ _ _ _ Q _ _ _ _ _ Q _ _ _ _ _ Q _ _ _ _ _ Q _ _ _ _ _ _ Q _ _ _ _ _ _ _ Q _ _ _ _ Q _ _ _ _ _ Q _ _ Q _ _ _ _ Q _ _ _ _The first of these is optimal in the sense that no solution on a smaller board exists. For the second, no solution on a smaller square board exists. A chess figure for the blocking solution is be found here.
Someone asked for a solution for the dodecahedral graph. Here's a blocking solution.
Q Q Q Q _ _ Q _ Q _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ Q _ _ _ _ _ _ _ Q _ _ _ _ Q _ _ _ _ _ _ _ _ Q _ _ _ _ _ Q _ _ _ _ _ Q _ _ _ _ _ _ _ _ Q _ _ _ _ _ _ _ _ _ _ _ _ Q _ _ _ _ _ _ Q _ _ Q _ _ Q Q Q Q
And here's one for the 4-cube:
_ _ Q _ Q _ _ _ _ _ Q _ Q _ _ _ Q Q _ _ _ _ _ _ _ _ _ _ _ _ Q Q Q Q _ _ _ _ _ _ _ _ _ _ _ _ Q Q _ _ _ Q _ Q _ _ _ _ _ Q _ Q _ _