5x5 satranç tahtasında atın tüm karelere tam 1 kere uğrayıp dolaşması.

Question

At L çizer bilindiği gibi, bu kodda başlangıç koordinatı $(0,0)$ olmak üzere, at o noktadan harekete başlıyor ve her bir kareye tam 1 kere uğramak zorunda. Bu mümkün mü, mümkünse bu tur nasıl tamamlanır? 

Bunun kodu yazılırken dikkat edilmesi gereken, atın satranç tahtasının dışına çıkmaması gerektiğidir, diğer göz önünde bulundurulması gereken bir husus, atın o kareyi daha önce ziyaret etmiş olup olmadığıdır. Eğer ziyaret ettiyse, geriye salınması gerekir. ($Backtracking$)

$Moves$ adlı dizi, atın nasıl hareket ettiğini tutuyor. 

$moves=[(1,2),(-1,2),(2,1),(2,-1),(-2,-1),(1,-2),(-1,-2),(-2,1)]$

$visited$ adlı dizi ise, karelerin ziyaret edilip edilmediği bilgisini tutuyor, ilk durumda, hiçbiri ziyaret edilmemiş, bu yüzden $False$, ziyaret edildiğinde $True$ olacak.

$visited=[[False]*N for i in range(N)]$

Örnek bir hareket, başlangıç noktası $(0,0)$ olmak üzere, $(x,y)$ şeklinde, $x$ yatay ve $y$ düşey hareket var. İlk hareket, $(2,1)$, yani sağa $2$ kare ve alta $1$ kare gidiyor demek.

İkinci hareket aşağıdaki listeye göre, $(2,-1)$, bu da $2$ birim sağ ve $1$ birim yukarıya demek. Listenin 3. elemanı, $(-1,2)$, bu da atın kaldığı yerden $1$ birim sola ve $2$ birim alta sallanması demek, bu şekilde listenin tamamı uygulanarak bir yol bulunmuş olur. Tabii bunu yaparken o hücreye daha önce ziyaret edilmiş mi edilmemiş mi bakılıyor. Ziyaret edildiyse, geriye dallanma yapıyor, oradan başka çözüm arıyor.

[(2, 1), (2, -1), (-1, 2), (-1, -2), (-2, 1), (1, 2), (2, 1), (1, -2), (-1, -2), (-2, 1), 

(-1, 2), (2, -1), (2, -1), (-1, 2), (-2, 1), (-1, -2), (1, -2), (2, 1), (1, 2), (-2, 1), 

(-1, -2), (-1, 2), (2, -1), (2, 1)]

Bu yukarıdaki liste gibi 304 adet liste var atın hareket ettiği.

Comments

Programın tamamı şu şekildedir,

N=5 #5x5 grid size.

#Knight Moves( its move's shape is like the L letter)

moves=[(1,2),(-1,2),(2,1),(2,-1),(-2,-1),(1,-2),(-1,-2),(-2,1)]

 

#If the square in the grid has been visited, then no need to visit that again

visited=[[False]*N for i in range(N)]

 

M=N-1

Max=(N*N)-2

 

#This is to store the knights moves.

count,LMoves=0,[]

 

#if the move makes the knight go outside the grid, so this

#function prevents it from doing that.

def CheckInOut(x,y):

    global M    

 

    if x<0 or y<0 or x>M or y>M:

        return False

     

 

    return not(visited[x][y])

      

def Traverse(x,y,counter):

    global count

    for i in range(len(moves)):

        X,Y=moves[i][0],moves[i][1]

        LMoves.append((X,Y))

        visited[x][y]=True

        x,y=x+X,y+Y

         

        if CheckInOut(x,y):

            #print(x,y,counter)

            if counter<Max:

                Traverse(x,y,counter+1)

            else:

                print(LMoves)

                count+=1

 

        #visited[x][y]=False

        #print(visited,i)

        #print("BACKTRACK",x,y,X,Y)

        #Backtracking occurs here

        x,y=x-X,y-Y

        visited[x][y]=False

        LMoves.pop()

 

#we start to traverse at (0,0) point.

Traverse(0,0,0)

print("count=",count)