Minimum number of blocked squares to ensure a draw in a generically sized tic-tac-toe grid

Question

There is a Japanese puzzle called marupeke which involves an $x$ by $y$ sized grid, where the objective is to place a $O$ or $X$ on every square so that there is not a "chain" of length 3.

Some tiles in the grid may be blocked out beforehand where a $O$ or $X$ can not be placed.

Here is an example of a solved grid:

My question is if there is a way to determine the minimum number of blocked squares needed to solve an $x$ by $y$ grid without brute forcing every solution, or at least a way of generating solvable grids for any size in a short amount of time.

Answer 1

You can always fill any $x \times y$ grid with X's and O's without having 3 in a row. Extend the following pattern to fill the grid:

XXOOXXOOXXOOXXOO...
OOXXOOXXOOXXOOXX...
XXOOXXOOXXOOXXOO...
OOXXOOXXOOXXOOXX...
XXOOXXOOXXOOXXOO...
OOXXOOXXOOXXOOXX...
...

That's a repeated tiling of the $2 \times 4$ pattern:

XXOO
OOXX

So we see that any marupeke puzzle is solvable when we shade some blocked squares, but before we write down any X's and O's. Usually you get some of those pre-filled for you, with the aim of creating a puzzle with a unique solution: that's the hard part.

For a (non-algorithmic) guide to the hard part, see this Puzzling StackExchange post.