Knight’s tour pada papan catur adalah suatu rangkaian perjalanan bidak kuda catur pada papan catur sehingga seluruh kotak terlewati oleh kuda tepat satu kali. Menurut jenisnya Knight’s tour dibedakan menjadi dua yaitu Open Knight’s tour dan Close Knight’s tour. Open Knight’s tour adalah perjalanan bidak kuda yang harus mampu melewati semua kotak pada bidang catur tepat satu kali dan tidak kembali ke kotak awal. Dalam permasalahan teori graf hal itu dikenal dengan lintasan Hamilton, sedangkan Close Knight’s tour adalah perjalanan bidak kuda yang harus melewati semua kotak bidang tepat satu kali dan harus dapat kembali ke kotak awal. Dalam teori graf hal itu dikenal dengan siklus Hamilton. Banyak algoritma yang telah ditemukan untuk menyelesaikan Knight’s tour, salah satunya algoritma Backtrack. Algoritma Backtrack merupakan suatu algoritma perbaikan dari algoritma Brute Force dengan menggunakan algoritma rekursif dan berbasis pada DFS (Depth-First Search) dalam mencari solusi. Selain itu, algoritma ini juga merupakan metode yang mencoba-coba dari beberapa keputusan sampai menemukan salah satu solusi. Algoritma Backtrack ini mampu mencari ada atau tidak adanya solusi Close Knight’tour dan Open Knight’tour. Pada pembahasan skripsi ini lebih difokuskan pada proses penyelesaian Open Knight’s tour dan Close Knight’s tour pada papan catur berukuran mxn dengan m≤12 dan n≤12 menggunakan algoritma Backtrack. Penyelesaian Open Knight’s tour dan Close Knight’s tour menggunakan algoritma Backtrack menghasilkan solusi berupa lintasan Hamilton atau siklus Hamilton pada papan catur. Penyelesaian Knight’s tour ini memunculkan beberapa kasus diantaranya adalah karakter papan catur yang mempunyai atau tidak mempunyai solusi. Selanjutnya adalah kasus jika dimulai dari kotak awal yang berbeda dan solusi tunggal atau tidak tunggal. Jika dapat ditemukan solusi Close Knight’s tour pada suatu kotak sebagai kotak awalnya maka akan dapat ditemukan juga solusi Close Knight’s tour di kotak lain sebagai kotak awalnya. Hal itu tidak berlaku pada Open Knight’s tour, kotak awal dimulainya perjalanan kuda sangat mempengaruhi ada atau tidak adanya solusi Open Knight’s tour pada papan catur. Algoritma Backtrack dapat dibuat menjadi perangkat lunak, sehingga proses pencarian solusi Open Knight’s tour dan Close Knight’s tour akan lebih cepat dibandingkan dengan pencarian secara manual. Hasil yang didapatkan antara pencarian dengan program algoritma Backtrack sama dengan pencarian
展开▼
机译：骑士在棋盘上的游览是在棋盘上的一系列棋子，这样整个箱子就可以被马精确地传递一次。根据其类型，骑士之旅可以分为两个类别，分别是公开骑士之旅和封闭骑士之旅。公开骑士之旅是典当行的旅程，典当行必须能够将象棋场中的所有箱子准确地传递一次，并且不能返回原始箱子。在图论问题中，这被称为汉密尔顿的轨迹，而近距离骑士的巡回之旅是马典当的旅程，该典当必须精确通过所有场方一次，并且必须能够返回到原始盒子。在图论中，它被称为汉密尔顿循环。已经发现许多算法可以完成Knight之旅，其中之一就是Backtrack算法。回溯算法是通过使用递归算法并基于DFS（深度优先搜索）查找解决方案的蛮力算法的一种改进算法。另外，该算法也是一种尝试通过多个决策来寻找解决方案的方法。该Backtrack算法能够查找是否存在Close Knight和Open Knight解决方案。在本文的讨论中，我们将重点更多放在使用Backtrack算法在m≤12且n≤12的棋盘上完成Open Knight和Close Knight巡回的过程中。使用Backtrack算法完成“公开骑士”之旅和“关闭骑士”之旅的完成，将产生汉密尔顿轨迹或棋盘上的汉密尔顿循环形式的解决方案。骑士之旅的结束导致了很多案件，其中包括有解决方案的棋盘角色。接下来的情况是，它是从不同的起始框开始，并使用单个或单个解决方案。如果您可以在一个框内找到“ Close Knight”的旅行解决方案作为初始框，那么您也可以在另一个框内找到“ Close Knight”的旅行解决方案作为初始框。这不适用于Open Knight的巡回演出，骑马旅程开始的初始框会极大地影响棋盘上Open Knight的巡回解决方案的存在与否。可以将回溯算法转化为软件，因此查找“公开骑士”之旅和“关闭骑士”之旅解决方案的过程将比手动搜索更快。使用Backtrack算法程序进行搜索之间获得的结果与搜索相同
展开▼
