Exploring Pyomo, MILP, and Hidato Puzzles

It's a boring sunday and solving a math based puzzle might be helful to reduce the bitterness of it.

This newsletter is dedicated to solving the Hidato puzzle created by Gyora M. Benedek . The objective of Hidato puzzle is to populate the grid with sequential numbers that establish connections in horizontal, vertical, or diagonal directions.

Here is some examples :

Solution:

But how to formulate it mathematically?

The grid can be envisioned as a unified graph in which each node (cell) possesses a value representing its visitation sequence. Certain nodes have predetermined sequences, and this construct forms the basis of our assumption.

Math model:

1. The objective is defined as the length of travelled path
2. Only one arc can exit each node
3. Only one arc can enter each node
4. The sequence of visit depends on binary variable Xij
5. It is assumed that node with value 1 is the starting node and has a source , each node has a small demand = 0.1 , this nodal balance constraint will ensure the connectivity of the graph
6. The flow can only happen between connected nodes

Pyomo code

model = AbstractModel()
model.i = RangeSet(N)
model.j = Set(initialize=model.i)

model.X = Var(model.i,model.j,bounds=(0,1),initialize=0, within=Binary)
model.flow = Var(model.i,model.j,bounds=(0,1),initialize=0, within=Reals)
model.U = Var(model.i,bounds=(1,N),initialize=1, within=Reals)
model.source = Var(model.i,bounds=(0,1),initialize=0, within=Reals)

def rule_C1(model,i):
    if d_data[i,'v'] == 1:
        coef = 1 
    else:
        coef = 0 
    return  coef*model.source[i] - 1/N == sum(model.flow[i,j]-model.flow[j,i] for j in model.j if (i,j) in connect) 
model.C1 = Constraint(model.i,rule=rule_C1)

def rule_C2(model,i):
    return  sum(model.X[i,j] for j in model.j if (i,j) in connect) <= 1
model.C2 = Constraint(model.i,rule=rule_C2)

def rule_C3(model,i):
    return  sum(model.X[j,i] for j in model.j if (i,j) in connect) <= 1
model.C3 = Constraint(model.i,rule=rule_C3)

def rule_C4(model,i,j):
    if (i,j) in connect:
        return  model.flow[i,j] <= model.X[i,j]
    else:
        return Constraint.Skip
model.C4 = Constraint(model.i,model.j, rule=rule_C4)

def rule_C5(model,i,j):
    if (i,j) in connect:
        return  model.U[i]-model.U[j] +N*model.X[i,j]+(N-2)*model.X[j,i]  <= (N-1)
    else:
        return Constraint.Skip
model.C5 = Constraint(model.i,model.j, rule=rule_C5)

def rule_C6(model,i,j):
    if (i,j) in connect and i>j:
        return  model.X[j,i]+ model.X[i,j] <=1
    else:
        return Constraint.Skip
model.C6 = Constraint(model.i,model.j, rule=rule_C6)


def rule_OF(model):
    return  sum(model.X[i,j] for (i,j) in connect) 
model.obj1 = Objective(rule=rule_OF, sense=minimize)
        

Results

Applications

1. Puzzle Games: Hidato puzzles are popular logic puzzle games that appear in newspapers, magazines, and online platforms. They provide engaging challenges for people who enjoy solving puzzles and exercising their logical thinking skills.
2. Cognitive Training: Hidato puzzles, like other logic puzzles, can be used as a form of cognitive training. Solving these puzzles regularly can help improve pattern recognition, problem-solving abilities, and overall mental agility.
3. Educational Tool: Hidato puzzles can be used in educational settings to teach concepts such as sequential reasoning, spatial awareness, and logical deduction. They provide a fun and interactive way for students to develop these skills.
4. Algorithmic Practice: The Hidato problem can be used as a practice exercise for computer science students and programmers learning about graph traversal algorithms and constraint satisfaction problems. It offers a real-world application for these concepts.
5. Artificial Intelligence: Solving Hidato puzzles can be used as a benchmark or test case for evaluating the capabilities of artificial intelligence algorithms. It involves both logical reasoning and constraint satisfaction, making it a suitable challenge for AI systems.
6. Cryptography: Hidato-like puzzles can be used in cryptography as a method of creating and solving puzzles for secure communication. They can serve as an interesting and secure way to exchange information.
7. Geographical Mapping: In geographical mapping, Hidato-like puzzles could represent paths or routes between specific locations on a map. This could have applications in navigation systems or optimizing travel routes.
8. Pathfinding Algorithms: The principles of Hidato can be applied to pathfinding algorithms in robotics and autonomous systems. By considering sequential and connected movements, these algorithms can navigate a space efficiently.
9. Medical Imaging: Hidato-like problems can be used as a way to map and connect regions of interest in medical images, aiding in the analysis and interpretation of complex medical data.
10. Data Visualization: Hidato puzzles can serve as a unique and engaging way to visualize certain types of data or information. The grid structure and sequential connections can be used creatively to represent various relationships.

Overall, the Hidato problem's blend of logical thinking, pattern recognition, and connectivity makes it applicable in various fields, ranging from entertainment and education to artificial intelligence and practical problem-solving.