Two-colour a board with walls and fixed cells

You are given an M x N board as a matrix of integers. Each cell is one of:

• 1: already painted black
• 0: already painted white
• 9: empty, still to be painted
• -1: a wall, which is never painted

Paint every empty cell black or white so that no two cells that share an edge (up, down, left, right) have the same colour. Walls take no colour and don't constrain their neighbours. Pre-painted cells keep their colour.

Implement color_grid(grid) -> list[list[int]] | None. It returns a new, fully painted board, or None if no valid painting exists. If more than one painting works, return any of them.

Constraints: 0 <= M, N <= 1000. Cell values are in {-1, 0, 1, 9}.

Example 1

input:            output:
 1  9  9           1  0  1
 9 -1  9           0 -1  0
 9  9  9           1  0  1

Example 2

input:  [[0, 9, 9, 0]]   -> None

The two white cells are three steps apart, so the cells between them can't alternate. Replace the third cell with a wall ([[0, 9, -1, 0]]) and the answer becomes [[0, 1, -1, 0]].

Then discuss: how many valid paintings exist, and what changes if diagonal neighbours also count as adjacent?

Reconstructed from the reported question; details may differ from what interviewers ask.