Finding the least number of dots to add into a 10x10 grid

Question

I have a 10x10 grid where are some dots.

What is the least number of dots that I need to add in order to

1. have 3 dots in every row and column
2. have odd number of dots in every row and column
3. have even number of dots in every row and odd number of dots in every column
4. have a dot in two of every dotted square's neighbour squares

(neighbour squares are squares that have the same side, each non-border squares have 4 neighbour squares)

I'm sure these questions can be answered without brute-forcing but how?

Thanks in advance!

Answer 1

For parts 1-3 I used a greedy algorithm favoring rows over columns. This is a little bit different than using brute force because rather than checking all possible legal arrangement of dots, I choose a strategy that I hoped would work(namely a greedy strategy). This is a common thing to try, because greedy algorithms tend to be easy to execute and are great for establishing an upper bound(if the algorithm halts on a solution.) In these cases, the lower bound was also easy to establish once I saw the finished products, and fortunately they matched the upper bound given by my greedy algorithm.

I should mention that my greedy algorithm for part 2 technically halted on a non-solution since once I added the third dot every row was odd, so I was unable to add a fourth dot without messing that up. Fortunately, it wasn't hard to figure out that I only needed two more dots and if I put them in the same row, it will preserve the parity.

Note: there are plenty of situations where greedy algorithms will not yield the optimal solution or even a solution, but due to their ease of use, they are a natural tool to try when you don't have other strategies in mind.

(1)

(2)

(3)

For (1) we know this is best because there are 30 total dots. For (2) this is best because there were five columns of even parity, so minimally five dots were needed. For (3) this is best because there were seven rows of odd parity, so we know at least seven dots needed to be added.

For part (4) if I understand your constraints correctly, I believe that the following is a minimal solution with the addition of 24 dots. I leave this without proof since it would be tedious, but the result relies on the fact that each dot must be part of either a cycle or a path between two cycles.