There is a 5×5 grid in front of you. You have to fill 25 squares with only 0 and 1.

But, every pair of neighboring squares (that is not diagonally adjacent) needs to have a product equal to 0.

How many possible grids are there?

I also wrote a branching tree to find the grid solutions, but I came up with a different total number. My program found 55,447 solutions as opposed to Charlie's 37,869. I have not resolved the discrepancy. I list all 55,447

here and the program

here. My "each 1000th grid" marched along through the grid square more slowly than Charlie's as you might expect if it were finding more.

In case it helps find the source of the discrepancy, I made a histogram of the number of solutions with 0, 1, 2, ...,13 "ones" present:

0 1 2 3 4 5 6 7 8 9 10 11 12 13

------------------------------------------------------------------------------

1 25 260 1474 5024 10741 14650 12798 7157 2578 618 106 14 1

*E.g. the values for 1 (25) and 12 (14) look right. *

*Edited on ***April 30, 2019, 1:40 am**