4
$\begingroup$

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:

enter image description here

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: enter image description here

However, performing the necessary swaps is not always easy, and things might get tricky. Consider the following case: enter image description here

Moreover, there is also a case where the grid has no solution, similar to the case mentioned previously. See the illustration below: enter image description here

Any ideas that might be helpful to solve this? Any help would be very much appreciated. If it is impossible to solve such a puzzle in polynomial time, is there any possible NP-complete problem that is reduced to this puzzle?

$\endgroup$
8
  • $\begingroup$ I think there is an algorithm. If there is no choice (after applying the rules internal to the region) for both endpoints in a region, we can deal with it separately. If a region has a choice for only 1 endpoint or at least 4 options for both its endpoints, we can always find a satisfying option after fixing the neighbors. So the only cases of interest are for 2 or 3 digits to place in 2 endpoints of a region. These cases both create a "chain" of regions of this type, that has ends in a region that either forces or frees a choice in the chain. Starting solving the chain at a forcing end. $\endgroup$
    – Discrete lizard
    Feb 3, 2023 at 10:02
  • $\begingroup$ @Discretelizard How do you justify your claim that "we can always find a satisfying option after fixing the neighbors"? And what do you mean by "chain" of regions? $\endgroup$
    – Iqazra
    Feb 3, 2023 at 10:39
  • 1
    $\begingroup$ What I'd call a chain is not as easy as I thought. Maybe the following is better: every region has a set of possible pairs of numbers that may appear on its endpoints, given the internal rules of the region. The same goes for every list of adjacent regions. It is possible to compute the possible pairs based on the lists of two lists of adjacent regions. So, we can merge them one by one in polynomial time, and in the end determine whether the entire puzzle has valid pairs. This can be made more efficient by noting we can store at most a constant number of pairs, but is still polynomial without. $\endgroup$
    – Discrete lizard
    Feb 3, 2023 at 12:28
  • $\begingroup$ @Iqazra Is each cell in exactly one group? $\endgroup$
    – John L.
    Feb 4, 2023 at 12:43
  • 2
    $\begingroup$ @Inteurce The order of merging doesn't matter for correctness, though you may be able to simplify things by choosing a specific order. The main point of the idea is that we don't make a choice when there are multiple choice locally, but instead maintain a list of the options we have at the endpoints of a sequence of regions. That said, John L.'s answer has an algorithm based on a similar idea that is a bit simpler than what I had in mind, so I think its better to look at that answer instead of my comments. $\endgroup$
    – Discrete lizard
    Feb 4, 2023 at 18:54

1 Answer 1

2
$\begingroup$

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$.

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

  2. 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$.

  3. 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.

  4. 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.
    1. If $|I_2|=1$, put the only number in $I_2$ in the only empty cell.
    2. If $|C_1|=1$ and the only number in $C_1$ is in the leftmost cell, return "NO".
    3. 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).
    4. If the rightmost cell is empty, let $C_2$ be $I_2$.
    5. Else the rightmost cell is not empty. Let $C_2$ be the set of the only number that is in the rightmost cell.
  5. Repeat step 4 above with each next region, replacing region $1$ with the current region and replacing region $2$ with the next region.

  6. 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.

$\endgroup$
4
  • $\begingroup$ To clarify, does $C_i$ represent the set of possible numbers that can be filled in the rightmost cell of region $i$? Also, could you specify the region you are referring to when mentioning the leftmost or rightmost cell by including the region number in your answer? $\endgroup$
    – Inteurce
    Feb 4, 2023 at 16:38
  • 1
    $\begingroup$ @Inteurce I just updated my answer. $\endgroup$
    – John L.
    Feb 4, 2023 at 18:12
  • $\begingroup$ Got it, thank you! $\endgroup$
    – Inteurce
    Feb 6, 2023 at 18:07
  • $\begingroup$ You are welcome! $\endgroup$
    – John L.
    Feb 6, 2023 at 18:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.