Possibly Tractable Variation of Suguru Puzzles

I'm currently investigating the computational complexity of a modified one-dimensional Suguru puzzle. The general Suguru puzzles were recently proven to be NP-complete (see here). My investigation considers a modified one-dimensional Suguru puzzle played in a $1 \times N$ grid of cells. These cells are grouped into one or more regions of consecutive cells. Say there are $k$ regions, and let us label the region from left to right with $1,2,\dots,k$. Let us denote $s_i$ as the size of the region $i$ (i.e., the number of cells in such a region). Initially, a cell is either empty or filled with a number ranging from 1 to $s_r$, where $r$ is the region label where the cell belongs. Our goal is to fill all empty cells with numbers, such that region $i$ is filled with distinct numbers $1, 2, \dots s_i$, and no two adjacent cells are filled with the same number. See the illustration below for example:

I have conducted some investigations. If all the cells in the grid are initially empty, then this problem can be easily solved in $O(N)$, where $N$ is the number of cells in the grid. The idea is to fill each region starting from the left-most cell with increasing numbers (starting from $1$). Then, we check for any adjacent cells with the same number and perform necessary swaps. I also found a particular case for this condition where we have no solution, that is, if there are two regions labeled with $L$ and $R$, such that $L < R$, $s_L = s_R = 1$, and all regions between $L$ and $R$ (if any) are of size $2$.

If some cells are initially filled with numbers, I guess that finding a solution in polynomial time may be possible, but I have yet to find an algorithm for this case. My initial approach was to fill each region starting from the left-most cell using only available numbers, starting from the minimum available number (MEX), and do necessary swaps. See the illustration below for example:

However, performing the necessary swaps is not always easy, and things might get

There is a simple linear-time algorithm that determines whether it is possible or find a possible way.
The algorithm for the decision problem

The idea is to collect the choices at the rightmost cell of each region, scanning regions from the leftmost region, i.e. region $1$ to the rightmost region, i.e. region $k$.

-
Check whether the initial configuration is valid, i.e., no two adjacent cells are filled with the same number. If not, return "NO".

-
Let $I_i$ be the set of numbers from $1$ to $s_i$ excluding the numbers given in the region $i$. $I_i$ is the set of initial choices for each empty cell in region $i$. $|I_i|$ is the number of empty cells in region $i$.

-
Consider region $1$. If its rightmost cell is empty, let $C_1$ be $I_1$. Otherwise, let $C_1$ be the set of the only number that is in the rightmost cell.

-
Consider region $2$. All cells mentioned in this step are in region $2$.

We will construct $C_2$ as the set of all possible numbers at the rightmost cell when we have filled regions up to region $2$ as required, i.e.,

• the numbers in region 2 are $1,2,\cdots,s_2$ and

• there is a number in $C_1$ that is not the number in the leftmost cell.

• If $|I_2|=1$, put the only number in $I_2$ in the only empty cell.

• If $|C_1|=1$ and the only number in $C_1$ is in the leftmost cell, return "NO".

• If $|C_1|=1$ and $|I_2|=2$:

Initialize $C_2$ as an empty set. There are two ways to put the two numbers in $I_2$ in the two empty cells. For each way, check if the number in the leftmost cell is the only number in $C_1$. If not, add the number in the rightmost cell to $C_2$.

Skip step $4$ and $5$ right below (i.e., outer step 4 is done).

• If the rightmost cell is empty, let $C_2$ be $I_2$.

• Else the rightmost cell is not empty. Let $C_2$ be the set of the only number that is in the rightmost cell.

-
Repeat step 4 above with each next region, replacing region $1$ with the current region and replacing region $2$ with the next region.

-
Return "YES".

Algorithm analysis

Note that whenever $C_i$ has more than one element, we don't even have to construct it. All we need is to remember it has more than one element.

The time completely of the algorithm is $O(N)$ or, if implemented properly, about $O(n)$ where $n$ is the number of numbers that appear in the input.

If we add some bookkeeping to the algorithm, we can either find a way to fill the numbers as wanted or conclude there is no such way in linear time as well.

StackExchange Computer Science Q#157283, answer score: 2