# Connect 4 - SAT

My question is about how the Hasbro game Connect4 can be viewed as a SAT problem.

My initial guess is that it would actually be QSAT, and that the 'problem' would be something along the lines of: "Is there a set of black/white turns such that X will happen" where X is some condition on the board.

I guess you could even specify that X has to be reached after a certain number of turns n.

Any ideas on encoding connect4 as a Q/SAT problem or any ideas on interesting questions that can be asked about it are welcome. Thank you muchly!

For reference if necessary: Thesis about Connect4 from AI perspective

-
SAT like the test high school students take? Didn't seem to come up when I took it –  ShawnD Mar 7 '12 at 23:22
–  deoxygerbe Mar 7 '12 at 23:33
The problem of deciding who's the winner (under optimal play) is an instance of TQBF. –  Yuval Filmus Mar 8 '12 at 3:29
@YuvalFilmus That's not QSAT? –  NickHalden Mar 8 '12 at 4:18
–  Kyle Jones Mar 8 '12 at 7:15