JP Ikäheimonen:

8 by 8: six blocks:

OOOOOOOO

OOOOOOOO

OOXOOXOO

OOOXOOOO

OOOOXOOO

OOXOOXOO

OOOOOOOO

OOOOOOOO

9 by 9: nine blocks:

OOOOOOOOO

OOOOOOOOO

OOXXOOXOO

OOOOOOXOO

OOOOXOOOO

OOXOOOOOO

OOXOOXXOO

OOOOOOOOO

OOOOOOOOO

10 by 10: twelve blocks:

OOOOOOOOOO

OOOOOXOOOO

OOXOOOOXOO

OOOOOOXOOO

OOOOOXOOXO

OXOOXOOOOO

OOOXOOOOOO

OOXOOOOXOO

OOOOXOOOOO

OOOOOOOOOO

11 by 11: thirteen blocks:

OOOOOOOOOOO

OOOOOXOOOOO

OOXOOOOOXOO

OOOOOOXOOOO

OOOXOOOOOOO

OXOOOXOOOXO

OOOOOOOXOOO

OOOOXOOOOOO

OOXOOOOOXOO

OOOOOXOOOOO

OOOOOOOOOOO

Scott Purdy

My conjecture

says that any mxn grid will require at least floor(m/3) * floor(n/3).
While

we're at it, though, I don't think it's a conjecture, I believe I can
prove it.

Beginning in one corner, section 3x3 sub-grids until no more can

be drawn. Discard the remainder (hence 11x11 is treated the same
as

9x9). Consider the central square of each of these grids.
Either it is

obstructed or the QORS can stop there. If the QORS can stop there,

one of the 8 adjacent squares is obstructed. Therefore, one of
the squares

in each 3x3 square (either the central square or one of those surrounding
it)

is obstructed. This is not to suggest that this many are sufficient,
only

necessary.

David Speyer

I can (and will below) show that the answer is between (1/7)*n^2+O(n)
and

(1/9)*n^2+O(n). Moreover, the method used to obtain the 1/7 bound lends
it

self to improvement by computer searching, although I have reason to

believe that some fairly high cases will have to be reached to improve
on

these numbers. Do you know of any improvements on these results?

OK, the 1/9 bound is easy: every square must border an obstacle. For
the

1/7 bound, suppose we have a square grid, kXk with o obstacles, which

solves the Wrap Around Queens with Roller Skates problem (a wrap around

queen with roller skates wraps around in stead of stopping when she
hits a

wall.) Suppose this grid has the additional property that the plane
is

tesselated with it, it is possible to move from any square in one grid
to

the corresponding square in any of the other grids that borders it
(trial

and error indicates that the first implies the second, but I don't
know

why.) Then o*n^2/k^2+O(n) can be achieved by tesselating this grid
over

and over. (If you like, I'll fill in details, but I think this should
be

intuitive.)

Anyways, I believe this grid, 7X7 with seven obstacles, has the required

properties:

XOOOOOO

OOXOOOO

OOOOXOO

OOOOOOX

OXOOOOO

OOOXOOO

OOOOOXO.

I'd be curious to know if you can extend these ideas, or whether you
know

the correct asymptopics.