4
What an interesting challenge. Learning Java8 is on my list, so here's some suggestions I have, but bear in mind that I am learning too....
First up, lets use functions for the functions we have. Starting with the safe function:
private static boolean safe(Pos p, Pos q) {
return p.x != q.x &&