Jalur Terpendek Ksatria di Papan Catur

Saya telah berlatih untuk kompetisi pemrograman yang akan datang dan saya telah menemukan sebuah pertanyaan yang membuat saya benar-benar bingung. Namun, saya merasa seolah-olah itu adalah konsep yang harus saya pelajari sekarang daripada berharap itu tidak pernah muncul.

Pada dasarnya, ini berhubungan dengan bidak ksatria di papan catur. Anda diberikan dua masukan: lokasi awal dan lokasi akhir. Tujuannya adalah untuk menghitung dan mencetak jalur terpendek yang dapat diambil ksatria untuk mencapai lokasi target.

Saya tidak pernah berurusan dengan hal-hal yang membutuhkan jalur terpendek, dan saya bahkan tidak tahu harus mulai dari mana. Logika apa yang saya terapkan untuk mengatasi masalah ini?

PS Jika ada relevansinya, mereka ingin Anda menambah gerakan normal ksatria dengan juga membiarkannya bergerak ke empat sudut alun-alun yang dibentuk oleh (berpotensi) delapan gerakan yang dapat dilakukan seorang ksatria, mengingat bahwa pusat alun-alun adalah lokasi ksatria.

Anda memiliki grafik di sini, di mana semua gerakan yang tersedia terhubung (nilai = 1), dan gerakan yang tidak tersedia terputus (nilai = 0), matriks renggang akan seperti:

(a1,b3)=1,
(a1,c2)=1,
  .....

Dan jalur terpendek dari dua titik dalam grafik dapat ditemukan menggunakan http://en.wikipedia.org/wiki/Dijkstra's_algorithm

Kode semu dari wikipedia-page:

function Dijkstra(Graph, source):
   for each vertex v in Graph:           // Initializations
       dist[v] := infinity               // Unknown distance function from source to v
       previous[v] := undefined          // Previous node in optimal path from source
   dist[source] := 0                     // Distance from source to source
   Q := the set of all nodes in Graph
   // All nodes in the graph are unoptimized - thus are in Q
   while Q is not empty:                 // The main loop
       u := vertex in Q with smallest dist[]
       if dist[u] = infinity:
          break                         // all remaining vertices are inaccessible from source
       remove u from Q
       for each neighbor v of u:         // where v has not yet been removed from Q.
           alt := dist[u] + dist_between(u, v) 
           if alt < dist[v]:             // Relax (u,v,a)
               dist[v] := alt
               previous[v] := u
   return dist[]

EDIT:

1. seperti orang tolol, mengatakan menggunakan http://en.wikipedia.org/wiki/A*_algorithm bisa lebih cepat.
2. cara tercepat adalah dengan menghitung sebelumnya semua jarak dan menyimpannya ke dalam matriks penuh 8x8. baik, saya akan menyebutnya curang, dan bekerja hanya karena masalahnya kecil. Tetapi terkadang kompetisi akan memeriksa seberapa cepat program Anda berjalan.
3. Poin utamanya adalah jika Anda sedang mempersiapkan kompetisi pemrograman, Anda harus mengetahui algoritma umum termasuk Dijkstra. Titik awal yang baik adalah membaca Introduction to AlgorithmsISBN 0-262-03384-4. Atau Anda dapat mencoba wikipedia, http://en.wikipedia.org/wiki/List_of_algorithms

EDIT: Lihat jawaban Simon , di mana dia memperbaiki rumus yang disajikan di sini.

Sebenarnya ada rumus O (1)

Ini adalah gambar yang saya buat untuk memvisualisasikannya (Kotak yang bisa dijangkau oleh seorang ksatria pada gerakan ^ke N dilukis dengan warna yang sama).

Dapatkah Anda memperhatikan polanya di sini?

Meskipun kita dapat melihat polanya, sangat sulit untuk menemukan fungsi f( x , y )yang mengembalikan jumlah gerakan yang diperlukan untuk berpindah dari kuadrat ( 0 , 0 )ke kuadrat( x , y )

Tapi inilah rumus yang bekerja kapan 0 <= y <= x

int f( int x , int y )
{
    int delta = x - y;

    if( y > delta )
        return 2 * ( ( y - delta ) / 3 ) + delta;
    else
        return delta - 2 * ( ( delta - y ) / 4 );
}

Catatan: Pertanyaan ini ditanyakan pada SACO 2007 Hari 1
Dan solusinya ada di sini

Berikut adalah solusi O (1) yang benar, tetapi untuk kasus di mana kesatria itu bergerak seperti seorang ksatria catur saja, dan pada papan catur yang tak terbatas:

https://jsfiddle.net/graemian/5qgvr1ba/11/

Kunci untuk menemukannya adalah dengan memperhatikan pola yang muncul saat Anda menggambar papan. Pada diagram di bawah ini, bilangan dalam persegi adalah jumlah gerakan minimum yang diperlukan untuk mencapai persegi tersebut (Anda dapat menggunakan pencarian luas-pertama untuk menemukan ini):

Karena penyelesaiannya simetris pada sumbu dan diagonal, saya hanya menggambar case x> = 0 dan y> = x.

Blok kiri bawah adalah posisi awal dan angka di blok mewakili jumlah minimum gerakan untuk mencapai blok tersebut.

Ada 3 pola yang perlu diperhatikan:

• Grup vertikal biru yang bertambah dari 4
• Diagonal merah "utama" (mereka berjalan dari kiri atas ke kanan bawah, seperti garis miring terbalik)
• Diagonal hijau "sekunder" (orientasinya sama dengan merah)

(Pastikan Anda melihat kedua set diagonal sebagai kiri atas ke kanan bawah. Mereka memiliki jumlah gerak yang konstan. Diagonal kiri bawah kiri atas jauh lebih kompleks.)

Anda bisa mendapatkan rumus untuk masing-masing. Blok kuning adalah kasus khusus. Jadi solusinya menjadi:

function getMoveCountO1(x, y) {

    var newXY = simplifyBySymmetry(x, y);

    x = newXY.x;
    y = newXY.y;

    var specialMoveCount = getSpecialCaseMoveCount(x ,y);

    if (specialMoveCount !== undefined)
        return specialMoveCount;

    else if (isVerticalCase(x, y))
        return getVerticalCaseMoveCount(x ,y);

    else if (isPrimaryDiagonalCase(x, y))
        return getPrimaryDiagonalCaseMoveCount(x ,y);

    else if (isSecondaryDiagonalCase(x, y))
        return getSecondaryDiagonalCaseMoveCount(x ,y);

}

dengan yang paling sulit menjadi grup vertikal:

function isVerticalCase(x, y) {

    return y >= 2 * x;

}

function getVerticalCaseMoveCount(x, y) {

    var normalizedHeight = getNormalizedHeightForVerticalGroupCase(x, y);

    var groupIndex = Math.floor( normalizedHeight / 4);

    var groupStartMoveCount = groupIndex * 2 + x;

    return groupStartMoveCount + getIndexInVerticalGroup(x, y);

}

function getIndexInVerticalGroup(x, y) {

    return getNormalizedHeightForVerticalGroupCase(x, y) % 4;

}

function getYOffsetForVerticalGroupCase(x) {

    return x * 2;

}

function getNormalizedHeightForVerticalGroupCase(x, y) {

    return y - getYOffsetForVerticalGroupCase(x);

}

Lihat biola untuk kasus lainnya.

Mungkin ada pola yang lebih sederhana atau lebih elegan yang saya lewatkan? Jika demikian, saya ingin sekali melihat mereka. Secara khusus, saya memperhatikan beberapa pola diagonal pada kotak vertikal biru, tetapi saya belum menjelajahinya. Terlepas dari itu, solusi ini masih memenuhi batasan O (1).

Masalah yang sangat menarik yang saya temui baru-baru ini. Setelah mencari beberapa solusi, saya mencoba memulihkan rumus analitik ( O(1) time and space complexity) yang diberikan pada solusi SACO 2007 Hari 1 .

Pertama-tama saya ingin mengapresiasi Graeme Pyle untuk visualisasi yang sangat bagus yang membantu saya memperbaiki formula.

Entah kenapa (mungkin untuk penyederhanaan atau keindahan atau hanya karena kesalahan) mereka pindah minussign ke flooroperator, akibatnya formula salah floor(-a) != -floor(a) for any a.

Berikut rumus analitik yang benar:

var delta = x-y;
if (y > delta) {
    return delta - 2*Math.floor((delta-y)/3);
} else {
    return delta - 2*Math.floor((delta-y)/4);
}

Rumus ini berfungsi untuk semua pasangan (x, y) (setelah menerapkan sumbu dan simetri diagonal) kecuali (1,0) dan (2,2) kasus sudut, yang tidak memenuhi pola dan hardcode dalam cuplikan berikut:

function distance(x,y){
     // axes symmetry 
     x = Math.abs(x);
     y = Math.abs(y);
     // diagonal symmetry 
     if (x < y) {
        t = x;x = y; y = t;
     }
     // 2 corner cases
     if(x==1 && y == 0){
        return 3;
     }
     if(x==2 && y == 2){
        return 4;
     }
    
    // main formula
    var delta = x-y;
		if(y>delta){
  		return delta - 2*Math.floor((delta-y)/3);
  	}
  	else{
  		return delta - 2*Math.floor((delta-y)/4);
  	}
}


$body = $("body");
var html = "";
for (var y = 20; y >= 0; y--){
	html += '<tr>';
	for (var x = 0; x <= 20; x++){
  	html += '<td style="width:20px; border: 1px solid #cecece" id="'+x+'_'+y+'">'+distance(x,y)+'</td>';
  }
  html += '</tr>';
}

html = '<table>'+html+'</table>';
$body.append(html);

<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script>

Catatan: jQuery hanya digunakan untuk ilustrasi, untuk distancefungsi kode lihat .

Ya, Dijkstra dan BFS akan memberi Anda jawabannya, tetapi menurut saya konteks catur dari masalah ini memberikan pengetahuan yang dapat menghasilkan solusi yang jauh lebih cepat daripada algoritma jalur terpendek generik, terutama pada papan catur tak terbatas.

Untuk mempermudah, mari kita gambarkan papan catur sebagai bidang (x, y). Tujuannya adalah untuk menemukan jalur terpendek dari (x0, y0) ke (x1, y1) hanya menggunakan langkah kandidat (+ -1, + -2), (+ -2, + -1), dan (+ -2 , + -2), seperti yang dijelaskan dalam PS pertanyaan

Berikut adalah pengamatan baru: gambar persegi dengan sudut (x-4, y-4), (x-4, y + 4), (x + 4, y-4), (x + 4, y + 4) . Set ini (sebut saja S4) berisi 32 poin. Jalur terpendek dari 32 titik ini ke (x, y) membutuhkan tepat dua langkah .

Jalur terpendek dari salah satu dari 24 titik dalam set S3 (didefinisikan serupa) ke (x, y) membutuhkan setidaknya dua gerakan .

Oleh karena itu, jika | x1-x0 |> 4 atau | y1-y0 |> 4, jalur terpendek dari (x0, y0) ke (x1, y1) tepat dua langkah lebih besar dari jalur terpendek dari (x0, y0) ke S4. Dan masalah terakhir dapat diselesaikan dengan cepat dengan iterasi langsung.

Misal N = max (| x1-x0 |, | y1-y0 |). Jika N> = 4, maka jalur terpendek dari (x0, y0) ke (x1, y1) memiliki langkah ceil (N / 2) .

Jawaban O (1) di atas [ https://stackoverflow.com/a/8778592/4288232 oleh Mustafa Serdar Şanlı] tidak benar-benar berfungsi. (Periksa (1,1) atau (3,2) atau (4,4), selain untuk kasus tepi yang jelas dari (1,0) atau (2,2)).

Di bawah ini adalah solusi yang jauh lebih buruk (python), yang berfungsi (dengan tambahan "tes"):

def solve(x,y):
        x = abs(x)
        y = abs(y)
        if y > x:
            temp=y
            y=x
            x=temp  
        if (x==2 and y==2):
            return 4
        if (x==1 and y==0):
            return 3

    if(y == 0 or float(y) / float(x) <= 0.5):
        xClass = x % 4
        if (xClass == 0):
            initX = x/2
        elif(xClass == 1):
            initX = 1 + (x/2)
        elif(xClass == 2):
            initX = 1 + (x/2)
        else:
            initX = 1 + ((x+1)/2)

        if (xClass > 1):
            return initX - (y%2)
        else:
            return initX + (y%2)
    else:
        diagonal = x - ((x-y)/2)
        if((x-y)%2 == 0):
            if (diagonal % 3 == 0):
                return (diagonal/3)*2
            if (diagonal % 3 == 1):
                return ((diagonal/3)*2)+2
            else:
                return ((diagonal/3)*2)+2
        else:
            return ((diagonal/3)*2)+1


def test():
    real=[
    [0,3,2,3,2,3,4,5,4,5,6,7,6,7],
    [3,2,1,2,3,4,3,4,5,6,5,6,7,8],
    [2,1,4,3,2,3,4,5,4,5,6,7,6,7],
    [3,2,3,2,3,4,3,4,5,6,5,6,7,8],
    [2,3,2,3,4,3,4,5,4,5,6,7,6,7],
    [3,4,3,4,3,4,5,4,5,6,5,6,7,8],
    [4,3,4,3,4,5,4,5,6,5,6,7,6,7],
    [5,4,5,4,5,4,5,6,5,6,7,6,7,8],
    [4,5,4,5,4,5,6,5,6,7,6,7,8,7],
    [5,6,5,6,5,6,5,6,7,6,7,8,7,8],
    [6,5,6,5,6,5,6,7,6,7,8,7,8,9],
    [7,6,7,6,7,6,7,6,7,8,7,8,9,8]]

    for x in range(12):
        for y in range(12):
            res = solve(x,y)
            if res!= real[x][y]:
                print (x, y), "failed, and returned", res, "rather than", real[x][y]
            else:
               print (x, y), "worked. Cool!"

test()

Yang perlu Anda lakukan adalah memikirkan kemungkinan gerakan ksatria sebagai grafik, di mana setiap posisi di papan adalah simpul dan kemungkinan pindah ke posisi lain sebagai tepi. Tidak perlu algoritma dijkstra, karena setiap sisi memiliki bobot atau jarak yang sama (semuanya mudah atau pendek untuk dilakukan). Anda tinggal melakukan pencarian BFS dari titik awal Anda sampai Anda mencapai posisi akhir.

Solusi dari prinsip pertama dengan Python

Saya pertama kali mengalami masalah ini dalam tes Codility. Mereka memberi saya waktu 30 menit untuk menyelesaikannya - saya butuh waktu lebih lama dari itu untuk mendapatkan hasil ini! Masalahnya adalah: berapa banyak gerakan yang dibutuhkan seorang ksatria untuk beralih dari 0,0 ke x, y hanya menggunakan jurus Knight yang sah. x dan y kurang lebih tidak dibatasi (jadi kita tidak berbicara di sini tentang papan catur 8x8 sederhana).

Mereka menginginkan solusi O (1). Saya menginginkan solusi di mana program secara jelas menyelesaikan masalah (yaitu saya menginginkan sesuatu yang lebih jelas benar daripada pola Graeme - pola memiliki kebiasaan rusak di tempat yang tidak Anda lihat), dan saya benar-benar ingin tidak harus bergantung pada formula yang tidak diperdebatkan, seperti dalam solusi Mustafa

Jadi, inilah solusi saya, untuk apa nilainya. Mulailah, seperti yang dilakukan orang lain, dengan mencatat solusinya simetris terhadap sumbu dan diagonal, jadi kita hanya perlu menyelesaikan untuk 0> = y> = x. Untuk kesederhanaan penjelasan (dan kode) saya akan membalikkan masalah: ksatria mulai dari x, y, dan membidik 0,0.

Misalkan kita mengecilkan masalah ke sekitar asalnya. Kita akan membahas apa sebenarnya arti 'vicinty' pada waktunya, tetapi untuk saat ini, mari kita tuliskan beberapa solusi di lembar contekan (asal di kiri bawah):

2 1 4 3
3 2 1 2
0 3 2 3

Jadi, dengan x, y pada grid, kita bisa membaca jumlah perpindahan ke titik awal.

Jika kita sudah mulai di luar grid, kita harus bekerja kembali ke sana. Kami memperkenalkan 'garis tengah', yang merupakan garis yang diwakili oleh y = x / 2. Ksatria mana pun di x, y pada baris itu dapat bekerja kembali ke lembar contekan menggunakan serangkaian gerakan jam 8 (yaitu: (-2, -1) gerakan). Jika x, y berada di atas garis tengah, maka kita membutuhkan urutan jam 8 dan jam 7, dan jika berada di bawah garis tengah, kita membutuhkan urutan jam 8 dan jam 10. 'jam bergerak. Dua hal yang perlu diperhatikan di sini:

• Urutan ini terbukti jalur terpendek. (Ingin saya membuktikannya, atau sudah jelas?)
• Kami hanya peduli dengan jumlah gerakan seperti itu. Kami dapat mencampur dan mencocokkan gerakan dalam urutan apa pun.

Jadi, mari kita lihat pergerakan garis tengah atas. Apa yang kami klaim adalah:

• (dx; dy) = (2,1; 1,2) (n8; n7) (notasi matriks, tanpa penyusunan huruf matematika - vektor kolom (dx; dy) sama dengan matriks persegi dikalikan dengan vektor kolom (n8; n7) - the jumlah jam 8 bergerak dan jumlah jam 7 bergerak), dan demikian pula;

• (dx; dy) = (2,2; 1, -1) (n8; n10)

Saya mengklaim bahwa dx, dy akan menjadi kasar (x, y), jadi (x-dx, y-dy) akan berada di sekitar asal ('sekitar' apa pun yang ternyata).

Dua baris dalam kode yang menghitung istilah-istilah ini adalah solusi untuk ini, tetapi mereka dipilih untuk memiliki beberapa properti yang berguna:

• Rumus garis tengah atas berpindah (x, y) ke salah satu dari (0,0), (1,1), atau (2,2).
• Rumus garis tengah bawah berpindah (x, y) ke salah satu dari (0,0), (1,0), (2,0), atau (1,1).

(Apakah Anda ingin bukti ini?) Jadi, jarak Knight adalah jumlah dari n7, n8, n10 dan cheatsheet [x-dx, y-dy], dan cheatsheet kami berkurang menjadi ini:

. . 4
. 2 .
0 3 2

Sekarang, ini bukanlah akhir dari cerita. Lihat 3 di baris bawah. Satu-satunya cara kita dapat mencapai ini adalah:

• Kami mulai di sana, atau
• Kami pindah ke sana, dengan urutan gerakan jam 8 dan jam 10. Tetapi jika langkah terakhir adalah pukul 8 (yang memang berhak, karena kita dapat melakukan gerakan kita dalam urutan apa pun), maka kita harus melewati (3,1), yang jaraknya sebenarnya 2 (seperti yang Anda bisa) lihat dari cheatsheet asli). Jadi yang harus kita lakukan adalah melacak mundur satu gerakan jam 8, menghemat total dua gerakan.

Ada pengoptimalan serupa yang bisa didapat dengan 4 di kanan atas. Selain memulai dari sana, satu-satunya cara untuk mencapainya adalah dengan gerakan jam 8 dari (4,3). Itu bukan di cheatsheet, tapi kalau ada di sana, jaraknya jadi 3, karena kita bisa saja jam 7 sampai (3,1) malah, yang jaraknya hanya 2. Jadi, kita harus back-track satu Pindah jam 8, lalu maju satu jam 7.

Jadi, kita perlu menambahkan satu angka lagi ke lembar contekan:

. . 4
. 2 . 2
0 3 2

(Catatan: ada banyak optimisasi pelacakan mundur dari (0,1) dan (0,2) tetapi karena pemecah tidak akan pernah membawa kita ke sana, kita tidak perlu mengkhawatirkannya.)

Jadi di sini, kemudian, adalah beberapa kode Python untuk mengevaluasi ini:

def knightDistance (x, y):
    # normalise the coordinates
    x, y = abs(x), abs(y)
    if (x<y): x, y = y, x
    # now 0 <= y <= x

    # n8 means (-2,-1) (8 o'clock), n7 means (-1,-2) (7 o'clock), n10 means (-2,+1) (10 o'clock)
    if (x>2*y):
        # we're below the midline.  Using 8- & 10-o'clock moves
        n7, n8, n10 = 0,  (x + 2*y)//4,  (x - 2*y + 1)//4
    else:
        # we're above the midline.  Using 7- and 8-o'clock moves
        n7, n8, n10 = (2*y - x)//3, (2*x - y)//3,  0
    x -= 2*n8 + n7 + 2*n10
    y -= n8 + 2*n7 - n10
    # now 0<=x<=2, and y <= x.  Also (x,y) != (2,1)

    # Try to optimise the paths.
    if (x, y)==(1, 0): # hit the  3.  Did we need to?
        if (n8>0): # could have passed through the 2 at 3,1.  Back-up
            x, y = 3, 1; n8-=1;
    if (x, y)==(2, 2): # hit the 4.  Did we need to?
        if (n8>0): # could have passed through a 3 at 4,3.  Back-up, and take 7 o'clock to 2 at 3,1
            x, y = 3, 1; n8-=1; n7+=1

    # Almost there.  Now look up the final leg
    cheatsheet = [[0, 3, 2], [2, None, 2], [4]]
    return n7 + n8 + n10 + cheatsheet [y][x-y]

Kebetulan, jika Anda ingin mengetahui rute yang sebenarnya, maka algoritma ini juga menyediakannya: ini hanyalah rangkaian gerakan jam 7 n7, diikuti oleh (atau diselingi dengan) gerakan jam 8 n8, n10 10- jam bergerak, dan tarian apa pun yang ditentukan oleh lembar contekan (yang, dengan sendirinya, bisa ada di lembar contekan).

Sekarang: Bagaimana membuktikan bahwa ini benar. Tidaklah cukup hanya membandingkan hasil ini dengan tabel jawaban yang benar, karena masalahnya sendiri tidak terbatas. Tetapi kita dapat mengatakan bahwa, jika jarak Knight dari bujur sangkar s adalah d, maka jika {m} adalah himpunan langkah legal dari s, jarak Knight dari (s + m) haruslah d-1 atau d + 1 untuk semua m. (Apakah Anda memerlukan bukti tentang ini?) Selanjutnya, harus ada setidaknya satu persegi yang jaraknya d-1, kecuali s adalah asalnya. Jadi, kita bisa membuktikan kebenarannya dengan menunjukkan properti ini berlaku untuk setiap persegi. Jadi:

def validate (n):

    def isSquareReasonable (x, y):
        d, downhills = knightDistance (x, y), 0
        moves = [(1, 2), (2, 1), (2, -1), (1, -2), (-1, -2), (-2, -1), (-2, 1), (-1,  2)]
        for dx, dy in moves:
            dd = knightDistance (x+dx,  y+dy)
            if (dd == d+1): pass
            elif (dd== d-1): downhills += 1
            else: return False;
        return (downhills>0) or (d==0)

    for x in range (0,  n+1):
        for y in range (0,  n+1):
            if not isSquareReasonable (x,  y): raise RuntimeError ("Validation failed")

Sebagai alternatif, kita dapat membuktikan kebenaran dari salah satu persegi dengan mengejar rute dari menuruni bukit ke asal. Pertama, periksa kewajaran s seperti di atas, lalu pilih s + m apa saja sehingga jarak (s + m) == d-1. Ulangi sampai kita mencapai asalnya.

Howzat?

/*
This program takes two sets of cordinates on a 8*8 chessboard, representing the
starting and ending points of a knight's path.
The problem is to print the cordinates that the knight traverses in between, following
the shortest path it can take.
Normally this program is to be implemented using the Djikstra's algorithm(using graphs)
but can also be implemented using the array method.
NOTE:Between 2 points there may be more than one shortest path. This program prints
only one of them.
*/

#include<stdio.h>

#include<stdlib.h>

#include<conio.h>

int m1=0,m2=0;

/*
This array contains three columns and 37 rows:
The rows signify the possible coordinate differences.
The columns 1 and 2 contains the possible permutations of the row and column difference 
between two positions on a chess board;
The column 3 contains the minimum number of steps involved in traversing the knight's 
path with the given permutation*/

int arr[37][3]={{0,0,0},{0,1,3},{0,2,2},{0,3,3},{0,4,2},{0,5,3},{0,6,4},{0,7,5},    {1,1,2},{1,2,1},{1,3,2},{1,4,3},{1,5,4},{1,6,3},{1,7,4},{2,2,4},{2,3,3},{2,4,2},
            {2,5,3},{2,6,3},{2,7,5},{3,3,2},{3,4,3},{3,5,4},{3,6,3},{3,7,4},{4,4,4},{4,5,3},{4,6,4},{4,7,5},{5,5,4},{5,6,5},{5,7,4},{6,6,5},{6,7,5},{7,7,6}};

void printMoves(int,int,int,int,int,int);
void futrLegalMove(int,int,int,int);
main()
{
  printf("KNIGHT'S SHORTEST PATH ON A 8*8 CHESSBOARD :\n");
  printf("------------------------------------------");
  printf("\nThe chessboard may be treated as a 8*8 array here i.e. the (1,1) ");
  printf("\non chessboard is to be referred as (0,0) here and same for (8,8) ");
  printf("\nwhich is to be referred as (7,7) and likewise.\n");
  int ix,iy,fx,fy;
  printf("\nEnter the initial position of the knight :\n");
  scanf("%d%d",&ix,&iy);
  printf("\nEnter the final position to be reached :\n");
  scanf("%d%d",&fx,&fy);
  int px=ix,py=iy;
  int temp;
  int tx,ty;
  printf("\nThe Knight's shortest path is given by :\n\n");
  printf("(%d, %d)",ix,iy);
  futrLegalMove(px,py,m1,m2);
  printMoves(px,py,fx,fy,m1,m2);
   getch();
} 

/*
  This method checkSteps() checks the minimum number of steps involved from current
  position(a & b) to final position(c & d) by looking up in the array arr[][].
*/

int checkSteps(int a,int b,int c,int d)
{  
    int xdiff, ydiff;
    int i, j;
    if(c>a)
        xdiff=c-a;
    else
        xdiff=a-c;
    if(d>b)
        ydiff=d-b;
    else
        ydiff=b-d;
    for(i=0;i<37;i++)
        {
            if(((xdiff==arr[i][0])&&(ydiff==arr[i][1])) || ((xdiff==arr[i][1])&& (ydiff==arr[i] [0])))
            {
                j=arr[i][2];break;
            }
        }

        return j;
}   

/*
This method printMoves() prints all the moves involved.
*/

void printMoves(int px,int py, int fx, int fy,int a,int b)
{    
 int temp;
 int tx,ty;
 int t1,t2;
  while(!((px==fx) && (py==fy)))
  {   
      printf(" --> ");
      temp=checkSteps(px+a,py+b,fx,fy);
      tx=px+a;
      ty=py+b;
      if(!(a==2 && b==1))
      {if((checkSteps(px+2,py+1,fx,fy)<temp) && checkMove(px+2,py+1))
      {temp=checkSteps(px+2,py+1,fx,fy);
       tx=px+2;ty=py+1;}}
      if(!(a==2 && b==-1))
      {if((checkSteps(px+2,py-1,fx,fy)<temp) && checkMove(px+2,py-1))
      {temp=checkSteps(px+2,py-1,fx,fy);
       tx=px+2;ty=py-1;}}
      if(!(a==-2 && b==1))
      {if((checkSteps(px-2,py+1,fx,fy)<temp) && checkMove(px-2,py+1))
      {temp=checkSteps(px-2,py+1,fx,fy);
       tx=px-2;ty=py+1;}}
      if(!(a==-2 && b==-1))
      {if((checkSteps(px-2,py-1,fx,fy)<temp) && checkMove(px-2,py-1))
      {temp=checkSteps(px-2,py-1,fx,fy);
       tx=px-2;ty=py-1;}}
      if(!(a==1 && b==2))
      {if((checkSteps(px+1,py+2,fx,fy)<temp) && checkMove(px+1,py+2))
      {temp=checkSteps(px+1,py+2,fx,fy);
       tx=px+1;ty=py+2;}}
      if(!(a==1 && b==-2))
      {if((checkSteps(px+1,py-2,fx,fy)<temp) && checkMove(px+1,py-2))
      {temp=checkSteps(px+1,py-2,fx,fy);
       tx=px+1;ty=py-2;}}
      if(!(a==-1 && b==2))
      {if((checkSteps(px-1,py+2,fx,fy)<temp) && checkMove(px-1,py+2))
      {temp=checkSteps(px-1,py+2,fx,fy);
       tx=px-1;ty=py+2;}}
      if(!(a==-1 && b==-2))
      {if((checkSteps(px-1,py-2,fx,fy)<temp) && checkMove(px-1,py-2))
      {temp=checkSteps(px-1,py-2,fx,fy);
       tx=px-1;ty=py-2;}}
       t1=tx-px;//the step taken in the current move in the x direction.
       t2=ty-py;//" " " " " " " " " " " " " " " " " " " " " y " " " " ".
       px=tx;
       py=ty;
       printf("(%d, %d)",px,py);
       futrLegalMove(px,py,t1,t2);
       a=m1;
       b=m2;
   }

} 

/*
The method checkMove() checks whether the move in consideration is beyond the scope of
board or not.
*/   

int checkMove(int a, int b)
{
    if(a>7 || b>7 || a<0 || b<0)
        return 0;
    else
        return 1;
}

/*Out of the 8 possible moves, this function futrLegalMove() sets the valid move by
  applying the following constraints
      1. The next move should not be beyond the scope of the board.
      2. The next move should not be the exact opposite of the previous move.
  The 1st constraint is checked by sending all possible moves to the checkMove() 
  method;
  The 2nd constraint is checked by passing as parameters(i.e. a and b) the steps of the 
  previous move and checking whether or not it is the exact opposite of the current move.
*/

void futrLegalMove(int px,int py,int a,int b)
{
     if(checkMove(px+2,py+1) && (a!=-2 && b!=-1))
         m1=2,m2=1;
     else
     {
         if(checkMove(px+2,py-1)&& (a!=-2 && b!=1))
             m1=2,m2=-1;
     else
     {
         if(checkMove(px-2,py+1)&& (a!=2 && b!=-1))
              m1=-2,m2=1;
     else
     {
         if(checkMove(px-2,py-1)&& (a!=2 && b!=1))
               m1=-2,m2=-1;
     else
     {
         if(checkMove(px+1,py+2)&& (b!=-2 && a!=-1))
               m2=2,m1=1;
     else
     {
         if(checkMove(px+1,py-2)&& (a!=-1 && b!=2))
               m2=-2,m1=1;
     else
     {
         if(checkMove(px-1,py+2)&& (a!=1 && b!=-2))
               m2=2,m1=-1;
     else
     {
         if(checkMove(px-1,py-2)&& (a!=1 && b!=2))
               m2=-2,m1=-1;
     }}}}}}}
}

//End of Program.

Saya belum mempelajari grafik .. sesuai masalah penerapannya hanya melalui array, saya tidak bisa mendapatkan solusi lain selain ini. Saya memperlakukan posisi bukan sebagai peringkat dan file (Notasi catur biasa), tetapi sebagai indeks array. FYI, ini hanya untuk papan catur 8 * 8. Setiap saran perbaikan selalu disambut baik.

* Komentar harus cukup untuk pemahaman Anda tentang logika. Namun, Anda mungkin selalu bertanya.

* Dicentang pada DEV-C ++ 4.9.9.2 compiler (Bloodshed Software).

Saya pikir ini juga dapat membantu Anda ..

NumWays(x,y)=1+min(NumWays(x+-2,y-+1),NumWays(x+-1,y+-2)); 

dan menggunakan Pemrograman Dinamis untuk mendapatkan solusinya.

PS: Ini agak menggunakan BFS tanpa harus bersusah payah mendeklarasikan node dan tepi grafik.

Berikut adalah solusi untuk masalah khusus ini yang diterapkan di Perl. Ini akan menampilkan salah satu jalur terpendek - mungkin ada lebih dari satu jalur dalam beberapa kasus.

Saya tidak menggunakan algoritma apa pun yang dijelaskan di atas - tetapi alangkah baiknya membandingkannya dengan solusi lain.

#!/usr/local/bin/perl -w

use strict;

my $from = [0,0];
my $to   = [7,7];

my $f_from = flat($from);
my $f_to   = flat($to);

my $max_x = 7;
my $max_y = 7;
my @moves = ([-1,2],[1,2],[2,1],[2,-1],[1,-2],[-1,-2],[-2,-1],[-2,1]);
my %squares = ();
my $i = 0;
my $min = -1;

my @s = ( $from );

while ( @s ) {

   my @n = ();
   $i++;

   foreach my $s ( @s ) {
       unless ( $squares{ flat($s) } ) {
            my @m = moves( $s );
            push @n, @m;
            $squares{ flat($s) } = { i=>$i, n=>{ map {flat($_)=>1} @m }, };

            $min = $i if $squares{ flat($s) }->{n}->{$f_to};
       }
   }

   last if $min > -1;
   @s = @n;
}

show_path( $f_to, $min );

sub show_path {
    my ($s,$i) = @_;

    return if $s eq $f_from;

    print "$i => $f_to\n" if $i == $min;

    foreach my $k ( keys %squares ) {
       if ( $squares{$k}->{i} == $i && $squares{$k}->{n}->{$s} ) {
            $i--;
            print "$i => $k\n";
            show_path( $k, $i );
            last;
       }
    }
}

sub flat { "$_[0]->[0],$_[0]->[1]" }

sub moves {
    my $c = shift;
    my @s = ();

    foreach my $m ( @moves ) {
       my $x = $c->[0] + $m->[0];
       my $y = $c->[1] + $m->[1];

       if ( $x >= 0 && $x <=$max_x && $y >=0 && $y <=$max_y) {
           push @s, [$x, $y];
       }
    }
    return @s;
}

__END__

public class Horse {

    private int[][] board;
    private int[] xer = { 2, 1, -1, -2, -2, -1, 1, 2 };
    private int[] yer = { 1, 2, 2, 1, -1, -2, -2, -1 };
    private final static int A_BIG_NUMBER = 10000;
    private final static int UPPER_BOUND = 64;


    public Horse() {
        board =  new int[8][8];
    }

    private int solution(int x, int y, int destx, int desty, int move) {

        if(move == UPPER_BOUND) {
            /* lets put an upper bound to avoid stack overflow */
            return A_BIG_NUMBER;
        }

        if(x == 6 && y ==5) {
            board[6][5] = 1;
            return 1;
        }
        int min = A_BIG_NUMBER;
        for (int i = 0 ; i < xer.length; i++) {
            if (isMoveGood(x + xer[i], y + yer[i])) {
                if(board[x + xer[i]][y + yer[i]] != 0) {
                    min = Integer.min(min, 1 + board[x +xer[i]] [y +yer[i]]);                   
                } else {
                    min = Integer.min(min, 1 + solution(x + xer[i], y + yer[i], destx, desty, move + 1));   
                }                   
            }
        }   
        board[x][y] = min;
        return min;
    }


    private boolean isMoveGood(int x, int y) {
        if (x >= 0 && x < board.length && y >= 0 && y < board.length)
            return true;
        return false;
    }


    public static void main(String[] args) {

        int destX = 6;
        int destY = 7;
        final Horse h = new Horse();
        System.out.println(h.solution(0, 0, destX, destY, 0));
    }
}

Hanya kode ruby ​​dari jawaban jsfiddle Graeme Pyle di atas , menghapus semua kode tambahan dan mengubahnya menjadi ruby ​​hanya untuk mendapatkan solusi dengan algoritmanya, sepertinya berfungsi. Masih menguji:

def getBoardOffset(board)
  return board.length / 2
end

def setMoveCount(x, y, count, board)
  offset = getBoardOffset(board)
  board[y + offset][x + offset] = count
end

def getMoveCount(x, y, board)
    offset = getBoardOffset(board)
    row = board[y + offset]
    return row[x + offset]
end

def isBottomOfVerticalCase(x, y)
    return (y - 2 * x) % 4 == 0
end

def isPrimaryDiagonalCase(x, y)
    return (x + y) % 2 == 0
end

def isSecondaryDiagonalCase(x, y)
    return (x + y) % 2 == 1
end

def simplifyBySymmetry(x, y)
    x = x.abs
    y = y.abs
    if (y < x)
      t = x
      x = y
      y = t
    end
    return {x: x, y: y}
end

def getPrimaryDiagonalCaseMoveCount(x, y)
    var diagonalOffset = y + x
    var diagonalIntersect = diagonalOffset / 2
    return ((diagonalIntersect + 2) / 3).floor * 2
end

def getSpecialCaseMoveCount(x, y)
    specials = [{
            x: 0,
            y: 0,
            d: 0
        },
        {
            x: 0,
            y: 1,
            d: 3
        },
        {
            x: 0,
            y: 2,
            d: 2
        },
        {
            x: 0,
            y: 3,
            d: 3
        },
        {
            x: 2,
            y: 2,
            d: 4
        },
        {
            x: 1,
            y: 1,
            d: 2
        },
        {
            x: 3,
            y: 3,
            d: 2
        }
    ];
    matchingSpecial=nil
    specials.each do |special|
      if (special[:x] == x && special[:y] == y)
        matchingSpecial = special
      end
    end
    if (matchingSpecial)
      return matchingSpecial[:d]
    end
end

def isVerticalCase(x, y)
  return y >= 2 * x
end

def getVerticalCaseMoveCount(x, y)
    normalizedHeight = getNormalizedHeightForVerticalGroupCase(x, y)
    groupIndex = (normalizedHeight/4).floor
    groupStartMoveCount = groupIndex * 2 + x
    return groupStartMoveCount + getIndexInVerticalGroup(x, y)
end

def getIndexInVerticalGroup(x, y)
    return getNormalizedHeightForVerticalGroupCase(x, y) % 4
end

def getYOffsetForVerticalGroupCase(x) 
    return x * 2
end

def getNormalizedHeightForVerticalGroupCase(x, y)
    return y - getYOffsetForVerticalGroupCase(x)
end

def getSecondaryDiagonalCaseMoveCount(x, y)
    diagonalOffset = y + x
    diagonalIntersect = diagonalOffset / 2 - 1
    return ((diagonalIntersect + 2) / 3).floor * 2 + 1
end

def getMoveCountO1(x, y)
    newXY = simplifyBySymmetry(x, y)
    x = newXY[:x]
    y = newXY[:y]
    specialMoveCount = getSpecialCaseMoveCount(x ,y)
    if (specialMoveCount != nil)
      return specialMoveCount
    elsif (isVerticalCase(x, y))
      return getVerticalCaseMoveCount(x ,y)
    elsif (isPrimaryDiagonalCase(x, y))
      return getPrimaryDiagonalCaseMoveCount(x ,y)
    elsif (isSecondaryDiagonalCase(x, y))
      return getSecondaryDiagonalCaseMoveCount(x ,y)
    end
end

def solution(x ,y)
  return getMoveCountO1(x, y)
end


puts solution(0,0)

Satu-satunya niat adalah untuk menghemat waktu seseorang mengonversi kode jika ada yang membutuhkan kode lengkap.

inilah versi PHP dari fungsi Jules May

function knightDistance($x, $y)
{
    $x = abs($x);
    $y = abs($y);

    if($x < $y)
    {
        $tmp = $x;
        $x = $y;
        $y = $tmp;
    }

    if($x > 2 * $y)
    {
        $n7 = 0;
        $n8 = floor(($x + 2*$y) / 4);
        $n10 = floor(($x - 2*$y +1) / 4);
    }
    else
    {
        $n7 = floor((2*$y - $x) / 3);
        $n8 = floor((2*$x - $y) / 3);
        $n10 = 0;
    }

    $x -= 2 * $n8 + $n7 + 2 * $n10;
    $y -= $n8 + 2 * $n7 - $n10;

    if($x == 1 && $y == 0)
    {
        if($n8 > 0)
        {
            $x = 3;
            $y = 1;
            $n8--;
        }
    }
    if($x == 2 && $y == 2)
    {
        if($n8 > 0)
        {
            $x = 3;
            $y = 1;
            $n8--;
            $n7++;
        }
    }

    $cheatsheet = [[0, 3, 2], [2, 0, 2], [4]];

    return $n7 + $n8 + $n10 + $cheatsheet [$y][$x-$y];
}

Ini program saya. Ini bukanlah solusi yang sempurna. Ada banyak perubahan yang harus dilakukan dalam fungsi rekursi. Tapi hasil akhir ini sempurna. Saya mencoba sedikit mengoptimalkan.

public class KnightKing2 {
    private static int tempCount = 0;

    public static void main(String[] args) throws IOException {
        Scanner in = new Scanner(System.in);
        int ip1 = Integer.parseInt(in.nextLine().trim());
        int ip2 = Integer.parseInt(in.nextLine().trim());
        int ip3 = Integer.parseInt(in.nextLine().trim());
        int ip4 = Integer.parseInt(in.nextLine().trim());
        in.close();
        int output = getStepCount(ip1, ip2, ip3, ip4);
        System.out.println("Shortest Path :" + tempCount);

    }

    // 2 1 6 5 -> 4
    // 6 6 5 5 -> 2

    public static int getStepCount(int input1, int input2, int input3, int input4) {
        return recurse(0, input1, input2, input3, input4);

    }

    private static int recurse(int count, int tx, int ty, int kx, int ky) {

        if (isSolved(tx, ty, kx, ky)) {
            int ccount = count+1;
            System.out.println("COUNT: "+count+"--"+tx+","+ty+","+ccount);
            if((tempCount==0) || (ccount<=tempCount)){
                tempCount = ccount;
            }
            return ccount;
        }

            if ((tempCount==0 || count < tempCount) && ((tx < kx+2) && (ty < ky+2))) {
                if (!(tx + 2 > 8) && !(ty + 1 > 8)) {
                    rightTop(count, tx, ty, kx, ky);

                }
                if (!(tx + 2 > 8) && !(ty - 1 < 0)) {
                    rightBottom(count, tx, ty, kx, ky);
                }
                if (!(tx + 1 > 8) && !(ty + 2 > 8)) {
                    topRight(count, tx, ty, kx, ky);
                }
                if (!(tx - 1 < 0) && !(ty + 2 > 8)) {
                    topLeft(count, tx, ty, kx, ky);
                }
                if (!(tx + 1 > 8) && !(ty - 2 < 0)) {
                     bottomRight(count, tx, ty, kx, ky);
                }
                if (!(tx - 1 < 0) && !(ty - 2 < 0)) {
                     bottomLeft(count, tx, ty, kx, ky);
                }
                if (!(tx - 2 < 0) && !(ty + 1 > 8)) {
                    leftTop(count, tx, ty, kx, ky);
                }
                if (!(tx - 2 < 0) && !(ty - 1 < 0)) {
                    leftBottom(count, tx, ty, kx, ky);
                }
            }

        return count;

    }

    private static int rightTop(int count, int tx, int ty, int kx, int ky) {
        return count + recurse(count + 1, tx + 2, ty + 1, kx, ky);

    }

    private static int topRight(int count, int tx, int ty, int kx, int ky) {
        return count + recurse(count + 1, tx + 1, ty + 2, kx, ky);
    }

    private static int rightBottom(int count, int tx, int ty, int kx, int ky) {
        return count + recurse(count + 1, tx + 2, ty - 1, kx, ky);
    }

    private static int bottomRight(int count, int tx, int ty, int kx, int ky) {
        return count + recurse(count + 1, tx + 1, ty - 2, kx, ky);
    }

    private static int topLeft(int count, int tx, int ty, int kx, int ky) {
        return count + recurse(count + 1, tx - 1, ty + 2, kx, ky);
    }

    private static int bottomLeft(int count, int tx, int ty, int kx, int ky) {
        return count + recurse(count + 1, tx - 1, ty - 2, kx, ky);
    }

    private static int leftTop(int count, int tx, int ty, int kx, int ky) {
        return count + recurse(count + 1, tx - 2, ty + 1, kx, ky);
    }

    private static int leftBottom(int count, int tx, int ty, int kx, int ky) {
        return count + recurse(count + 1, tx - 2, ty - 1, kx, ky);
    }

    private static boolean isSolved(int tx, int ty, int kx, int ky) {
        boolean solved = false;
        if ((tx == kx) && (ty == ky)) {
            solved = true;
        } else if ((tx + 2 == kx) && (ty + 1 == ky)) { // right top
            solved = true;
        } else if ((tx + 2 == kx) && (ty - 1 == ky)) { // right bottom
            solved = true;
        } else if ((ty + 2 == ky) && (tx + 1 == kx)) {// top right
            solved = true;
        } else if ((ty + 2 == ky) && (tx - 1 == kx)) {// top left
            solved = true;
        } else if ((tx - 2 == kx) && (ty + 1 == ky)) { // left top
            solved = true;
        } else if ((tx - 2 == kx) && (ty - 1 == ky)) {// left bottom
            solved = true;
        } else if ((ty - 2 == ky) && (tx + 1 == kx)) { // bottom right
            solved = true;
        } else if ((ty - 2 == ky) && (tx - 1 == kx)) { // bottom left
            solved = true;
        }

        return solved;
    }

}

Berikut adalah versi C berdasarkan kode Mustafa Serdar Şanlı yang berfungsi untuk papan finit:

#include <stdio.h>
#include <math.h>

#define test(x1, y1, x2, y2) (sx == x1 && sy == y1 &&tx == x2 &&ty == y2) || (sx == x2 && sy == y2 && tx == x1 && ty==y1)

int distance(int sx, int sy, int tx, int ty) {
    int x, y, t;
    double delta;

    // special corner cases 
    if (test(1, 1, 2, 2) || 
        test(7, 7, 8, 8) || 
        test(7, 2, 8, 1) || 
        test(1, 8, 2, 7))
        return 4;

    // axes symmetry 
    x = abs(sx - tx);
    y = abs(sy - ty);

    // diagonal symmetry 
    if (x < y) {
        t = x;
        x = y;
        y = t;
    }

    // 2 corner cases
    if (x == 1 && y == 0)
        return 3;
    if (x == 2 && y == 2)
        return 4;

    // main
    delta = x - y;
    if (y > delta) {
        return (int)(delta - 2 * floor((delta - y) / 3));
    }
    else {
        return (int)(delta - 2 * floor((delta - y) / 4));
    }
}

Uji di sini dengan bukti terhadap solusi rekursif