<jupyter_start><jupyter_text>Knight's Tour&nbsp;Knight's tour is about a knight who tries to travel through all vertices on the chessboard and each vertex is visited only once. Rules of knight's tour can be found in the following linkhttps://en.wikipedia.org/wiki/Knight%27s_tour&nbsp;<jupyter_code>import matplotlib.pyplot as plt
import matplotlib.animation as pltani
import os
os.chdir('K:/ecole/github')

#graph adt
#check the below link for more details
# https://github.com/je-suis-tm/graph-theory/blob/master/graph.py
import graph
#dfs here is slightly different from other dfs
#an organic dfs goes very deep until we cannot find any unvisited children vertices
#in that case we move up to the parent vertex to find unvisited sibling vertices
#this action violates the rule of travel-once
#hence we use a few more lines to adjust the algorithm
#when we havent finished visiting all the vertices
#any backtracking leads to cancellation of the visited status of the current vertex
#becuz this is not the solution we want
#we cant visit one vertex twice
#we keep doing cancellation
#until we find a path that dives very deep and never comes back
#in the end, this path would ve visited all the vertices only once
#it would be the answer we are looking for
#details of organic dfs can be found in the following link
# https://github.com/je-suis-tm/graph-theory/blob/master/BFS%20dfs%20on%20DCG.ipynb
def dfs(ADT,start,path):

    ADT.visit(start)

    path.append(start)

    for newpos in ADT.edge(start):

        if ADT.go(newpos)==0:

            dfs(ADT,newpos,path)

    if len(path)<ADT.order():

        ADT.clear(start)

        path.pop()
#create graph adt
#the movement of knight is very special
#for each vertex, there are eight possible next moves at maximum
#we also need a semi definite constraint to make sure knight doesnt travel outta chessboard
def check_around(ADT,i,j,size):

    for x,y in [(i-2,j+1),(i-2,j-1),(i-1,j-2),
                (i-1,j+2),(i+1,j-2),(i+1,j+2),
                (i+2,j-1),(i+2,j+1)]:

        if x<size and x>=0 and y<size and y>=0:

            ADT.append((i,j),(x,y),1)
            
    return ADT
#viz knight s tour
def draw_chessboard(ind,*args):
    
    ax,path,knight=args
    
    #vertices the knight travelled
    for i in range(ind):
        ax.scatter(path[i][0]+0.5,path[i][1]+0.5,
                    color='red',marker='x',s=200)
    
    #knight s current position
    knight.set_offsets((path[ind][0]+0.5,path[ind][1]+0.5))   
#assume this is an 8 by 8 chessboard
size=8

#generate graph adt
chessboard=graph.graph()
for i in range(size):
    for j in range(size):
        chessboard=check_around(chessboard,i,j,size)
#dfs
#plz note that there are many possible solutions
#this is not the only answer
path=[]
dfs(chessboard,(0,0),path)
fig,ax=plt.subplots(figsize=(5,5))

#create black and white chessboard
for i in range(size):
    for j in range(size):
        if (i%2==0 and j%2==0) or (i%2!=0 and j%2!=0):
            ax.fill_between([i,i+1],j,j+1,color='black')

#knight s trajectory
knight=ax.scatter(path[0][0]+0.5,path[0][1]+0.5,
                    color='gold',marker='*',s=250)
    
#chic design
ax.set_xlim(0,size)
ax.set_ylim(0,size)
ax.set_xticks([])
ax.set_yticks([])

#create animations
anim=pltani.FuncAnimation(fig,draw_chessboard,
                          frames=size*size,
                          interval=700,
                          fargs=(ax,path,knight))
anim.save('knights tour.gif')<jupyter_output>MovieWriter ffmpeg unavailable.
{'fraction_non_alphanumeric': 0.11634506242905789, 'fraction_numerical': 0.021566401816118047, 'mean_word_length': 3.4395465994962215, 'pattern_counts': {'":': 0, '<': 7, '<?xml version=': 0, '>': 6, 'https://': 3, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '1', 'dir': 'jupyter-structured-clean-dedup', 'id': '221050', 'license': 'Apache-2.0', 'n_tokens_mistral': 1254, 'n_tokens_neox': 1188, 'n_words': 374, 'path': 'knights tour.ipynb', 'repo_name': 'tattooday/graph', 'size': '3524'}