INTERNATIONAL JOURNAL OF COMPUTING SCIENCE AND APPLIED MATHEMATICS VOL.
NO.
MARCH 2024
In Search of Dotless Kropki Puzzle Solution Andri Purnama Ramadan AbstractAiSearching all possible solution and finding the minimum number of clues to make uniquely solvable puzzle always been a natural question for puzzle enthusiast.
However, the attempt usually provide that as difficult task.
In this paper, we attempt to search the solution of Kropki puzzle without dot clues given with graph theory approach, which resulted in some conjectures involving the planarity of graph and cyclicity of latin Index TermsAiKropki.
Latin Square.
Puzzle I NTRODUCTION ATIN square is an arrangement of n uniquely different elements into n y n array such that no row and column contains repeating element.
Even though latin square can use arbitrary symbol for the element, latin square puzzles like sudoku, kropki, and futoshiki usually use the element of A = .
, 2, .
, .
for their element symbols.
Studying the solution or number of clues of puzzle is not a new thing.
Some works of it like .
Ae.
had been published, even proof of minimum clues such that sudoku can be uniquely solvable had been given by .
1 million hours of computation claim.
However, research on latin square puzzle seems mostly still involved in sudoku.
ItAos not surprising because of sudokuAos popularity, but itAos encourage us to study other latin square puzzle.
Kropki is a latin square puzzle with additional constraint using black and white dots between two cells.
Every adjacent cells with 1 : 2 number ratio should be indicated with black dots and every adjacent cells with consecutive number should be indicated with white dots.
Thus, if between the adjacent cells contain no black or white dots, then those numbers must not be consecutive or have 1 : 2 ratio.
Fig.
1: Kropki puzzle and its solution Like the name, dotless kropki means there are no dot clue given, so every adjacent cells should not contain any consecutive number nor the numbers have 1 : 2 ratio.
II.
P RELIMINARIES
In this paper, we write n y n latin square as n-ordered latin square.
Every rows and columnsAo label will begin from 0 consecutively from top to bottom and left to right.
For Ramadan is independent researcher from Kabupaten Bandung.
West Java.
Indonesia.
Email: (Andri.
Purnama98@gmail.
Manuscript received June 12, 2023.
accepted March 5, 2024.
example, if we have 3-ordered latin square, then we will have row 0, row 1, and row 2 from top to bottom and column 0, column 1, and column 2 from left to right, labelling the said row and column.
Every binary operation involving row and column will be operated in Zn even if itAos not implicitly stated.
However, notice that even though we use the element of A = .
, 2, .
, .
to fill the Kropki puzzle, we will use them only as a symbol without making any operation of it, so it shouldnAot make any Definition 1.
Let L be n-ordered latin square.
The element of row r and column c from L is notated as xr,c .
To shorten the writing, we will write row r, column c, and element xr,c as 3-tuple .
, c, xr,c ), which then we will call it coordinate of L.
Definition 2.
Let L be n-ordered latin square.
If there exist k OO N such that xr,c = xr 1,c k for every r and c, then L is called k-cyclic.
Considering the global constraint of dotless kropki puzzle about what number can be adjacent to other number, we can also construct the relation of the numbers using graph.
Definition 3.
n-ordered dotless kropki graph is G = (V.
E) with V = .
, 2, .
, .
and E = {.
i , vj ) :
vi , vj nonconsecutive and the ratio of them is not 1 : .
for distinct i, j OO .
, 1, .
, n Oe .
Let v0 , v1 , .
, vk a sequence of distinct vertices in G = (V.
E) and P1 = (V1 .
E1 ) where V1 = .
0 , v1 , .
, vk } OI V (G) and E1 = {.
i , vi 1 ) : i OO 0, 1, .
, k Oe .
OI E(G).
We call P as path in G.
If edge .
0 , vk ) exists in G, then C = (V1 .
E1 O {.
0 , vk )}) is called cycle in G.
Hamiltonian path is a path such that every vertices on G is visited exactly Similarly.
Hamiltonian cycle is a Hamiltonian path with additional edge connecting pathAos end vertices .
Classifying all graph that has Hamiltonian path or cycle is not an easy task.
In fact, research on finding globally sufficient condition of Hamiltonian path and cycle is still being developed like by .
, .
For this paper.
FanAos result from .
will be used to assist our work.
We will write degree of x, which is the number of edges connected to x, as deg.
Definition 4.
Let G = (V.
E) be a graph, |G| be the number of vertices in G, and k OO N.
If |G| > 1 and G Oe F is connected for every set F OI E of fewer than k edges, then G is called k-edge-connected.
In simple word, a graph G is called k-edge-connected if G remain connected whenever we remove l amount of edges in G, with l < k.
Furthermore, for our convenience, we will call k-edge-connected as k-connected.
INTERNATIONAL JOURNAL OF COMPUTING SCIENCE AND APPLIED MATHEMATICS VOL.
NO.
MARCH 2024
Theorem 1.
Let G = (V.
E) be 2-connected graph with n Ou 3 vertices and let u, v be distinct vertices with distance If max.
, deg.
} Ou n2 then G have Hamiltonian If thereAos a way to draw a graph G on Euclidian plane such that every edges are not intersecting, then G is called planar One famous theorem to examine the planarity of a graph is KuratowskiAos theorem.
Theorem 2 (KuratowskiAos theore.
Let G = (V.
E) be a graph.
G is nonplanar if and only if it contains subdivision of complete graph K5 or complete bipartite graph K3,3 We can illustrate subdividing graph as adding additional vertex on an edge, so the vertex divide the edge.
As in contains, we can only examine the subgraph of nonplanar graph G and find the subdivision of K5 or K3,3 .
Now we are going to search dotless kropki puzzle solution.
R ESULTS AND D ISCUSSIONS
For n = 1, itAos obvious that the puzzle will only have one solution.
For nontrivial cases, let L be n-ordered latin square and to be filled with element of A = .
, 2, .
, .
Because every rows and columns must contain non-repeating n symbols, then there exist r, c OO N with c = 1, n such that .
, c, xr,c ) is coordinate of L.
Thus, every xr,c must be adjacent to at least two different numbers.
In graph, we could interpreted it as degree of v = xr,c should be at least 2.
For n = 2, 3, 4, we have deg.
= 0 because it canAot be connected to 1, 3, and 4.
For n = 5, we have deg.
= 1 because it can only be connected to 5.
Since every verticesAo degree of dotless kropki puzzle should be at least 2 to have a solution, then we can conclude that n-ordered dotless kropki puzzle donAot have any solution for n = 2, 3, 4, 5.
For n = 6, we will have deg.
Ou 2 for every v.
If we add the next vertex consecutively, we will still have deg.
Ou 2, since the kropki constraint will only prohibit it connected to maximum 2 other previous vertices, so there are still .
Oe .
other vertices to be choosen and it will implies deg.
Ou 2 for every v for all n Ou 6.
Lemma 1.
For n Ou 6, every n-ordered dotless kropki graph have Hamiltonian cycle.
Proof.
Let G = (V.
E) be n-ordered dotless kropki graph.
Since for every v OO V (G) we have deg.
Ou 2, so G must be 2-connected.
We will always have 1 OO V (G) with deg.
= .
Oe .
for every n Ou 6, since 1 will be connected to every other number However, thereAos 5 OO V (G) such that .
, .
, .
, .
OO E(G) for every n, thus there will always be vertices 1 and 2 with distance 2.
Since max.
, deg.
} = n Oe 1 Ou n2 , then by theorem 1.
G must be have Hamiltonian cycle.
In n-ordered latin square puzzle, the solution in k-cyclic form can be constructed if n, k are coprime, and itAos very clear that 1 and nOe1 will always be coprime with n.
However, since we have additional kropki constraint, we canAot directly stated that easily because the relationship of their adjacency may forbid us to construct such solution.
Fortunately, they are not.
Theorem 3.
Let n Ou 6 and L be n-ordered dotless kropki Dotless kropki graph always have solution in 1-cyclic and .
Oe .
-cyclic form.
Proof.
By lemma 1, we know that every dotless kropki graph have Hamiltonian cycle.
Let v0 , v1 , .
, vnOe1 , v0 be vertices sequence that establish the Hamiltonian cycle, then we can construct puzzle solution for row r by .
, i, xr,i ) coordinates with xr,i = vi .
Representing it in graph, itAos clear that xr,i must be connected to xr,iOe1 and xr,i 1 , which have been fulfilled by the Hamiltonian cycle.
Notice that for every r, c OO .
, 1, .
, .
Oe .
}, xr,c is adjacent to xr,cOe1 , xr,c 1 , xrOe1,c , and xr 1,c .
If the puzzle solution is in form of 1-cyclic like we already defined on definition 2, we will have xr,iOe1 = xr 1,i and xr,i 1 = xrOe1,i .
So, if we consider the row r Oe 1 and row r 1, we need no any additional edges for the graph.
Thus, we will not breaking any kropki rules and the solution still satisfy the kropki puzzle.
Proof for .
Oe .
is analogous.
By theorem 3 we conclude that n-ordered dotless kropki puzzle always have solution in 1-cyclic and .
Oe .
-cyclic form, but are they the only solution form? Theorem 4.
Let L be 6-ordered dotless kropki puzzle, then L only have 1-cyclic and 5-cyclic form solution.
Proof.
We already know that 6-ordered dotless kropki puzzle have solution in 1-cyclic or 5-cyclic form.
So, we only need to proof there are no other form solution.
Since L is latin square, then every column should contain So, we will have .
, 1, .
as solution coordinate for some However, notice that 2 can only be connected to 5, 6, this implies .
, 0, .
, 2, .
, 0, .
, 2, .
must be the other solution coordinates.
Let .
, 0, .
, 2, .
be the other solution coordinates.
Notice that 3 can only be connected to 1, 5.
Thus, we will have .
, 3, .
, .
, 4, .
, and .
, 5, .
as another solution coordinates.
So, if we look at the row r, we will have 6, 2, 5, 3, 1, 4 sequence as solution of the puzzle on row r.
On the other hand, if we let .
, 0, .
, 2, .
as solution coordinates, then we will have 5, 2, 6, 4, 1, 3 sequence as solution of the puzzle on row r.
So, the puzzle always should contain 6, 2, 5, 3, 1, 4 or 5, 2, 6, 4, 1, 3 sequence in some row to be solvable.
Let L have row of 6, 2, 5, 3, 1, 4 for the solution.
Considering the solution coordinates of row r, we can only have .
1, 0, .
1, 2, .
as other solution coordinate.
If we have .
1, 2, .
as solution coordinate, we are going to have .
1, 0, .
, .
1, 1, .
, .
1, 3, .
, .
1, 4, .
, .
1, 5, .
as other solution coordinate.
This also implies .
Oe 1, 0, .
, .
Oe 1, 1, .
, .
Oe 1, 2, .
, .
Oe 1, 3, .
, .
Oe 1, 4, .
, .
Oe 1, 5, .
as other coordinate.
Repeating this, we will have k = 1 such that xr,c = xr 1,c 1 for all r, c, which means the solution is 1-cyclic.
With similar approach and letting .
1, 0, .
, we will have 5 Oe cyclic solution.
We will also have similar result by letting INTERNATIONAL JOURNAL OF COMPUTING SCIENCE AND APPLIED MATHEMATICS VOL.
NO.
MARCH 2024
, 0, .
, 2, .
as solution coordinates.
So, no matter how we choose the possibility, it will be always 1-cyclic or 5-cyclic.
Considering the permutation of latin square row, we can easily see that there are only 2 y 6 y 2 = 24 possible solution for 6-ordered dotless kropki puzzle.
Unfortunately, the more vertices the dotless kropki graph have, the more complex it will be.
Theorem 5.
Let L be 7-ordered dotless kropki puzzle.
If the puzzle solution is in k Oe cyclic form, then k = 1 or 6 Proof.
By theorem 3, we know that 7-ordered dotless kropki puzzle must have a solution in 1-cyclic and 6-cyclic form.
So.
Assume the solution is in k Oe cyclic form with k = 1, 6.
As already mentioned in the proof of theorem 3, xr,i must be connected to xr,iOe1 , xr,i 1 , xrOe1,i , xr 1,i .
However, since k = 1, 6, then the vertices connected to xr,i must be distinct.
Now, let k = 2, then the dotless kropki graph must contain this below graph as subgraph.
xr,i 2 xr,i 1 xr,i 3 xr,i 4 xr,i 7 xr,i 5 Call it graph G = (V.
E).
Now take H = (V.
E Oe {.
r,i 1 , xr,i 2 ), .
r,i 3 , xr,i 4 ), .
r,i 5 , xr,i 6 )}) subgraph of G, then we will have H as below xr,i 1 xr,i 3 xr,i 2 xr,i 4 xr,i 5 xr,i 7 As we can see, graph H contain subdivision of K3,3 , so by theorem 2 H must be nonplanar.
Since H is not planar, then G must be nonplanar.
However, 7-ordered dotless kropki graph is planar as shown below.
So, itAos impossible for the dotless kropki graph to contains G, therefore k must not be 2.
For k = 3, 4, 5, similar proof will follow and it force k to be 1 or 6 only.
An alternative proof is to show that for solution to be kcyclic with k = 1, .
Oe .
, then it should satisfy deg.
Ou 4 for every vertices v, but in 7-ordered dotless kropki graph we have 2 with deg.
= 3.
This is also our background to propose conjecture 1 later.
Of course the solution of dotless kropki puzzle doesnAot always have to be k-cyclic.
For example, we have valid non k-cyclic solution for 8-ordered dotless kropki as below.
However.
Finding all possibility of solution combination is exhausting, even for n = 7.
The cyclicity ensure degree of every vertices v of G to be deg.
= 4.
Without it, itAos possible to have deg.
= 2, 3, 4.
If we ignore what vertices does the edge connecting to, we still have 37 = 2187 possible combination to be examine.
The number of combination for n = 7 is still low, but it will grow exponentially as n After tedious brute force, we canAot find any another solution of 7-ordered dotless kropki in any form other than 1-cyclic and 6-cyclic.
We know brute force method is not practical for large number of n.
So, after proving theorem 5, we try to find any properties that related to the solution classification.
8-ordered dotless kropki graph G = (V.
E) is nonplanar because thereAos subgraph H = (V Oe .
, .
E Oe {.
, .
, .
, .
, .
, .
}) which contains subdivision of K3,3 .
8-ordered dotless kropki graph will always be subgraph of n-ordered dotless kropki graph with n > 8, then n-ordered dotless kropki graph must be nonplanar for n Ou 8.
We suspect distance of vertices pair, degree of vertices, and the planarity of graph is related to construct the dotless kropki puzzle solution, so we propose some conjecture which seems to be true.
Conjecture 1.
Let n Ou 6 and G = (V.
E) be n-ordered dotless kropki graph, then there exists vi OO V such that deg.
i ) < 4 if and only if every k-cyclic solution form of the kropki puzzle only satisfied with k = 1, .
Oe .
For left to right proof, it can be seen by looking through any coordinate solution .
, c, xr,c ).
If we want k-cyclic solution with k = 1, .
Oe .
, then xr,c must be adjacent with distinct INTERNATIONAL JOURNAL OF COMPUTING SCIENCE AND APPLIED MATHEMATICS VOL.
NO.
MARCH 2024
xr 1,c , xrOe1,c , xr,c 1 , and xr,cOe1 , which means deg.
r,c ) should be at least 4.
Thus, itAos impossible to construct such solution with deg.
i ) < 4 for some vi .
By theorem 3, the only solution in k-cyclic form are 1-cyclic and .
Oe .
-cyclic.
For right to left proof, we already prove through theorem 4 and 5 that k-cyclic solution form with k = 1, .
Oe .
doesnAot exists for n = 6, 7.
And, for n = 6, 7, we have deg.
= 3 < 4 which hold true for the statement.
To investigate further, we also search all possible combination to create k-cyclic form for n = 8.
Let n = 8.
We need to find all Hamiltonian cycle from 8ordered dotless kropki graph and use the Hamiltonian path of the cycle as our solution of row 0Aos puzzle.
After that, we can construct our k-cyclic by shifting every elements of the row .
Oe .
to fill row r by k and prove that there will be at least one adjacent cells which break the kropki puzzle rules.
For illustration, letAos take 135274681 as our Hamiltonian cycle from 8-ordered dotless kropki graph, then we can fill the row 0 of our solution candidate with 13527468 consucetively.
By theorem 3, we know that 1-cyclic and 7-cyclic form solution exist.
However, from the figure 3, we can see that there are no any other solution for k = 2, 3, .
, 6, at least with our choosen Hamiltonian cycle before, because it will either break the latin square rules .
f k, n is coprim.
or kropki Since if k, n coprime, then the k-cyclic form will not satisfy latin square rules, thus we can neglect every k that coprime with n to ease our work.
So that for n = 8, we only need to inspect all the 3-cyclic, 5-cyclic form for our solution The complete list of Hamiltonian path and every k-cyclic candidate solution that need to be inspected for n = 8 are given in our supplementary files, and all of the candidate solution will have at least one adjacent cell that broke kropki Moreover, for n = 8 we have deg.
= 3 < 4, which again analogous with our statement.
Interestingly, for n > 8, it seems we will always find kcyclic form solution with k = 1, .
Oe .
, which also stronger our notion for conjecture 1.
Figure 4 show one of such solution for n = 9, 10, 11, 12.
Fig.
2: Our solution candidate for 8-ordered dotless kropki Then, shifting the previous rowAos element by k cells with k = 1, 2, .
, 7 respectively, we will have below k-cyclic form as in figure 3 from figure 2.
The shaded cells are the elements that break the rules of latin square or kropki.
Fig.
4: k-cyclic solution with k = 1, .
Oe .
for n = 9, 10, 11, 12 Remember that for n = 9, 10, 11, 12, every degree of the vertices always equals or more than 4, and Figure 4 show that there exists k-cyclic form solution of kropki with k = 1, .
Oe .
, which is in line with our propose conjecture.
Furthermore, we propose our next conjecture.
Conjecture 2.
For n Ou 6, the solution of n-ordered dotless kropki is only in 1-cyclic and .
Oe .
-cyclic form if and only if n-ordered dotless kropki graph is planar.
Fig.
3: Every k Oe cyclic form from figure 2 We know that dotless kropki graph is planar only if n = 6, 7.
Through theorem 4, 5, and some small describing about finding solution through brute force, we have right to left For left to right proof, we may examine it through contrapositive statement.
So, if we have nonplanar graph, then there INTERNATIONAL JOURNAL OF COMPUTING SCIENCE AND APPLIED MATHEMATICS VOL.
NO.
MARCH 2024
must be other solution other than in 1-cyclic and .
Oe.
-cyclic The easiest attempt to validate that it is probably by finding any kOecyclic solution with k = 1, n Oe 1.
However, we should find general condition so that the Hamiltonian cycle on the dotless kropki graph will preserve the condition of latin square and kropki rules to not be broken.
(Thus, we automatically eliminate all possible non-coprime n, k pair, since itAoll not hold latin square properties anymor.
So, if we can prove conjecture 1, then conjecture 2 will be proven automatically.
Since we already found non k-cyclic solution for 8-ordered dotless kropki puzzle, we also suspect there are non k-cyclic solution for arbitary n-ordered dotless kropki puzzle, with n Ou For more generalization, we also propose third conjecture as below.
Conjecture 3.
Let L be latin square puzzle with some restriction of the element adjacency.
If the constructed graph G = (V.
E) of the puzzleAos elements is planar and contain Hamiltonian cycle, then the puzzle solution must be in 1-cyclic or .
Oe .
-cyclic form.
For partial work, letAos assume that L only have k-cyclic form solution with k = 1, .
Oe.
, let k, n coprime, and construct the solution by one row of v0 , v1 , v2 , .
, vnOe1 Hamiltonian path from the Hamiltonian cycle with vi OO G(V ), then vi must be connected to vi 1 , viOe1 .
y Hamiltonian pat.
and vi k , viOek .
y additional edge from .
Oe .
, r, and .
Since we have n, k coprime, then we must have vi k = viOek .
ItAos still possible that .
i k , viOek ) OO E(G).
However, letAos assume that .
i k , viOek ) OO / E(G) for now.
LetAos take vertices vi , vi 1 , vi k , vi k 1 , viOek , viOek 1 .
ItAos obvious that vi is connected to vi 1 , vi k and viOek .
Since the solution is k-cyclic, we will also have vi k 1 connected to vi k .
rom the Hamiltonian pat.
and vi 1 .
rom the additional edg.
With similar reasoning, we also will have viOek 1 connected to vi 1 and viOek .
Remember that the row solution constructed from Hamiltonian cycle, thus for vi k 1 OO V (G), we must have path from vi k 1 to viOek by vi k 1 , vi k 2 , .
, viOe2k , viOek through Hamiltonian path and additional edge for the last edge.
Within similar reasoning, we also will have viOek 1 , viOek 2 , .
, viOe1 vi kOe1 , vi k path from viOek 1 to vi k without intersecting the path of vi k 1 to viOek .
This prove that the graph will have subdivision of K3,3 , so by theorem 2 it must be nonplanar and contradict the planarity However, the same argument will not work if .
i k , viOek ) OO E(G), because then we will have vi k 1 = viOek .
Also, of course the works only covered some possibility since we assume that the solution is on k-cyclic.
However, we hope this partial work will give insight for further study.
IV.
C ONCLUSIONS
We create theorem 3, 4, and 5 to find the solution of dotless kropki puzzle and propose conjecture 1, 2, and 3 as open questions from our search of dotless kropki puzzle solution.
ACKNOWLEDGMENT