Light Up

Light Up is a pencil puzzle. Your job here is not to play Light Up, but to judge whether a player's solution is correct.

The game is played on a square grid. Some cells are blocked, and some blocked cells have a number from $0$ to $4$. The player places light bulbs in open cells. Each light bulb lights all open cells above, below, left, and right (but not diagonally) until the light reaches the edge of the grid or a blocked cell. The player must place light bulbs so that:

• Every open cell is lit.
• No two light bulbs shine on each other.
• Any blocked cell with a number must have exactly that many light bulbs immediately adjacent above, below, left, or right. Diagonals do not count.

The following is an example grid with its solution:

Given a grid with light bulbs placed, determine whether it is a solution. If a grid has no open cells and violates no other constraints, it is trivially solved.

The first line of input contains a single integer $n$ ($1≤n≤30$), the number of rows and columns in the grid.

Each of the next $n$ lines contains exactly $n$ characters from the set {., X, ?, 0, 1, 2, 3, 4}. . is an open cell, X is a blocked cell, ? is a light bulb, and the digits 0 through 4 are blocked cells with a constraint on the number of adjacent light bulbs.

Output a single integer: $1$ if the input is a valid solution, and $0$ otherwise.