Up to 9x9 it's nice that you can do it with the first row all one color (view this in fixed-width font): ......... .X.X.X.X. ..XX..XX. X...XXX.. .X.XX.X.X XX....XXX X.X.XX.X. X.XX....X .XX..XX.X So even my stupid computer program can solve it essentially immediately. Starting with 10x10, the lexicographically first solution is no longer with a monochromatic first row: .........X .X.X.X.X.. .XX..XX..X ..XXX...X. .XX.XX.X.X X.X...XXX. .X.XX.X.X. X..X.X..X. XXX....X.. ....XXXXX. In general, it seems up to 9x9 there's a very large proportion of squares that work, and 10x10 it starts to go down, and by 11x11 there's a very small proportion of squares that work. Rather than looking for lexicographically first, I had it look more at random (but keeping track of the tree, just ordering randomly, so it is sure to check all possibilities in looking for a solution) and in about a minute it found OOOXOOOXOXX XOXOOXOXXOX OOXOXXOOXOX OXOOOXXOXOO XXXXOOOOXXO XOOXXOXOOXX XXOOOOXXXXO OXOXXOOXOOO XXXOOXOOOXX OOXOXXOXXXO XXOOOXXXOXX for the 11 by 11 case. (by contrast, finding the lexicographically first 10x10 took it 3 minutes). I'll run it on 15x15 and see if it finds a solution or not ... and meanwhile look for a proof by hand as well. --Joshua Zucker