{"id":25533,"date":"2017-10-15T19:10:46","date_gmt":"2017-10-15T13:40:46","guid":{"rendered":"https:\/\/www.wikitechy.com\/technology\/?p=25533"},"modified":"2017-10-15T19:10:46","modified_gmt":"2017-10-15T13:40:46","slug":"backtracking-set-1-knights-tour-problem-2","status":"publish","type":"post","link":"https:\/\/www.wikitechy.com\/technology\/backtracking-set-1-knights-tour-problem-2\/","title":{"rendered":"JAVA Programming-Backtracking Set 1 (The Knight\u2019s tour problem)"},"content":{"rendered":"

Backtracking is an algorithmic paradigm that tries different solutions until finds a solution that \u201cworks\u201d. Problems which are typically solved using backtracking technique have following property in common. These problems can only be solved by trying every possible configuration and each configuration is tried only once. A Naive solution for these problems is to try all configurations and output a configuration that follows given problem constraints. Backtracking works in incremental way and is an optimization over the Naive solution where all possible configurations are generated and tried.<\/p>\n

For example, consider the following Knight\u2019s Tour problem.
\nThe knight is placed on the first block of an empty board and, moving according to the rules of chess, must visit each square exactly once.<\/p>\n

Path followed by Knight to cover all the cells<\/strong><\/p>\n

Following is chessboard with 8 x 8 cells. Numbers in cells indicate move number of Knight.
\n\"knight-tour-problem\"
\nLet us first discuss the Naive algorithm for this problem and then the Backtracking algorithm.<\/p>\n[ad type=\u201dbanner\u201d]\n

Naive Algorithm for Knight\u2019s tour<\/strong>
\nThe Naive Algorithm is to generate all tours one by one and check if the generated tour satisfies the constraints.<\/p>\n

while there are untried tours\r\n{ \r\n   generate the next tour \r\n   if this tour covers all squares \r\n   { \r\n      print this path;\r\n   }\r\n}<\/pre>\n
Backtracking works in an incremental way to attack problems. Typically, we start from an empty solution vector and one by one add items (Meaning of item varies from problem to problem. In context of Knight\u2019s tour problem, an item is a Knight\u2019s move). When we add an item, we check if adding the current item violates the problem constraint, if it does then we remove the item and try other alternatives. If none of the alternatives work out then we go to previous stage and remove the item added in the previous stage. If we reach the initial stage back then we say that no solution exists. If adding an item doesn\u2019t violate constraints then we recursively add items one by one. If the solution vector becomes complete then we print the solution.<\/p>\n
Backtracking Algorithm for Knight\u2019s tour
\nFollowing is the Backtracking algorithm for Knight\u2019s tour problem.<\/p>\n
If all squares are visited
\nprint the solution
\nElse<\/p>\n
    \n
  • \u00a0Add one of the next moves to solution vector and recursively
    \ncheck if this move leads to a solution. (A Knight can make maximum
    \neight moves. We choose one of the 8 moves in this step).<\/li>\n
  • If the move chosen in the above step doesn\u2019t lead to a solution
    \nthen remove this move from the solution vector and try other
    \nalternative moves.<\/li>\n
  • \u00a0If none of the alternatives work then return false (Returning false
    \nwill remove the previously added item in recursion and if false is
    \nreturned by the initial call of recursion then \u201cno solution exists\u201d )<\/li>\n<\/ul>\n
    Following are implementations for Knight\u2019s tour problem. It prints one of the possible solutions in 2D matrix form. Basically, the output is a 2D 8*8 matrix with numbers from 0 to 63 and these numbers show steps made by Knight.<\/p>\n[ad type=\u201dbanner\u201d]\nJAVA\u00a0Progrmming<\/strong><\/p>\n[pastacode lang=\u201djava\u201d manual=\u201d%2F%2F%20Java%20program%20for%20Knight%20Tour%20problem%0Aclass%20KnightTour%20%7B%0A%20%20%20%20static%20int%20N%20%3D%208%3B%0A%20%0A%20%20%20%20%2F*%20A%20utility%20function%20to%20check%20if%20i%2Cj%20are%0A%20%20%20%20%20%20%20valid%20indexes%20for%20N*N%20chessboard%20*%2F%0A%20%20%20%20static%20boolean%20isSafe(int%20x%2C%20int%20y%2C%20int%20sol%5B%5D%5B%5D)%20%7B%0A%20%20%20%20%20%20%20%20return%20(x%20%3E%3D%200%20%26%26%20x%20%3C%20N%20%26%26%20y%20%3E%3D%200%20%26%26%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20y%20%3C%20N%20%26%26%20sol%5Bx%5D%5By%5D%20%3D%3D%20-1)%3B%0A%20%20%20%20%7D%0A%20%0A%20%20%20%20%2F*%20A%20utility%20function%20to%20print%20solution%0A%20%20%20%20%20%20%20matrix%20sol%5BN%5D%5BN%5D%20*%2F%0A%20%20%20%20static%20void%20printSolution(int%20sol%5B%5D%5B%5D)%20%7B%0A%20%20%20%20%20%20%20%20for%20(int%20x%20%3D%200%3B%20x%20%3C%20N%3B%20x%2B%2B)%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20for%20(int%20y%20%3D%200%3B%20y%20%3C%20N%3B%20y%2B%2B)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20System.out.print(sol%5Bx%5D%5By%5D%20%2B%20%22%20%22)%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20System.out.println()%3B%0A%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%7D%0A%20%0A%20%20%20%20%2F*%20This%20function%20solves%20the%20Knight%20Tour%20problem%0A%20%20%20%20%20%20%20using%20Backtracking.%20%20This%20%20function%20mainly%0A%20%20%20%20%20%20%20uses%20solveKTUtil()%20to%20solve%20the%20problem.%20It%0A%20%20%20%20%20%20%20returns%20false%20if%20no%20complete%20tour%20is%20possible%2C%0A%20%20%20%20%20%20%20otherwise%20return%20true%20and%20prints%20the%20tour.%0A%20%20%20%20%20%20%20Please%20note%20that%20there%20may%20be%20more%20than%20one%0A%20%20%20%20%20%20%20solutions%2C%20this%20function%20prints%20one%20of%20the%0A%20%20%20%20%20%20%20feasible%20solutions.%20%20*%2F%0A%20%20%20%20static%20boolean%20solveKT()%20%7B%0A%20%20%20%20%20%20%20%20int%20sol%5B%5D%5B%5D%20%3D%20new%20int%5B8%5D%5B8%5D%3B%0A%20%0A%20%20%20%20%20%20%20%20%2F*%20Initialization%20of%20solution%20matrix%20*%2F%0A%20%20%20%20%20%20%20%20for%20(int%20x%20%3D%200%3B%20x%20%3C%20N%3B%20x%2B%2B)%0A%20%20%20%20%20%20%20%20%20%20%20%20for%20(int%20y%20%3D%200%3B%20y%20%3C%20N%3B%20y%2B%2B)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20sol%5Bx%5D%5By%5D%20%3D%20-1%3B%0A%20%0A%20%20%20%20%20%20%20%2F*%20xMove%5B%5D%20and%20yMove%5B%5D%20define%20next%20move%20of%20Knight.%0A%20%20%20%20%20%20%20%20%20%20xMove%5B%5D%20is%20for%20next%20value%20of%20x%20coordinate%0A%20%20%20%20%20%20%20%20%20%20yMove%5B%5D%20is%20for%20next%20value%20of%20y%20coordinate%20*%2F%0A%20%20%20%20%20%20%20%20int%20xMove%5B%5D%20%3D%20%7B2%2C%201%2C%20-1%2C%20-2%2C%20-2%2C%20-1%2C%201%2C%202%7D%3B%0A%20%20%20%20%20%20%20%20int%20yMove%5B%5D%20%3D%20%7B1%2C%202%2C%202%2C%201%2C%20-1%2C%20-2%2C%20-2%2C%20-1%7D%3B%0A%20%0A%20%20%20%20%20%20%20%20%2F%2F%20Since%20the%20Knight%20is%20initially%20at%20the%20first%20block%0A%20%20%20%20%20%20%20%20sol%5B0%5D%5B0%5D%20%3D%200%3B%0A%20%0A%20%20%20%20%20%20%20%20%2F*%20Start%20from%200%2C0%20and%20explore%20all%20tours%20using%0A%20%20%20%20%20%20%20%20%20%20%20solveKTUtil()%20*%2F%0A%20%20%20%20%20%20%20%20if%20(!solveKTUtil(0%2C%200%2C%201%2C%20sol%2C%20xMove%2C%20yMove))%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20System.out.println(%22Solution%20does%20not%20exist%22)%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20return%20false%3B%0A%20%20%20%20%20%20%20%20%7D%20else%0A%20%20%20%20%20%20%20%20%20%20%20%20printSolution(sol)%3B%0A%20%0A%20%20%20%20%20%20%20%20return%20true%3B%0A%20%20%20%20%7D%0A%20%0A%20%20%20%20%2F*%20A%20recursive%20utility%20function%20to%20solve%20Knight%0A%20%20%20%20%20%20%20Tour%20problem%20*%2F%0A%20%20%20%20static%20boolean%20solveKTUtil(int%20x%2C%20int%20y%2C%20int%20movei%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20int%20sol%5B%5D%5B%5D%2C%20int%20xMove%5B%5D%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20int%20yMove%5B%5D)%20%7B%0A%20%20%20%20%20%20%20%20int%20k%2C%20next_x%2C%20next_y%3B%0A%20%20%20%20%20%20%20%20if%20(movei%20%3D%3D%20N%20*%20N)%0A%20%20%20%20%20%20%20%20%20%20%20%20return%20true%3B%0A%20%0A%20%20%20%20%20%20%20%20%2F*%20Try%20all%20next%20moves%20from%20the%20current%20coordinate%0A%20%20%20%20%20%20%20%20%20%20%20%20x%2C%20y%20*%2F%0A%20%20%20%20%20%20%20%20for%20(k%20%3D%200%3B%20k%20%3C%208%3B%20k%2B%2B)%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20next_x%20%3D%20x%20%2B%20xMove%5Bk%5D%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20next_y%20%3D%20y%20%2B%20yMove%5Bk%5D%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20if%20(isSafe(next_x%2C%20next_y%2C%20sol))%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20sol%5Bnext_x%5D%5Bnext_y%5D%20%3D%20movei%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20if%20(solveKTUtil(next_x%2C%20next_y%2C%20movei%20%2B%201%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20sol%2C%20xMove%2C%20yMove))%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20return%20true%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20else%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20sol%5Bnext_x%5D%5Bnext_y%5D%20%3D%20-1%3B%2F%2F%20backtracking%0A%20%20%20%20%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%20%20%20%20%7D%0A%20%0A%20%20%20%20%20%20%20%20return%20false%3B%0A%20%20%20%20%7D%0A%20%0A%20%20%20%20%2F*%20Driver%20program%20to%20test%20above%20functions%20*%2F%0A%20%20%20%20public%20static%20void%20main(String%20args%5B%5D)%20%7B%0A%20%20%20%20%20%20%20%20solveKT()%3B%0A%20%20%20%20%7D%0A%7D%0A%0A\u201d message=\u201dJAVA\u201d highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\n
    Output<\/strong>:<\/p>\n
      0  59  38  33  30  17   8  63\r\n 37  34  31  60   9  62  29  16\r\n 58   1  36  39  32  27  18   7\r\n 35  48  41  26  61  10  15  28\r\n 42  57   2  49  40  23   6  19\r\n 47  50  45  54  25  20  11  14\r\n 56  43  52   3  22  13  24   5\r\n 51  46  55  44  53   4  21  12\r\n<\/pre>\n
    Note that Backtracking is not the best solution for the Knight\u2019s tour problem. See below article for other better solutions. The purpose of this post is to explain Backtracking with an example.<\/p>\n[ad type=\u201dbanner\u201d]\n","protected":false},"excerpt":{"rendered":"
    JAVA Programming-Backtracking Set 1 (The Knight\u2019s tour problem) – Backtracking – Backtracking is an algorithmic paradigm that tries different solutions until finds a solution that \u201cworks\u201d. Problems which are typically solved using backtracking technique have following property in common. <\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[73907,1,2139],"tags":[73908,73915,73912,73940,73947,73914,73944,73941,73929,73926,70705,73938,73942,73930,73916,73919,73911,73933,73945,73939,73932,73923,73924,73918,73922,73925,73910,73946],"class_list":["post-25533","post","type-post","status-publish","format-standard","hentry","category-backtracking-algorithm","category-coding","category-java","tag-backtracking-algorithm","tag-backtracking-algorithm-tutorial","tag-c-programming-problems","tag-chess-algorithm","tag-chess-board-coordinates","tag-chess-board-numbers","tag-chess-board-placement","tag-chess-knight-moves","tag-define-knight","tag-hamiltonian-circuit","tag-hamiltonian-cycle-algorithm","tag-horse-in-chess","tag-how-does-a-knight-move-in-chess","tag-java-knights-tour","tag-java-problems","tag-java-programming-backtracking-set-1-the-knights-tour-problem","tag-knight-and-day","tag-knight-mover","tag-knight-moves-in-chess","tag-knight-tour-problem-solution","tag-knights-journey","tag-knights-tour-algorithm-java","tag-knights-tour-solution","tag-life-a-users-manual","tag-the-knights-tour","tag-what-is-a-knight","tag-what-is-backtracking","tag-what-is-recursion-in-java"],"_links":{"self":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/25533","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/comments?post=25533"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/25533\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=25533"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=25533"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=25533"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}