Conquering the Chessboard: Unleashing the Knight’s Tour with Pyomo

The Knight’s Tour puzzle is a classic problem in chess, where the goal is to find a sequence of moves for a knight that visits each square on a chessboard exactly once.

This puzzle has intrigued mathematicians and puzzle enthusiasts for centuries. One way to approach solving the Knight’s Tour puzzle is by formulating it as a Mixed Integer Linear Programming (MILP) problem.

In MILP, the chessboard is represented as a set of variables, with each variable indicating whether a knight occupies a particular square. Constraints are defined to ensure that each square is visited only once and that the knight’s moves are valid. Objective functions can be incorporated to guide the search for an optimal or near-optimal solution.

By utilizing the power of Pyomo, a modeling language for optimization problems in Python, the Knight’s Tour puzzle can be tackled efficiently and systematically. MILP techniques provide a rigorous framework to explore different strategies and find solutions to this captivating puzzle.

Let't see the mathematical problem formulation:

1. Minimize the number of required arcs to be travelled
2. if di =1 the olny one path should go out of node i (Ai is the set of allowed nodes that j can take value from them)
3. if di =1 the olny one path should go into the node i (Ai is the set of allowed nodes that j can take value from them)
4. if an arc between i and j is selected we can have flow from i to j otherwise if Uij = then fij= 0
5. Only one node is selected as the starting node and Si = 1 other nodes have Si = 0 , This enforces Gi = 0 in all other nodes
6. Nodal balance on each node
7. Uij (move from i to j) , fij (amount of flow from i to j) , Gi (source value in node i , which has value only in start node)
8. di is a binary parameter indicating those cells that should be visited (in knight tour, all di are 1), Si is a binary parameter which indicates the single starting node

Pyomo Code

First we need to import the required packages

from pyomo.environ import *
import matplotlib.pyplot as plt
import numpy as np
import random 
import operator
from pyomo import environ as pe
import os
os.environ['NEOS_EMAIL'] = 'XXXXXX@gmail.com' 

We also use Neos Server for solving the Pyomo model.

Now we should precalculate the location and allowed movements:

n=64
Xdic={}
itr=0
for i in range(1,int(sqrt(n))+1):
    for j in range(1,int(sqrt(n))+1):
        itr+=1
        Xdic[itr,'x']=i
        Xdic[itr,'y']=j
    
AllTour={}
for i in range(1,n+1):
    for j in range(1,n+1):
        if i!=j:
            AllTour[i,j]=sqrt((Xdic[i,'x']-Xdic[j,'x'])**2+(Xdic[i,'y']-Xdic[j,'y'])**2)
allowed={}
test={}
for cc in [-1,+1]:
    for rr in [-2,+2]:
        test[cc,rr]=1
        test[rr,cc]=1
print(test)                    
for i in range(1,n+1):
    for j in range(1,n+1):
        if i!=j:
            #print(i,j, (Xdic[i,'x']-Xdic[j,'x'],Xdic[i,'y']-Xdic[j,'y']))
            if (Xdic[i,'x']-Xdic[j,'x'],Xdic[i,'y']-Xdic[j,'y']) in test:
                allowed[i,j]=1
                allowed[j,i]=1

Pyomo model

model = AbstractModel()
model.N =Param(mutable=True, default=n) 
model.i = RangeSet(n)
model.j = Set(initialize=model.i)

model.U = Var(model.i,model.j, initialize=0, within=Binary)
model.flow = Var(model.i,model.j,bounds=(0,1), within=NonNegativeReals)
model.G = Var(model.i, bounds=(0,64), within=NonNegativeReals)
model.demand = Var(model.i, within=Binary)


model.OF = Var(within=NonNegativeReals, initialize=5)
def initvalx(model,i):
    return Xdic[i,'x']

def initvaly(model,i):
    return Xdic[i,'y']

model.Xloc=Param(model.i,  within=NonNegativeReals, initialize=initvalx,mutable=True)
model.Yloc=Param(model.i,  within=NonNegativeReals, initialize=initvaly, mutable=True)
model.start=Param(model.i, initialize=0, mutable=True)

def rule_w(model,i):
    return 1+0.05*random.random()
model.w=Param(model.i, initialize=rule_w, mutable=True)

def Rule_D(model,i,j):
    #return sqrt((model.Xloc[i]-model.Xloc[j])**2+(model.Yloc[i]-model.Yloc[j])**2)
    return random.random()

model.D=Param(model.i,model.j,  within=NonNegativeReals,initialize=Rule_D, mutable=True)

def rule_C1(model,i):
    return model.G[i]-0.001*(model.demand[i])==sum(model.flow[i,j]-model.flow[j,i] for j in model.j if (i,j) in allowed)
model.C1   = Constraint(model.i,rule=rule_C1)

def rule_C1A(model,i):
    return model.G[i]<= model.start[i]
model.C1A   = Constraint(model.i,rule=rule_C1A)

def rule_C2(model,i,j):
    if i!=j and (i,j) in allowed:
        return model.flow[i,j]<=model.U[i,j]
    else:
        return Constraint.Skip
model.C2   = Constraint(model.i,model.j,rule=rule_C2)

def rule_C3(model,i):
    return sum(model.U[i,j] for j in model.j if (i,j) in allowed)==model.demand[i]
model.C3   = Constraint(model.i,rule=rule_C3)

def rule_C4(model,j):
    return sum(model.U[i,j] for i in model.i if (i,j) in allowed)==model.demand[j]
model.C4   = Constraint(model.j,rule=rule_C4)

def rule_C5(model,i,j):
    if (i,j) in allowed and i<j:
        return model.U[i,j] + model.U[j,i]<=1
    else: 
        return Constraint.Skip 
model.C5   = Constraint(model.i,model.j,rule=rule_C5)

def rule_OF(model):
    return sum(model.U[r,c]*model.D[r,c] for (r,c) in allowed) - 100*sum(model.demand[i]*model.w[i] for i in model.i) 

model.obj1 = Objective(rule=rule_OF, sense=minimize)

from pyomo import environ as pe
solver_manager = pe.SolverManagerFactory('neos')

Simulation result :

Now, let's make the Knight tour more complicated:

How can we do a knight tour (not obliged to visit all cells) that avoids crossing the travelled arcs ?

In order to consider this issue, we should determine the crossing arcs (before solving the model) and then add the following constraint to the model:

def rule_C6(model,i,j,a,b):
    if [i,j,a,b] in new_ckeck:
        return model.U[i,j] + model.U[a,b]<=1
    else:
        return Constraint.Skip 
model.C6   = Constraint(model.i,model.i,model.i,model.i,rule=rule_C6)

Simulation result :

Conclusions:

Knight’s Tour is a mathematical problem that involves finding a sequence of moves for a knight on a chessboard to visit every square exactly once. While it may not have direct real-world applications in energy, supply chain, and healthcare industries, certain concepts or algorithms inspired by the Knight’s Tour problem can be applied in various ways. Here are three examples for each industry:

Energy:

1. Optimal Routing: The concept of finding an optimal path in the Knight’s Tour problem can be applied to energy distribution networks. By applying similar algorithms, energy companies can optimize the routing of power transmission lines to minimize losses, improve efficiency, and ensure reliable supply.
2. Maintenance Scheduling: In the energy sector, regular maintenance of power plants, substations, and other infrastructure is crucial. Algorithms inspired by the Knight’s Tour problem can help optimize maintenance schedules, ensuring that each component is inspected and serviced efficiently, minimizing downtime and improving overall reliability.
3. Resource Allocation: Energy production involves the allocation of resources such as manpower, equipment, and materials. Applying concepts from the Knight’s Tour problem, algorithms can be developed to optimize the allocation of these resources, ensuring efficient utilization and reducing waste.

Supply Chain:

1. Warehouse Optimization: Warehouses play a vital role in supply chain management. By utilizing algorithms inspired by the Knight’s Tour problem, companies can optimize the layout of their warehouses, improving the flow of goods, reducing travel time, and minimizing storage space requirements.
2. Delivery Route Planning: Delivery route planning is crucial for efficient supply chain operations. Similar to finding an optimal path in the Knight’s Tour problem, algorithms can be used to determine the most efficient routes for delivery vehicles, considering factors such as distance, traffic, and delivery time windows.
3. Inventory Management: Inventory management involves maintaining optimal stock levels while minimizing costs. Concepts from the Knight’s Tour problem can be applied to develop algorithms that optimize inventory placement and movement within a warehouse, reducing stockouts, improving order fulfillment, and minimizing holding costs.

Healthcare:

1. Patient Scheduling: Optimizing patient scheduling in healthcare facilities is important for efficient use of resources and minimizing waiting times. Algorithms inspired by the Knight’s Tour problem can be used to develop scheduling systems that optimize appointment sequencing, reducing patient waiting times and maximizing healthcare provider utilization.
2. Resource Allocation in Hospitals: Hospitals face the challenge of allocating limited resources such as beds, operating rooms, and medical equipment effectively. Concepts from the Knight’s Tour problem can be applied to develop algorithms that optimize the allocation of these resources, ensuring efficient utilization, minimizing wait times, and improving patient care.
3. Disease Surveillance: Disease surveillance involves monitoring the spread of infectious diseases and predicting outbreaks. Algorithms inspired by the Knight’s Tour problem can be used to develop models that simulate the movement of diseases through populations, helping public health authorities identify high-risk areas and allocate resources for prevention and control efforts.

References

[1] Github code