INTERNATIONAL JOURNAL OF COMPUTING SCIENCE AND APPLIED MATHEMATICS VOL.
NO.
MARCH 2024
Elementary Algorithmic Methods for Solving Suguru Puzzles Butrahandisya.
Muhammad Arzaki, and Gia Septiana Wulandari AbstractAiWe discuss elementary algorithmic aspects of the Suguru puzzleAia single-player paper-and-pencil puzzle introduced in 2001 and confirmed NP-complete by Robert et al.
We propose a backtracking algorithm with pruning optimizations for solving an m y n Suguru puzzles containing R regions and H hint cells in O(R A .
n Oe H .
!) time.
Despite this factorial asymptotic upper bound, a C implementation of our proposed algorithm successfully solved all Suguru instances with no more than 100 cells using a personal computer in less 5 seconds.
We also prove that any Suguru instance of size m y n with either m = 1 or n = 1 can be solved in linear time regarding of the puzzle size.
Finally, we provide an upper bound for the number of solutions to such tractable instances.
Index TermsAiasymptotic analysis, backtracking.
Suguru puzzle, tractable subproblems I NTRODUCTION uguru .
lso known as Nanbaburokk.
is a single-player pencil-and-paper puzzle invented by Naoki Inaba, a prominent Japanese puzzle designer.
It first appeared in 2001 .
and was recently proven NP-complete by Robert et al.
in 2022 .
Like the famous Sudoku, the player must fill the empty cells in a rectangular grid, satisfying some puzzle rules.
The game is played on an m y n grid partitioned into regions.
A region is a collection of orthogonally connected cells.
The goal is to fill all cells with numbers such that:
no two cells in a region can contain the same number.
no two adjacent cells, either orthogonally or diagonally, can contain the same number.
a number in a cell must be between 1 and the size of the region it belongs to, where the size of a region is defined as the number of cells in it.
Puzzles have long been regarded as captivating mental challenges that have entertained and engaged individuals throughout history.
They provide leisure and diversion opportunities and stimulate cognitive skills such as critical thinking and problem-solving .
Moreover, theoretical aspects of puzzles have garnered substantial interest from the scientific community in the last twenty years owing to their profound links with crucial problems in mathematics and the theory of computation, resulting in extensive investigations into their mathematical and computational aspects .
Ae.
for extensive Butrahandisya was an undergraduate student at Computing Laboratory.
School of Computing.
Telkom University.
Bandung 40257.
Indonesia, email butrahandisya@gmail.
Muhammad Atzaki and Gia Septiana Wulandari are with Computing Laboratory.
Telkom University.
Bandung Indonesia, arzaki@telkomuniversity.
giaseptiana@telkomuniversity.
Manuscript received June 20, 2023.
accepted March 21, 2024.
Furthermore, a variety of paper-and-pencilbased games have been confirmed NP-complete, including but not limited to .
n chronological orde.
: Nonogram .
Sudoku .
Nurikabe .
Heyawake .
Hashiwokakero .
Kurodoko .
Shikaku and Ripple Effect .
Yosenabe .
Fillmat .
Dosun-Fuwari .
Tatamibari .
Kurotto and Juosan .
Yin-Yang .
Tilepaint .
, and Suguru .
The NP-completeness of Suguru puzzles implies the existence of a polynomial-time verification procedure for checking whether an arbitrary configuration is a solution to a Suguru instance.
However, solving a Suguru puzzle remains an exponential-time task because no known polynomial-time algorithm exists for any NP-complete problem.
Moreover, formal algorithmic investigation for solving Suguru puzzles has been relatively limited as it has only recently proven NPcomplete.
Investigations on elementary algorithmic methods such as the exhaustive search and prune-and-searchAiwhich utilizes a similar approach to the methods used in this paperAi have been carried out on puzzles such as Yin-Yang .
Tatamibari .
Tilepaint .
Path Puzzles .
, and Juosan Puzzles .
More advanced techniques are also available for solving NP-complete puzzles, such as SAT solvers .
, .
and the deep learning method .
This paper discusses an elementary approach, the backtracking method, enhanced with pruning optimizations.
demonstrate that this approach can solve any Suguru puzzle, with the caveat that the solving time increases in factorial factor in terms of the puzzle size and the number of hints.
addition to this, we delve into the exploration of a tractable variant of the Suguru puzzle.
Investigating such variants of NP-complete problems holds significant importance in computational complexity theory .
The remainder of this paper is structured as follows.
Section II introduces some definitions and notations regarding Suguru puzzlesAo data structure and mathematical representation, as well as some relevant theoretical results.
Section i presents an algorithm that verifies a solution to a Suguru puzzle of size m y n in O.
Section IV discusses our proposed backtracking algorithmAiwhich incorporates pruning optimizationsAifor solving arbitrary m y n Suguru puzzles.
Specifically, we prove that our backtracking algorithm can solve an arbitrary myn Suguru instance with R regions and H hint cells in O(RA.
nOeH .
!) time.
Section V investigates a tractable variant of the puzzle.
We show that any m y n Suguru instances where m = 1 or n = 1 are solvable in linear Nevertheless, we argue that discovering all solutions to a INTERNATIONAL JOURNAL OF COMPUTING SCIENCE AND APPLIED MATHEMATICS VOL.
NO.
MARCH 2024
tractable Suguru puzzle may require a non-polynomial number of computational steps.
The experimental results to evaluate our proposed algorithmAos practical performance are discussed in Section VI.
Lastly, the important results of this paper are summarized and concluded in Section VII.
II.
P RELIMINARIES
All arrays in this paper use one-based indexing and are written using uppercase letters.
The notation Ai for a onedimensional array A of length or size n denotes the i-th entry of array A where 1 O i O n.
The notation Ai,j for a twodimensional array A of m rows and n columns denotes the entry in i-th row and j-th column of array A where 1 O i O m and 1 O j O n.
Definition and Representation of Suguru Puzzles Before delving into the technical details and algorithms related to the Suguru puzzle, we introduce the definition of Suguru instance, configuration, and solution in Definition 1.
Moreover.
Fig.
1a and Fig.
1b depict a Suguru instance and one of its corresponding solutions.
Definition 1.
A Suguru instance of size m y n is defined as a grid of m rows and n columns containing mn cells divided into one or more regions.
A region is a collection of one or more orthogonally connected cells.
The size of a region is the number of cells within such a region.
Initially, each cell may either be empty or contain an integer between 1 and s .
, where s is the size of the region it belongs to.
configuration of a Suguru instance is obtained by filling all of its empty cells with non-negative integers.
A solution to a Suguru instance is a configuration that satisfies the following rules of Suguru:
no two cells in the same region can contain the same .
no two adjacent cells, either orthogonally or diagonally, can contain the same integer.
all cells must be filled with an integer between one and the size of the region it belongs to.
In this paper, we formally represent a Suguru instance of size m y n using a two-dimensional array G of the same size such that Gi,j = .
i,j , ri,j ) where hi,j and ri,j respectively denote the hint for the cell .
, .
and the region label to which the cell .
, .
The value ri,j is a positive integer between 1 and R .
, where R is the number of regions in the corresponding instance.
The regions are numbered using the row-major order format, i.
, the first region in the first row is labeled with one while the last region visited is labeled with The value hi,j is a non-negative integer between 0 and sri,j where sri,j denotes the size of the region labeled ri,j .
Furthermore, hi,j = 0 if and only if the cell .
, .
is empty.
, .
that initially contains a number .
r mathematically hi,j = .
is called a hint cell.
From Definition 1, we know that a Suguru configuration C corresponding to a Suguru instance G is obtained by imposing the value of hi,j to a positive integer for every cell .
, .
, that is, we need to fill every empty cell with a number satisfying the constraint above.
An instance of a Suguru .
An example of a solution to the instance in Fig.
Array G for the Suguru instance in Fig.
Representation of a solution to the instance in Fig.
1a obtained by altering 0 to a positive integer in array G in Fig.
Fig.
1: An example of a Suguru instance (Fig.
, its solution (Fig.
, and data structure representations for Suguru instance and solution (Fig.
1c and Fig.
We provide an example of a Suguru instance, its solution, and its corresponding data structure formalization in Fig.
Using this convention, the Suguru instance and solution in Fig.
1a and Fig.
1b are respectively represented formally as two-dimensional arrays of pairs in Fig.
1c and Fig.
Summary of the NP-Completeness of Suguru Puzzles Suguru puzzles are recently proven NP-complete by Robert et al.
in 2022 .
The authors demonstrated the NPcompleteness of these puzzles by establishing a polynomialtime reduction from the Planar Circuit SAT problem to the Suguru puzzle.
According to Robert et al.
, the Planar Circuit SAT problem is similar to the Planar SAT problem, shown NPcomplete by Lichtenstein .
The Planar SAT problem was proven NP-complete by the reduction from the 3-Quantified Boolean Formula problem, similar to the 3-SAT problem.
In the Planar Circuit SAT problem, a planar logical circuit is given and connected solely to the logic gates responsible for computing a Boolean formula.
A planar circuit is a Boolean circuit that can be drawn on a plane such that none of its wires Robert et al.
construct a polynomial-time reduction using constant-sized partial instances of Suguru puzzles, known as gadgets, for representing objects in the Planar Circuit SAT problem.
The summary of the gadgetsAo constructions is described as follows:
The construction of types of cells.
Four types of cells are used to formally define the gadgets: input, output, propagated, and independent cells.
These cells are explained in .
Fig.
The construction of true and false gadgets.
The true and false gadgets are constructed using a region of size 1 y 2 or 2 y 1 in a Suguru instance.
It is important to note that the orientation of the cells determines whether the gadget INTERNATIONAL JOURNAL OF COMPUTING SCIENCE AND APPLIED MATHEMATICS VOL.
NO.
MARCH 2024
is either a true or false gadget.
For further illustration of these gadgets, see .
Fig.
Fig.
The construction of the not gadget.
The not gadget is created using a Suguru instance of size 5y11.
This gadget takes an input and produces an output.
The not gadget is illustrated in .
Fig.
The construction of the or and and gadgets.
The or and and gadgets are constructed using a Suguru instance of size 5 y 11.
These gadgets take two inputs and generate an output.
Although the or and and gadgets are alike, they differ in some of the predetermined cells.
Pictorial representations of these gadgets are available in .
Fig.
Fig.
The construction of split and split stop gadgets.
The split gadget is created using a Suguru instance of size 5 y 22 and propagates its input to two outputs of identical values .
rue or fals.
In contrast to the split gadget, the split stop gadget propagates its input to just one of the outputs.
The split and split stop gadgets are illustrated in .
Fig.
Fig.
, respectively.
The construction of the horizontal and vertical isolator and connector.
Robert et al.
introduced horizontal and vertical isolators and connectors to connect all of the logical gadgets.
The horizontal isolator, horizontal connector, vertical isolator, and vertical connector are respectively illustrated in .
Fig.
, .
Fig.
, .
Fig.
, and .
Fig.
According to Robert et al.
, it is possible to transform any Planar Circuit SAT instance into a Suguru instance using the gadgets above.
Furthermore, if the planar circuit has a maximum of x logical gadgets in a row of its layout and a maximum of y logical gadgets in a column, the corresponding Suguru instance constructed contains x y 22 rows and y y 15 Oe 10 columns.
Thus, the Suguru instance constructed is polynomially proportional to the input size.
To determine whether a formula in the Planar Circuit SAT instance is satisfiable, we set the output in the corresponding Suguru instance to true.
The formula is satisfiable if a solution to the Suguru instance exists.
Consequently, the polynomial-time reduction is established.
Moreover, since the compliance of Suguru configuration to the puzzleAos rules can be carried out in polynomial time, they belong to the NP-complete class.
Section i of this paper also discusses a polynomial-time verification algorithm that can check the compliance of an arbitrary Suguru configuration to the puzzleAos rules.
Grid S1 of size 2 y 2.
Grid S2 of size 2 y 2.
Grid G of size 3 y 3.
Fig.
2: Grid S1 in Fig.
2a is a subgrid of grid G in Fig.
while Grid S2 in Fig.
2b is not.
Definition 3.
A region is completely inside a subgrid if all its cells are contained within the subgrid.
In the following theorem, we prove an elementary property that a Suguru instance with a 2 y 2 subgrid containing more than one complete region has no solution.
Theorem 1.
If G is a Suguru instance of size m y n that contains at least one 2 y 2 subgrid with more than one complete region, then G has no solution.
Proof.
Suppose G is a Suguru instance that contains a 2 y 2 subgrid S consisting of more than one complete region, then at least two cells within S must contain the integer 1.
Since all cells in S are adjacent to each other, this results in two adjacent cells having the same number, which violates one of the Suguru puzzleAos rules.
V ERIFYING S UGURU S OLUTIONS IN P OLYNOMIAL
T IME
This section outlines an algorithm for verifying whether a configuration constitutes a solution to a Suguru instance.
The algorithm requires a two-dimensional array of pairs of integers denoting the configuration of a particular Suguru instance.
The Non-existence of a Particular 2 y 2 Subgrid Determining the Size of Each Region In a Suguru instance, it is possible to have a 2 y 2 subgrid that contains more than one complete region.
To formally illustrate this condition, we first discuss some collections of cells in Definition 2 and Definition 3.
Fig.
2 illustrates an example of a grid that is a subgrid of another larger grid and a grid that is not.
Suppose we consider a Suguru configuration C containing R regions where each cell .
, .
consists of a pair .
i,j , ri,j ).
We define an array S = .
1 , s2 , .
, sR ] where sk denotes the size of region k .
O k O R).
Here, sk = |{.
, .
: ri,j = .
We can determine the array S by traversing all mn cells in row-major order and increment the value sk if and only if ri,j = k for a cell .
, .
Thus, the asymptotic upper bound of the running time for determining the array S is O.
Moreover, the process to construct S requires O(R) space where R O mn.
Definition 2.
A contiguous orthogonal collection of cells in grid S is a subgrid of G if there exists S in G and the region for each cell in S is identical to the region for each cell in G.
INTERNATIONAL JOURNAL OF COMPUTING SCIENCE AND APPLIED MATHEMATICS VOL.
NO.
MARCH 2024
Computing the Number of Cells Containing a Particular Number within a Region To check if every cell .
, .
has a unique value within a particular region k .
O k O R), we use a list CV of Aucell valuesAy of size R whose k-th component is a list of size sk .
The notation CV, denotes the number of cells .
, .
such that hi,j = and ri,j = , that is, the number of cells in region filled with the number .
We determine CV by traversing all mn cells in row-major order and increment the value CV, if and only if = ri,j and = hi,j for a cell .
, .
The process to construct CV requires O.
time and O.
Validating the Compliance of Cell Values within a Region To verify if the value of hi,j in a given cell .
, .
complies with the regionAos size, we check the condition 1 O hi,j O sk , where k corresponds to the region ri,j that the cell belongs to.
The validation process for a cell takes a constant O.
Validating the Uniqueness of Cell Values within a Region To validate if the value of hi,j in a given cell .
, .
is unique within its corresponding region, we need to ensure that it satisfies the condition CV, = 1 where and corresponds to the region ri,j and the value hi,j , respectively.
The validation process for a cell takes constant O.
Validating the Compliance of Adjacent Cell Values This process ensures that the value of hiA ,j A of any cell .
A , j A ) that is adjacent to the cell .
, .
differs from hi,j .
Mathematically it checks that if .
Oe iA | O 1 and .
Oe j A | O 1 for any cell .
A , j A ) = .
, .
, then hi,j = hiA ,j A .
The validation process for a cell is constant, i.
, since a cell can only have at most eight adjacent cells.
Main Verification Process To verify whether a configuration is a solution to a Suguru instance, we initially perform the computations outlined in Section i-A and Section i-B, which have a time complexity of O.
Subsequently, we verify that all cell values satisfy the conditions specified in Section i-C.
Section i-D, and Section i-E.
This process has a time complexity of O.
, since we need to check for mn cells, and for every cell, each validation step has a constant time complexity of O.
This demonstrates that verifying whether a Suguru configuration is also a solution can be done in polynomial time.
Additionally, the space complexity of this process is O.
as the size of the list CV is proportional to mn.
IV.
A BACKTRACKING A PPROACH FOR S OLVING S UGURU
P UZZLES
Backtracking is an algorithmic strategy used to explore all or some possible solutions to a problem by incrementally building partial solutions and testing if they satisfy the problemAos constraints.
The method abandons .
r prune.
a partial solution when it determines that it cannot lead to a valid solution within the constraints.
This approach involves making a series of choices and using recursion to traverse the state space tree until a solution is found or all possibilities are exhausted .
Backtracking is chosen as our approach for solving Suguru puzzles due to its efficiency compared to other elementary methods, such as the exhaustive search approach .
Ae.
for such argument.
To solve the Suguru puzzle using a backtracking approach, we initially compute the arrays S of region sizes and CV of cell values as explained in Section i-A and Section i-B.
We achieve this by incrementing sk where k = ri,j for each cell .
, .
and CV, for each hint cell .
, .
, where = ri,j and = hi,j .
Recall that CV can be considered as twodimensional list of size R whose k-th component is a list of size sk such that CV, is the number of cells in region whose hints are equal to .
These computations yield the necessary information to construct a list of length R containing sets of integers denoted by N.
Each set N .
O O R) within N consists of numbers .
O O s ) that do not appear in any of the initial hint cells within region where 1 O O R.
In other words.
N contains a set of possible values for every empty cell in the region .
Mathematically.
N = { : 1 O O s .
CV, = .
Subsequently, the algorithm follows these steps:
We fill the cells in row-major order.
For each hint cell .
, .
, we leave it unchanged.
However, for each empty cell .
, .
, we attempt to fill it with the values from the set N corresponding to region = ri,j .
We iterate through the elements of N in increasing order.
As we fill the cell .
, .
with a value , we simultaneously increment CV, .
After assigning a value to cell .
, .
, we evaluate whether backtracking is necessary based on the following .
any of the adjacent cells to cell .
, .
have the same value as .
there exists another cell in the same region ri,j with the value .
CV, > 1 where = ri,j ).
If any of the above conditions are met, we backtrack by first undoing the value assignment of cell .
, .
and simultaneously decrementing CV, where = ri,j .
then proceed to try other possible values for cell .
, .
However, if no other values are available to try for cell .
, .
, we continue backtracking further, moving back to the previous cell.
Once all cells have been successfully filled, a solution has been found, and the algorithm terminates.
If we backtrack after trying all possible values for cell .
, .
, or if we backtrack to the hint cell .
, .
, we conclude that the instance has no solution.
To provide a more elaborate description of the algorithm, we introduce two auxiliary functions: the function N EXT C ELL.
, .
, which returns the next cell .
A , j A ) following the row-major order traversal from cell .
, .
, and the function M UST BACKTRACK.
, .
, which determines if backtracking is necessary from cell .
, .
based on the conditions mentioned in step 2 above.
Algorithm 1 provides a more detailed description of the INTERNATIONAL JOURNAL OF COMPUTING SCIENCE AND APPLIED MATHEMATICS VOL.
NO.
MARCH 2024
Algorithm 1 M UST BACKTRACK.
, .
returns true if we need to backtrack based on the current condition of cell .
, .
Input: The cell to be checked .
, .
taken from an instance Gi,j .
Output: If any of the backtracking conditions are met, the function returns true.
1: .
, .
Ia Gi,j n h is the hint and r is the region label 2: ConditionA Ia false 3: for all cell .
A , j A ) adjacent to .
, .
A , rA ) Ia GiA ,j A ConditionA Ia ConditionA or h = hA 6: end for 7: ConditionB Ia CVr,h > 1 8: return ConditionA or ConditionB M UST BACKTRACK.
, .
The variable ConditionA in line 2 of Algorithm 1 stores a Boolean value illustrating whether any cells adjacent to the cell .
, .
have hints equal to hi,j .
The variable ConditionB in line 7 of Algorithm 1 describes the condition of whether a particular hint hi,j within a region r appears more than once.
Notice that this algorithm involves one iteration in lines 3-5 to update the value of ConditionA.
Since a cell .
, .
has at most eight adjacent cells, we may assume that Algorithm 1 takes O.
time for an input cell .
, .
Algorithm 2 expounds the backtracking algorithm, utilizing N EXT C ELL.
, .
and M UST BACKTRACK.
, .
as subroutines.
These functions and procedures consider the variables G and C, respectively representing the grid state during the backtracking process and the grid state that constitutes a solution.
Furthermore, these processes also consider the variables CV as a list of size R whose k-th component is a list of integers of size sk , and N as a list of size R where each component is a set of integers.
Here.
R denotes the number of regions.
By invoking S EARCH.
, .
outlined in Algorithm 2, the search for a solution commences recursively using the backtracking approach, starting from cell .
, .
Fig.
visualizes the algorithm on a 3 y 3 instance with two regions and four hint cells.
We use the state space tree model of the backtracking process to analyze the asymptotic complexity of the running time for Algorithm 2.
This running time is measured in terms of the number of elementary operations as defined in .
In the following theorem, the notation P .
, .
denotes the number of r-permutations of n objects, i.
P .
, .
= n!/.
Oe .
! where n! denotes the factorial of n.
Theorem 2.
The number of elementary operations in Algorithm 2 for solving any Suguru instance of size m y n with R regions is given by T .
, n.
R) where T .
, n.
R) O 1
Oe1
A !
A P (A , .
A i where A denotes the number of empty cells in region .
O O R).
Proof.
In the worst-case scenario, the number of states in the backtracking algorithm equals the number of nodes in the state space tree.
In this proof, it is important to note that when we refer to a state, we specifically mean a valid state unless it is specified otherwise.
By valid state, we mean a state with at least one child node within the search space tree .
xcept for the terminal stat.
Each region allows an empty cell there to be filled with any value from the set N , where N is the set of numbers .
O O s ) that do not appear in any of the initial hint cells within region .
Here, s denotes the number of cells in region .
Consequently, each region .
O O R, where R is the number of region.
, contains A = |N | empty cells.
The order in which empty cells are filled does not impact the number of states in the state space tree, provided we exclude the pruning process for the condition related to the adjacent cells.
This is because the number of possible values for all empty cells in a region remains identical regardless of the current stateAos condition.
For simplicity, we consider the generated state space tree as a result of filling the empty cells in the order of region labels.
Each level in the state space tree, except for the root state .
, the initial puzzle stat.
level, corresponds to states resulting from filling a single empty cell, branching from the previous level.
The immediate A1 levels after the root consist of states obtained by filling the empty cells in region 1.
The following A2 levels correspond to the states obtained by filling the empty cells in region 2 after all empty cells in region1 are Oe1 In general.
A levels starting at level =1 A 1 until level =1 A correspond to the states obtained by filling the empty cells in region .
O O R) after all cells in region for 1 O O Oe 1 are filled.
To visualize this state space tree, see Fig.
Level 1 involves filling the first empty cell in region 1.
this level, there are A1 states.
This can be easily understood by observing that the root state branches out into A1 states, as there are A1 possible values for the first empty cell.
Level 2 corresponds to possible states of filling the second empty cell in region 1.
Notice that there are A1 (A1 Oe.
possible states in this level because there are A1 states in the previous level .
, and each of those states branches to A1 Oe 1 Moreover.
A1 Oe 1 possible values exist for the second empty cell, as one value is already taken to fill the first empty Generally, the number of states in the i-th level .
O i O A ) corresponding to region can be determined based on the number of states in the preceding level.
Each state from the preceding level branches to A Oe .
Oe .
This is because by the i-th level, i Oe 1 out of A values in the set N are no longer possible to be filled into the current empty cell, as they are already taken by i Oe 1 previous cells in the region .
To ease our analysis, let us introduce the function S.
, ) to count the number of states at the i-th level within the A levels corresponding to the region .
We can define it recursively as S.
, ) = S.
Oe 1, ) A (A Oe .
Oe .
), where 1 O i O A .
, .
= A1 , and S.
, ) = S(AOe1 .
Oe .
A A for any value 1 < O R.
The reason for this is that the preceding level INTERNATIONAL JOURNAL OF COMPUTING SCIENCE AND APPLIED MATHEMATICS VOL.
NO.
MARCH 2024
Algorithm 2 S EARCH.
, .
uses a backtracking approach by filling empty cells in row-major order to search for a solution to a Suguru instance.
Executing S EARCH.
, .
commences the search for a solution starting from cell .
, .
Input: The cell .
, .
to be filled taken from an instance Gi,j .
The initial instance is represented by a two-dimensional array Output: A solution to a Suguru instance .
f an.
, or information that the instance has no solution.
1: if i O m then .
, .
Ia Gi,j n h is the hint and r is the region label of the cell .
, .
if h = 0 then n the cell .
, .
is a hint cell .
A , j A ) Ia N EXT C ELL.
, .
n go to the next cell based on row-major order traversal S EARCH.
A , j A ) n the cell .
, .
is not a hint cell .
, it is empt.
for each integer in Nr do Gi,j Ia (, .
n set as the value for the cell .
, .
CVr.
Ia CVr, 1 n increment CVr, by 1 if not M UST BACKTRACK.
, .
then n up to this point, filling the cell .
, .
with does not violate the rule .
A , j A ) Ia N EXT C ELL.
, .
n go to the next cell based on row-major order traversal S EARCH.
A , j A ) end if Gi,j Ia .
, .
n filling the cell .
, .
with violates the rule, hence h is reset to 0 CVr.
Ia CVr.
Oe 1 n decrement CVr, by 1 end for end if 18: else n all cells in G are filled CIaG n set G as the configuration of the Suguru instance .
hich is also the solutio.
terminate the algorithm 21: end if 22: if .
, .
= .
, .
then n at this point, the instance has no solution terminate the algorithm 24: end if of the first level of the region 1 is the root state level.
the other hand, for > 1, the preceding level of the first level corresponding to the region is the last level from the previous region .
egion Oe .
Simplifying the function for region 1, we obtain S.
, .
= A1 A (A1 Oe .
A (A1 Oe .
A A A (A1 Oe .
Oe .
) where 1 O i O A .
It can be proven that S.
, .
represents the number of i-permutations of A1 elements.
Thus, within the A1 levels corresponding to region 1, the i-th level has S.
, .
= P (A1 , .
states where 1 O i O A1 .
Now let us consider the first level corresponding to region 2, which is level A1 1.
Notice that S.
, .
= S(A1 , .
A A2 = A1 ! A A2 states, as the preceding level .
evel A1 ) has S(A1 , .
= P (A1 .
A1 ) = A1 ! states.
In general, we observe that S.
, ) = S(AOe1 .
Oe .
A P (A , .
for > 1.
Simplifying the function using mathematical induction to a non-recursive form, we also observe that S(A , ) = S(AOe1 .
Oe .
A A ! = A1 ! A A2 ! A .
A !.
Therefore.
Q the i-th level corresponding to region has Oe1 S.
, ) = A P (A , .
states where 1 O i O A .
By considering all A levels corresponding to a region , it is clear that the number of states associated with region is given by S where A Oe1
S =
A ! A P (A , .
Accordingly, by taking into account all levels across all regions, the maximum number of states in the tree is bounded by S where S =1 =1 S =1 "A Oe1
A !
A P (A , .
Furthermore, the algorithm performs i operations for each state that belongs to the i-th level of the region where 1 O O R.
This involves branching the current state into other i invalid states, with each branching operation taking constant This is because the set N does not shrink as we fill the cells in the region .
Thus, the number of elementary operations in Algorithm 2 is:
Oe1 T .
, n.
R) O 1 A ! A P (A , .
A i =1 =1 where the inequality occurs because we omit the pruning process related to the adjacent cells.
In an m y n Suguru instance with only one region and A empty cells, the number of states in the corresponding space tree as in the proof of Theorem 2 becomes 1 i=1 P (A, .
As a result, the number of elementary operations involved for solving this PA instance using Algorithm 2 becomes T .
, n, .
O 1 i=1 P (A, .
A i.
Notice that INTERNATIONAL JOURNAL OF COMPUTING SCIENCE AND APPLIED MATHEMATICS VOL.
NO.
MARCH 2024
ue Fig.
3: Illustration of the pruned state space tree generated by Algorithm 2 for solving a 3 y 3 Suguru instance .
epicted in the topmost par.
The hint cells are indicated by bold red-colored numbers within the cells.
Pruned states, which cannot possibly lead to a solution as they meet any condition specified in step 2, are indicated by red crosses.
The solution found is indicated by a green check mark.
P (A, .
O A! for any 1 O i O A, thus PA i=1 P (A, .
< A AP A! < (A .
Accordingly, 1 i=1 P (A, .
A i < 1 i=1 P (A, .
A A < 1 A A (A .
! < 1 (A .
Therefore, the asymptotic upper bound for solving this instance can be written as O((A .
!).
Notice that the number of empty cells.
A, can be expressed as mn Oe H, where H is the number of hint cells in the instance.
As a result, the asymptotic upper bound for solving an m y n Suguru instance with only one region and H hints using Algorithm 2 is O(.
n Oe H .
!).
To analyze the asymptotic running time complexity of an m y n Suguru instance with R regions and H hint cells, we first prove the following lemma.
Lemma LetQa1 , a2 , .
, an be n positive integers, then ( k=1 ak )! Ou k=1 .
k !).
Proof.
From the Multinomial Theorem .
ee, e.
, .
, .
2 a an )! is a non-negative integer.
we have .
1a a 1 !Aa2 !an ! Pn This quantity represents the number of ways to permute i=1 ai objects with ai indistinguishable objects of type i .
O i O .
Equivalently it also represents the coefficient of xa1 1 xa2 2 A A A xann in the expansion of .
1 x2 A A A xn ).
1 a2 a an ) .
Thus .
1 a2 a an )! Ou 1 and therefore the lemma is proven.
a1 !Aa2 !an ! The following corollary establishes the closed-form expression for the asymptotic running time of Algorithm 2 for solving a general m y n Suguru instance with H hint cells and R regions.
The proof of this corollary uses the fact that the total number PRof empty cells in such an instance equals mn Oe H, i.
, =1 A = mn Oe H.
Corollary 1.
The asymptotic running time complexity of the backtracking algorithm described in Algorithm 2 for solving m y n Suguru instance containing H hint cells and R regions is bounded above by O(R A .
n Oe H .
!).
Proof.
From Theorem 2, the number of elementary operations of Algorithm 2, denoted by T .
, n.
R), satisfies the following "A Oe1 T .
, n.
R) O 1 A ! A P (A , .
A i =1 =1 .
To analyze the asymptotic upper bound of T .
, n.
R), let ushfirst observe the upper i bound of the expression PA QOe1 =1 A ! A P (A , .
on the right hand side of .
Notice that this expression is identical to S , i.
, the number INTERNATIONAL JOURNAL OF COMPUTING SCIENCE AND APPLIED MATHEMATICS VOL.
NO.
MARCH 2024
Fig.
4: The state space tree generated by Algorithm 2 for solving a general m y n Suguru puzzle with R regions.
Although Algorithm 2 fills the empty cells in row-major order, the illustration presents a scenario where the empty cells are filled according to the order of region labels.
This approach is discussed in the proof of Theorem 2.
Each node in the tree represents a grid state, with the root node representing the initial grid state.
INTERNATIONAL JOURNAL OF COMPUTING SCIENCE AND APPLIED MATHEMATICS VOL.
NO.
MARCH 2024
of states associated with region , as defined earlier in the proof of Theorem 2.
By using the fact that P (A , .
O A !, the definition of product, and Lemma 1, we observe the following chains of inequalities " Oe1 ! A A ! A P (A , .
Oe1
A A !
A !
ecause P (A , .
O A !) A ! A ! A ! A =1 .
efinition of produc.
A .
y Lemma .
Thus, we have " Oe1 ! A A ! A P (A , .
A i O
A ! A
Accordingly, we can bound the right hand side of .
as " Oe1 ! A A ! A P (A , .
A i =1 O
A ! A
A ! A A
A ! A A
n Oe H)! A A 2 n Oe H)! A .
n Oe H) .
ince A < mn Oe H) =1 = R A .
n Oe H)! A .
n Oe H)2 < R A .
n Oe H)! A .
n Oe H .
A .
n Oe H .
= R A .
n Oe H .
Therefore, the corollary is proven.
Notice that Corollary 1 complies with the condition when the instance contains only one region, namely, the expression O(R A .
n Oe H .
!) becomes O(.
n Oe H .
!).
Unsurprisingly, this corollary aligns with a factorial complexity class, considering the n-queen problem, another NP-complete problem that shows factorial complexity when solved using the backtracking technique .
T RACTABLE VARIANTS OF S UGURU P UZZLES
There are occasions where NP-complete problems, known for their computational hardness, have solvable subproblems in polynomial time.
This means that although the general problem remains NP-complete, certain sub-problems within it can be efficiently solved.
One recent example of such a case is the Yin-Yang puzzle, which, despite being NP-complete, possesses a polynomial-time solution for the puzzles of size m y n where m O 2 or n O 2, including the search of all possible solutions .
Theorem 2 and Theorem .
Another case involves Nonogram, another NP-complete puzzle that has a tractable variant.
Specifically, the subproblem where each row or column consists of a single block of connected cells can be solved in polynomial time by transforming it into a 2-SAT problem .
Several tractable problems are also found in computational graph theory.
The existence of the maximum clique in a general graph is NP-complete, but the problem can be solved in polynomial time if the graph is planar .
Moreover, determining the minimum set cover and the maximum independent set in bipartite graphs are tractable even though these problems are NP-complete in arbitrary graphs .
These tractable subproblems provide some ways to identify specific situations within NP-complete problems where efficient solutions are attainable.
By isolating these tractable subproblems, we may gain valuable insights into the underlying structure and properties of the NP-complete This section demonstrates that Suguru puzzles of size 1 y n and m y 1 can be solved in polynomial time.
To ease our analysis, we focus on the instance of size 1 y n, noting that the case of size m y 1 can be transformed into this form.
1 y n Suguru puzzle is a variant of the Suguru puzzle, where the grid is restricted to a single row of length n.
Two key characteristics of a 1 y n Suguru puzzle are: .
the shapes of all regions are rectangular.
each cell can be adjacent to at most two other cells.
Before delving into the general solution for a 1 y n Suguru puzzle, let us first introduce a specific variant referred to as the hintless 1 y n Suguru.
This variant is characterized by the absence of hint cells.
In the hintless 1 y n Suguru, we divide the n cells into R regions, which are sequentially labeled from left to right with integers ranging from 1 to R.
Each region k consists of sk cells.
Furthermore, we represent the value in the i-th cell of the puzzle as vi .
To solve the hintless 1yn instance, we use an algorithm that follows these straightforward steps:
For each region k .
O k O R), we assign the values 1 to sk to all sk cells in the region.
Specifically, we fill the i-th cell in each region k with the value i.
We examine each i-th cell .
O i O n Oe .
in the grid in left-to-right order and consider two cases when vi = vi 1 :
If s = 1, where represents the region label of the .
-th cell in the puzzle, we conclude that the instance has no solution.
Otherwise, we swap the values between vi 1 and vi 2 .
The aforementioned algorithm clearly runs in O.
The following example outlines the step-by-step construction INTERNATIONAL JOURNAL OF COMPUTING SCIENCE AND APPLIED MATHEMATICS VOL.
NO.
MARCH 2024
Instance G after filling each regionAos i-th cell with i.
Instance G after swapping the values of v2 and v3 .
Instance G after swapping the values of v4 and v5 .
Fig.
5: Solving a hintless 1 y 6 Suguru instance G with three of a hintless 1 y 6 Suguru puzzle.
Example 1.
Consider a hintless 1 y 6 Suguru puzzle instance G, where the cells are divided into three regions: region 1 consists of the first cell, region 2 consists of the next two cells, and region 3 consists of the remaining three cells.
obtain a solution, we begin by sequentially filling the i-th cell within each region with the value i.
As a result, the current values for v1 , v2 , v3 , v4 , v5 , and v6 are respectively set as 1, 1, 2, 1, 2, and 3 .
ee Fig.
Currently, v1 is equal to v2 , and considering s2 > 1, we proceed by swapping the values of v2 and v3 .
ee Fig.
Consequently, v3 is now equal to v4 , and since s3 > 1, we perform another swap between v4 and v5 .
ee Fig.
Ultimately, the resulting values v1 = 1, v2 = 2, v3 = 1, v4 = 2, v5 = 1, and v6 = 3 form a solution.
This process is visually summarized in Fig.
The aforementioned algorithm is specifically designed to solve a hintless 1 y n Suguru puzzle.
It cannot solve a general 1 y n Suguru puzzle due to the presence of initial hint cells.
The reason is that the swapping process described in the algorithm cannot be applied to initial hint cells since they are not allowed to be modified.
We discuss the algorithm to solve a general 1 y n Suguru puzzle in the proof of the following theorem, which is refined from the explanation in .
Theorem 3.
The construction of a solution .
r determination of its non-existenc.
to any instance of a 1 y n Suguru puzzle can be achieved in O.
Proof.
Suppose we have a Suguru puzzle of size 1 y n, where the cells are divided into R regions with each region labeled in left-to-right order with integers from 1 to R.
Each region k contains sk cells, and each cell in region k is labeled ck,i indicating that it is the i-th cell in region k in left-to-right order where 1 O i O sk .
Moreover, the value presents in cell ck,i is denoted as vk,i .
We first check if any adjacent cells share the same number to ensure a valid initial condition.
we find such a pair of cells, we determine that the instance has no solution.
Subsequently, for each region k, we define the sets k , k , and Nk : the set k = .
, 2, .
, sk } contains the possible numbers that can appear in any cell of region k.
set k contains the numbers in the initial hint cells in region the set Nk = k \ k contains the numbers that can be used to fill the non-hint cells in region k.
By utilizing an efficient implementation of the set data structure, the initial values of k , k , and Nk for all k .
O k O R) can be determined in linear time complexity O.
as each set operation such as inserting, removing, or finding an element can be performed in constant time O.
Moreover, we define the set Ak for each region k representing the set of numbers that the right-most cell of the region k .
, cell ck,sk ) can only be filled with, considering only the condition of the region kOe1 and ignoring the condition of the region k 1.
We set A1 initially as follows:
if the right-most cell in region 1 .
, cell c1,s1 ) is a hint cell, we set A1 = .
1,s1 } .
, the set containing only the number in the right-most cell of region .
otherwise, we set A1 = N1 .
Subsequently, we proceed to determine A2 .
A3 , .
AR by going through each region k .
O k O R).
We perform the following steps for each region:
We check if |Nk | = 1, in which case there is only one way to fill the empty cell in the region k.
If |AkOe1 | = 1 and vk,1 OO AkOe1 , we determine that there is no possible solution for the instance.
This is because this condition implies that we have two adjacent cells with the same value.
If |AkOe1 | = 1 and |Nk | = 2, then there are two ways to fill the empty cells in region k, and one of these ways may conflict with vkOe1,skOe1 .
, the number present in right-most cell in the previous region, k Oe .
For each way, we verify if the condition vk,1 OO / AkOe1 is satisfied.
If the condition holds for such a way, we call it a valid For each valid way, we add vk,sk to Ak .
If the previous step does not hold, we set Ak as follows:
if the right-most cell in region k is a hint cell, we set Ak = .
k,sk } .
, the set containing only the number in the right-most cell of region .
otherwise, we set Ak = Nk .
The absence of a specific condition for when |AkOe1 | = 1 and |Nk | > 2 can be derived by the fact that all values in Nk is possible to be filled in the right-most cell of region k .
he cell ck,sk ).
Specifically, when filling ck,sk with any value from the set Nk where |Nk | > 2, the cardinality of Nk minus the set consisting of and AkOe1 where |AkOe1 | = 1 is greater than zero, i.
, |Nk \ ({} O AkOe1 )| > 0.
Consequently, if the left-most cell in region k .
ell ck,1 ) is empty, we ensure that we have a way to fill ck,1 without conflicting with the right-most cell in the previous region .
ell ckOe1,skOe1 ).
This process of determining A2 .
A3 , .
AR can be achieved with a linear time complexity O.
by traversing sk cells in step 1 or step 3 for each region k.
Once we successfully determine all the sets A2 .
A3 , .
AR , we conclude that a solution to the Suguru instance exists.
Subsequently, we proceed to construct the solution by going through each region k .
O k O R) in reverse order .
, from region R to region .
For each region, we perform the following steps:
If k > 1 and the left-most cell in region k .
, ck,1 ) is empty and |AkOe1 | = 1, we fill vk,1 with any number INTERNATIONAL JOURNAL OF COMPUTING SCIENCE AND APPLIED MATHEMATICS VOL.
NO.
MARCH 2024
Algorithm 3 C ONSTRUCTN(G) constructs the set Nk for every region k .
O k O R) in a one-dimensional Suguru instance Input: A one-dimensional Suguru instance G containing vk,i for each region k and cell i where 1 O k O R and 1 O i O sk .
Output: The array N containing the set Nk for every region k .
O k O R).
1: Ia .
, 2 , .
R ]
2: Ia .
, 2 , .
R ]
3: N Ia [N1 .
N2 , .
NR ]
4: for k Ia 1 to R do k Ia .
, 2, .
, sk } k Ia .
k,i : I S N OT E MPTY C ELL.
k,i ), 1 O i O sk } n k is the set of initial hints for region k Nk Ia k \ k n Nk is the set of possible values for region k 10: end for 11: return N in Nk that is not in AkOe1 .
We then update Ak , and Nk .
If the right-most cell in region k .
, ck,sk ) is empty, we fill vk,sk with any number in Ak and update Nk .
We fill all of the remaining empty cells in region k with numbers in Nk in any order.
If k > 1, we update AkOe1 by removing the number in the left-most cell of region k .
, vk,1 ) .
f an.
This means that AkOe1 becomes AkOe1 \ .
k,1 }.
By the end of these steps, all of the cells in the Suguru instance are filled with numbers, and we have successfully constructed a solution.
In step 3, the process of traversing sk cells for each region k exhibits a time complexity of O.
This algorithm operates with a time complexity of O.
for each of its processes, leading to an overall time complexity of O.
To elaborate on the algorithm described in the proof of Theorem 3, we introduce four functions:
I S E MPTY C ELL.
k,i ), which returns true if the cell ck,i is empty.
I S N OT E MPTY C ELL.
k,i ), which returns true if the cell ck,i is not empty.
C ONSTRUCTN.
, which returns the array N containing sets N1 .
N2 , .
NR .
and C ONSTRUCTA.
N), which returns the array A containing sets A1 .
A2 , .
AR .
The functions C ONSTRUCTN.
and C ONSTRUCTA.
N) are described in Algorithm 3 and Algorithm 4.
Furthermore.
Algorithm 5 elaborates the steps described in the proof of Theorem 3, utilizing the functions I S E MPTY C ELL.
k,i ).
I S N OT E MPTY C ELL.
k,i ).
C ONSTRUCTN.
, and C ONSTRUCTA.
N) as subroutines.
These algorithms consider the variable s as an array of integers of size R, storing the size of each region.
Initial instance G.
Instance G after filling the cells in region 3.
Instance G after filling the cells in region 1.
Fig.
6: Solving a 1 y 6 Suguru instance G with three regions and two hint cells.
The following example outlines the step-by-step construction of a 1 y 6 Suguru puzzle containing three regions with two hint cells.
Example 2.
Consider a 1 y 6 Suguru puzzle instance G with six cells divided into three regions as in Fig.
Region 1 consists of the first two cells, region 2 consists of the next cell, and region 3 consists of the remaining three cells.
this instance, the cells c2,1 and c3,2 are hint cells filled with the numbers 1 and 2, respectively.
We first construct the sets N1 = .
, .
N2 = OI, and N3 = .
, .
These sets contain the numbers that do not appear in any initial hint cells of their respective regions.
Subsequently, we construct the sets A1 .
A2 , and A3 to determine the possible values of the rightmost cell of their respective regions.
Since the right-most cell in region 1 .
ell c1,s2 ) is empty, we set A1 = N1 .
Similarly, as the right-most cell in region 2 .
ell c2,1 ) is a hint cell, we set A2 = .
2,1 }.
For A3 , we have two ways to fill the empty cells in region 3.
Using the first way, we fill cells c3,1 and c3,3 respectively with the numbers 1 and 3.
We find that v3,1 OO A2 , indicates that the first way is not valid.
However, using the second way, we fill cells c3,1 and c3,3 correspondingly with the numbers 3 and 1.
This time, v3,1 OO / A2 , confirming that the second way is valid.
Hence, we set A3 = .
3,3 }.
Since all A1 .
A2 , and A3 are successfully constructed, a solution exists for the Suguru instance.
To construct the solution, we fill cells from the right-most region and move towards the first region.
In this case, as cell c3,1 is empty and |A2 | = 1, we fill v3,1 with a value from N3 excluding A2 , which in this case is .
Since only one possible value exists, we set v3,1 = 3.
Next, since A3 contains only one value, we fill v3,3 = 1.
The instance after the cells in region 3 are filled is depicted in Fig.
As the only cell in region 2 is a hint cell, we leave it unchanged and update A1 to A1 \ .
2,1 } = .
Subsequently, as A1 has only one value, we fill v1,2 = 2.
Finally, we fill v1,1 = 1 as depicted in Fig.
The visual representation for the overall process is given in Fig.
Although the algorithm described in the proof of Theorem 3 has an O.
running time upper bound, it does not retrieve all solutions to a Suguru instance of size 1 y n.
In contrast.
INTERNATIONAL JOURNAL OF COMPUTING SCIENCE AND APPLIED MATHEMATICS VOL.
NO.
MARCH 2024
Algorithm 4 C ONSTRUCTA(G.
N) construct the set Ak for every region k .
O k O R) in a one-dimensional Suguru instance Input: A one-dimensional Suguru instance G containing vk,i for each region k and cell i where 1 O k O R and 1 O i O sk , and the array N containing the sets N1 .
N2 , .
NR .
Output: The array A containing the sets Ak for every region k .
O k O R).
Ak denotes the set of possible values for the right-most cell of the region k .
O k O R).
1: A Ia [A1 .
A2 , .
AR ]
2: if I S N OT E MPTY C ELL .
1,s1 ) then A1 Ia .
1,s1 } n c1,s1 is a hint cell 4: else A1 Ia N1 n A1 can be filled with any value in N1 = 1 \ 1 6: end if 7: for k Ia 2 to R do if |Nk | = 1 then fill the one remaining empty cell in region k with the only number in Nk end if if |AkOe1 | = 1 and vk,1 OO AkOe1 then n if this condition holds, we terminate as the instance has no solution return empty array end if if |AkOe1 | = 1 and |Nk | = 2 then if the first way of filling cells in region k is a valid way then fill the cells in region k with the first way Ak Ia Ak O .
k,sk } undo the filling of cells in region k end if if the second way of filling cells in region k is a valid way then fill the cells in region k with the second way Ak Ia Ak O .
k,sk } undo the filling of cells in region k end if if I S N OT E MPTY C ELL.
k,sk ) then Ak Ia .
k,sk } Ak Ia Nk end if end if 32: end for 33: return A the Yin-Yang puzzle has a tractable variant when considering puzzles of size m y n with m O 2 or n O 2, where the number of solutions is correspondingly bounded above by O.
or O.
Theorem 2 and Theorem .
, enabling the retrieval of all solutions in polynomial time.
Nonetheless, in the subsequent analysis, we demonstrate that for any arbitrary 1 y n Suguru instance with H hints, the number of solutions is factorial in terms of n Oe H.
It is not unexpected that this observation holds, considering that some computationally easy decision problems .
ith polynomial time complexitie.
show non-polynomial time complexities when their corresponding counting problems are considered .
The following theorem provides an upper bound on the number of solutions in a 1 y n Suguru instance.
Theorem 4.
The number of solutions to a Suguru instance of size 1yn with H hint cells is bounded above by O(.
OeH)!).
Proof.
Consider a Suguru instance of size 1 y n containing H hint cells, divided into R regions.
Each region k corresponds to the set Nk containing the numbers not present in any hint cell within that region.
Thus, each region k has |Nk | empty cells, resulting in a total of k=1 |Nk | = n Oe H empty cells across all regions.
It is easy to see that empty cells in each region k can be filled in |Nk |! possible ways.
Considering all regions k where 1 O k O R.
Q the total number of solutions to the instance is bounded |Nk |!.
Using Lemma 1, we have k=1 |Nk |! O k=1 |Nk | ! = .
Oe H)!, which is O(.
Oe H)!).
VI.
C OMPUTATIONAL E XPERIMENTS AND R ESULTS
This section discusses the computational experiments of our proposed backtracking algorithm and their results.
We conducted the experiments using a C programming INTERNATIONAL JOURNAL OF COMPUTING SCIENCE AND APPLIED MATHEMATICS VOL.
NO.
MARCH 2024
Algorithm 5 S OLVE O NE D IMENSIONAL S UGURU(G) returns a solution to the 1 y n Suguru instance, or determines that the instance has no solution.
Input: A one-dimensional Suguru instance G containing vk,i for each region k and cell i where 1 O k O R and 1 O i O sk .
Output: A solution to the Suguru instance .
f an.
1: for all cells in G do n checking if there are adjacent cells that share a number if shares a number with its adjacent cell then return Auno solutionAy end if 5: end for 6: N Ia C ONSTRUCTN(G) 7: A Ia C ONSTRUCTA(G.
N) 8: if A is an empty array then return Auno solutionAy 10: end if 11: for k Ia R to 1 do n construct the solution if k > 1 and I S E MPTY C ELL.
k,1 ) and |AkOe1 | = 1 then fill vk,1 with any number OO Nk \ AkOe1 Ak Ia Ak \ .
k,1 } Nk Ia Nk \ .
k,1 } end if if I S E MPTY C ELL.
k,sk ) then fill vk,sk with any number OO Ak Nk Ia Nk \ .
k,sk } end if fill all of the |Nk | remaining empty cells in region k with the numbers in Nk if k > 1 then AkOe1 Ia AkOe1 \ .
k,1 } end if 25: end for 26: return G language and g compiler version 12.
0 on a 64-bit Windows 10 operating system with 16 GB of RAM and an Intel(R) Core(TM) i7-10750H CPU @ 2.
60GHz.
used C to implement the algorithm because, according to empirical investigation, it performs relatively faster than other prevalently used programming languages .
Interested readers may retrieve the C source codes of our program, test cases for all instances, and other documents pertinent to the experiment at https://github.
com/abcqwq/suguru-backtrack.
The experiment evaluated the performance of the backtracking algorithm described in Section IV, implemented in C .
To ensure comprehensive testing, we utilized a diverse set of test cases gathered from .
The test cases encompass a wide range of Suguru puzzles, varying in dimensions from 6 y 6 to 10 y 10.
There are one hundred eighty test cases, of which 9% are of size 8 y 8.
All instances in the test cases are guaranteed to have exactly one solution.
The objective of the experiment was to calculate the average running time across ten executions required for the algorithm to solve each Table 1 summarizes the algorithmAos running times for solving the test cases, categorized according to their sizes.
From the experiment, despite the factorial upper bound of the running time according to Corollary 1, it is evident that the C implementation of our proposed algorithm solves all instances in less than 0.
5 seconds.
Unfortunately, we could not test the implementation with larger puzzles due to the limitation of the test cases.
It is important to note that the puzzle size does not solely determine the running time of the backtracking algorithm.
Factors such as the number of regions, the number of hint cells, the position of the hint cells, and their arrangements also affect the algorithmAos running time.
As a result, two equally sized test cases may yield varying outcomes and larger test cases potentially have a shorter running time than the smaller ones.
Figure 7 illustrates a particularly challenging instance of the Suguru puzzle for the proposed algorithm, showcasing the longest running time among all test cases.
Although, at first glance, the puzzle appears to be a standard 8 y 8 Suguru grid, its intricacies lie in the number of hints, the arrangement of regions, the configuration of these regions, and the strategic placement of hint cells.
These factors contribute to the proposed algorithm encountering numerous invalid states during its exploration before ultimately converging to the correct solution state.
Except for this challenging instance, on average, the proposed algorithm solved all 8 y 8 test cases 679 milliseconds.
Moreover, excluding such an instance also brings the average running time for solving all instances 311 milliseconds.
The challenging instance in Figure 7 is the most complex puzzle regarding the time required to solve INTERNATIONAL JOURNAL OF COMPUTING SCIENCE AND APPLIED MATHEMATICS VOL.
NO.
MARCH 2024
Puzzle Size 6y6 7y7 8y8 9y9 10 y 10 Number of Test Cases Minimum Running Time Maximum Running Time Average Running Time Table 1.
Running times .
n millisecond.
taken by the backtracking algorithm for solving one hundred eighty instances.
One particular test case of size 8 y 8 takes 470.
481 milliseconds to be solved and is depicted in Figure 7.
Exclusion of such a test case brings the average running time of the algorithm for solving 8 y 8 test case to 2.
679 milliseconds.
The instance of the challenging 8 y 8 Suguru puzzle.
The solution to the challenging 8 y 8 Suguru puzzle.
Fig.
7: An instance of a challenging 8 y 8 Suguru puzzle among the test cases and its solution.
VII.
C ONCLUDING R EMARKS AND O PEN P ROBLEMS
We present an algorithm that verifies a Suguru puzzle solution of size m y n in O.
time and propose a backtracking technique for solving arbitrary Suguru puzzle instance of size myn with H hint cells and R regions in O(RA.
nOeH .
!) Despite this factorial upper bound for the asymptotic running time, all test cases from .
were solved using a standard personal computer in less than half a second.
These test cases contain Suguru puzzles with no more than 100 cells.
With the exclusion of the single test case exhibiting the maximum running time among all 8 y 8 puzzles .
epicted in Figure .
, the average running time for the proposed algorithm in solving 8y8 test cases notably decreased to 2.
This brings the overall average time for solving any instance among the test cases to 1.
311 milliseconds.
We also discuss some tractable variants of Suguru puzzles.
In particular, in Theorem 3, we prove that any Suguru puzzle of size m y n where either m or n equals 1 is solvable in linear time.
This finding presents a particular subproblem of the Suguru puzzles where the solution can be efficiently found.
In Theorem 4, we discuss the upper bound for the number of solutions to a Suguru instance of size 1 y n with H hint We mathematically prove that the number of solutions to such a Suguru instance is bounded above by O(.
Oe H)!).
This result provides insight into the complexity of the counting problem for a tractable Suguru puzzle.
We conjecture that the complexity for such a counting problem belongs to the #P We conclude by suggesting more investigations into the potential use of SAT solvers in solving Suguru puzzles.
The application of SAT solvers has proven highly effective in solving other NP-complete problems, such as the n-queen problem .
, and could also be a promising approach for Suguru puzzles.
Additionally.
SAT solvers can be used for generating Suguru puzzles with unique solutions, opening up the possibilities to explore and gain insights into the underlying structure and properties of Suguru puzzles.
ACKNOWLEDGMENT