I need to make some pseudocode for my class and I am stumped on how to do this question:
There is an NxN grid (1 < N < 1300). You have to place exactly 2 items in every 2x2 subgrid (Assume that there is a solution for every case). Print every solution.
Input Example: 3
Output Example:
111
000
111
000
111
000
101
010
101
010
101
010
etc... (where 0 is an empty space and 1 is taken)
Bonus: If every square in the grid was weighted, explain how you can find the best solution.
A simple method to generate some solutions is to pick a first row arbitrarily and then fill out each subsequent row by taking one minus the previous row. We can also do this with columns.
It turns out that every valid matrix is generated by one of these two variants (note that the two perfect checkerboards are generated by both). The reason is that if the first row has adjacent zeros or adjacent ones, then the entries below it are forced, these force the rest of the row to be one minus the previous row, and in turn the rest of the rows are forced. Ditto columns. If neither the first row nor the first column has a duplicate, then we have one of the two checkerboards.
Maximizing isn't too hard. For alternating rows, decide for each column whether the even rows or the odd rows are more valuable. For alternating columns, decide for each row whether the even columns or the odd columns are more valuable. Take the best of these two solutions.
