Fill a Mini Number Square

A puzzle book prints small number squares of size n x n, where n is 4 or 6. The grid is split into boxes that are 2 rows tall and n // 2 columns wide (2x2 boxes for n = 4, 2x3 boxes for n = 6). A finished square contains each number 1..n exactly once in every row, every column and every box. Given grid (a list of lists, 0 for blank), return a completed grid that keeps every given number. Every puzzle has at least one solution; if several exist, any one is accepted.

Examples

Input:  grid = [[1, 0, 0, 0],
                [0, 0, 3, 0],
                [0, 4, 0, 0],
                [0, 0, 0, 2]]
Output: [[1, 3, 2, 4],
         [4, 2, 3, 1],
         [2, 4, 1, 3],
         [3, 1, 4, 2]]

Constraints

• n is 4 or 6, entries are 0..n, the givens do not clash

Goals

• Fill blank cells one at a time, undoing a value when a dead end is reached
• Maintain row, column and box usage sets for O(1) validity checks