10572 - Black & White

[seKallePuk]

Dear Friends,

May someone give some hints about solving this problem?
My idea is this:
1- First I fill boundary squares. boundary must have some consecutive '#' and then 'O'. This will improve solution speed, very much.
2- Then I try to fill left squares of board with attention to 2X2 same color squares(for forcing appreciate squares to take one of colors).
3- For bounding, I constructing a graph with squares as vertex and checking connectivity in any instance. If graph has any cut vertex I will force this square to take suitable color.

But this was not enough!!!
For an empty 7x7 grid there are 230568 differant solutions. where for a 6x6 one there are only 7736 solutions. it seems that for 8x8 it would be about sevral milions of solutions, that just counting them would be time consuming... is there any non-backtrack solution or any special bound??

Thanks in advance,
seKallePuk

[Yarin]

Yes, you have to look for a different approach, involving dynamic programming (or memoization). Counting the solutions one by one won't work.