Problem 1595

1. Divide the Grid: Divide the $6 \times 6$ grid into nine $2 \times 2$ square grids. Each $2 \times 2$ square can have at most one black cell to ensure no two black cells share a corner or an edge. Therefore, each $2 \times 2$ square must have exactly one black cell.

2. Positioning Black Cells: Describe the position of the black cell in each $2 \times 2$ square as being on the left or right side and on the upper or lower half. Denote these positions as $L$ or $R$ and $U$ or $D$ respectively.

3. Row and Column Constraints: The condition that no two black cells share a corner or an edge implies that:
- Two consecutive black cells in a row cannot be $RL$.
- Two consecutive black cells in a column cannot be $DU$.

4. Possible Configurations: For a row, the only valid configurations are $LLL$, $LLR$, $LRR$, or $RRR$. Similarly, for a column, the valid configurations are $UUU$, $UUD$, $UDD$, or $DDD$. Since there are 3 rows and 3 columns, the total number of configurations is:
$$4^3 \times 4^3 = 4^6 = 4096$$

5. Subtract Invalid Configurations: Not all of these configurations are valid. We need to subtract the cases where one of the corners of the middle $2 \times 2$ square is shared by two black cells. We use the Principle of Inclusion-Exclusion (PIE) to account for these cases.

6. Case Analysis:
- Single Corner Shared: Consider the top-left corner of the middle $2 \times 2$ square being shared. There are two ways this can happen:
1. One black cell in the top-left $2 \times 2$ square shares the corner with a black cell in the center $2 \times 2$ square. The top row must be $RRR$ because the first one is on the right. In the second row, we have $LL \_$. Since the middle square is $L$, the first one must also be $L$. The third one can either be $L$ or $R$. In the third row, we can have any of the 4 possibilities, so there are $2 \times 4 = 8$ ways to decide the left/right positions. Similarly, there are $8$ ways to decide the up/down positions, so there are $8^2 = 64$ ways to color the grid.
2. One black cell in the middle-left $2 \times 2$ square shares the corner with a black cell in the middle-top $2 \times 2$ square. Similarly, there are $8^2 = 64$ ways to color the grid in this case.

- Total for Single Corner: Since there are 4 corners, the total number of colorings that have a shared corner is:
$$4 \times (64 + 64) = 512$$

7. Double Corner Shared: Subtract the number of colorings where two of the corners are shared. We can either have the top-right and bottom-left corners shared or the top-left and bottom-right corners shared. WLOG, consider the top-left and bottom-right corners shared. There are 2 ways to choose which squares have black cells' corners shared and $2^2 = 4$ ways to color the rest of the grid. Therefore, there are:
$$2 \times 2 \times 2^2 = 16$$

8. Final Calculation: Using PIE, the total number of valid configurations is:
$$4096 - 512 + 16 = 3600$$