This is a n-queens problem but the per "square" test is simpler. There are a couple of n-queens threads on site with code.

           Solutions found
Prob.    1st.   2nd ... last

10010    10000  10000  00010
01100    01000  01000  00100
01110    01000  01000  00010
11000    10000  01000  01000

Score      2      2      3
[download]

I don't really know how you want to score solutions, but that is not significant.

Put a marker at the start of each row, when the top marker is to be reset you've found all solutions.

When you find a 1 descend a row.

When you reach the end of a row, reset its marker to the start and continue solving from the above row.

When you find a 1 on the last row, score your solution and do what you want depending on the quality of your answer: save it, trash it, quit or continue solving.