No recursion or brute force would needed, if you could guess some regularity. Of course this requires some thoughts from you ;)

My main() contains only these lines but input:

if(canWinNow('X') > 0 || existsMagicCell('X')) CROSSESWIN
else if(canWinNow('O') > 1) OUTHSWIN
else DRAW

What canWinNow() does you may guess yourself, and existsMagicCell() contains about 10 lines and is not recursive.

Who wants to find out my algo write a-zakh [at] yandex.ru