8 Jun 2014

Knight's Tour

Problem Statement:
      Find the sequences of the Knight on a chess board, such that Knight visits every square only once.

Fig: Knight's Tour on 5x5 Board

Download Source Code
Solution:

Knight's tour problem dates back to 9th Century AD, the procedure for completing Knight's tour was first described by Warnsdorff in 1823.

The optimal approach for solving this problem is using back-tracking.
Back-Tracking is a technique which incrementally builds candidates to a solution, and it rejects the candidate as soon as it determines the choosing that particular candidate will not lead to valid solution.
Back-Tracking takes the advantage of choosing and rejecting a candidate in a solution with the help of combined effect of Tail and Head Recursion.

Below is the figure demonstrating the possible moves of Knight placed a given square.

Fig: Possible Moves

Below is the implementation of the logic used in the problem with Back-tracking approach.


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
/**
  * Recursive Sub-routine for Knight's Tour
  */
 private static void knightTour(int[][] board, int row , int col , int curr)
 {
  count++;
   if(isValid(board,row,col))
   {
    board[row][col]=curr;
    
    if(curr == (rowLen * colLen - 1))
    {
     printSol(board);
     System.exit(0);
    }
    else
    {
     // All Coordinates from given (row,col)
     knightTour(board,row + 2 , col + 1, curr+1 );
     knightTour(board,row + 1 , col + 2, curr+1 );
     
     knightTour(board,row - 1 , col + 2, curr+1 );
     knightTour(board,row - 2 , col + 1, curr+1 );
     
     knightTour(board,row - 2 , col - 1, curr+1 );
     knightTour(board,row - 1 , col - 2, curr+1 );
     
     knightTour(board,row + 1 , col - 2, curr+1 );
     knightTour(board,row + 2 , col - 1, curr+1 );
     
     board[row][col]=BLANK;
    }
   }
 }

 /**
  * Checks if for given row and col, the move is Valid or not
  * @return true: Valid Mode, false: Invalid Move
  */
 private static boolean isValid(int[][] board, int row, int col) {
  if(row >= 0 && row < colLen && col>=0 && col < rowLen && board[row][col]==BLANK)
   return true;
  return false;
 }

 /**
  * Prints the Chessboard having the hops
  * @param board
  */
 private static void printSol(int[][] board) {
  for(int i=0;i<colLen;i++)
  {
   for(int j=0;j<rowLen;j++)
   {
    System.out.print(board[i][j]+ "\t");
   }
   System.out.println();
  }
  System.out.println("recursive Function called " + count + " times");
 }

Note: the order in which coordinates are given , gives the least number of  failed back-track-paths.

Please post your comments and feedback
Happy Coding !! :)

19 comments:

  1. With a bit browsing, you will discover it's easy to locate wire mesh displays that may work well with your distinct POP location as well as hold the
    belongings you need to show off. But, calling the target market, instilling interest included
    in this, was difficult since there was no definitive strategy for promoting the emblem or business via brochures.
    In short, it's crucial for organizations to ensure they deliver enough exciting details to pique the crowd's interest without crossing the line into the dreaded
    very real problem territory.

    Feel free to visit my homepage; inexpensive trade show displays

    ReplyDelete
  2. From small, mom and pop shops each of the way through to heavily established market leaders,
    annually businesses in most industry as well as every size choose to participate during these important promotional events.
    However, locking in rates early can assist you secure the best
    bargain and assist you to spread out expenditures on the greater length of time
    for max savings. Wood displays are employed by most retail merchandisers for his or her business
    because wood can be a stable and reliable material to produce products.


    Feel free to surf to my website: portable booth displays store

    ReplyDelete
  3. Is the crowd still made up of decision makers. If you already possess a
    display booth designed, have it ready to get a full analysis.
    In short, it's crucial for organizations to ensure they deliver
    enough exciting details to pique the crowd's interest without crossing the road into
    the dreaded mass confusion territory.

    Review my website buy event booth

    ReplyDelete
  4. Saved as a favorite, I really like your site!


    Also visit my blog post; Las Vegas Whirlpool Repairman

    ReplyDelete
  5. This is a topic which is near to my heart... Best wishes!
    Exactly where are your contact details though?

    my blog: Las Vegas GE Appliance Parts

    ReplyDelete
  6. Usually I don't read article on blogs, however I wish
    to say that this write-up very forced me to check out
    and do so! Your writing style has been amazed me. Thanks, very great article.


    my blog :: expert seo london

    ReplyDelete
  7. I am extremely impressed with your writing skills as well as with the layout on your blog.
    Is this a paid theme or did you customize it yourself?
    Either way keep up the nice quality writing, it is rare to see a
    great blog like this one nowadays.

    My site; charter private jets

    ReplyDelete
  8. Good article! We are linking to this particularly great article on our website.
    Keep up the great writing.

    my webpage - cars shipping companies

    ReplyDelete
  9. I drop a leave a response when I appreciate a post on a
    website or if I have something to contribute to the
    discussion. Usually it is caused by the passion communicated in the post
    I read. And on this post "Knight's Tour". I was excited enough
    to drop a thought :) I do have 2 questions for you if
    you don't mind. Could it be just me or do some of these responses appear like written by brain dead people?
    :-P And, if you are posting at other places, I
    would like to keep up with you. Would you list all of all your communal pages like your twitter feed, Facebook page or linkedin profile?


    My weblog jobs in central london

    ReplyDelete
  10. This post will help the internet visitors for setting up
    new blog or even a blog from start to end.

    Feel free to surf to my site ... social media networking

    ReplyDelete
  11. We stumbled over here by a different website and thought I should check things out.
    I like what I see so now i am following you. Look forward to looking into
    your web page yet again.

    my web blog: social media policy for employees

    ReplyDelete
  12. Marvelous, what a weblog it is! This web site gives helpful facts
    to us, keep it up.

    Look into my web site; jobs agencies london

    ReplyDelete
  13. Hello! I know this is kinda off topic but I'd figured I'd ask.
    Would you be interested in exchanging links or
    maybe guest writing a blog article or vice-versa?
    My website discusses a lot of the same subjects as yours and I
    think we could greatly benefit from each other. If you happen to
    be interested feel free to shoot me an e-mail.
    I look forward to hearing from you! Excellent blog by the way!


    Here is my web blog: uk private jet hire

    ReplyDelete
  14. Heya i am for the first time here. I found this board and I find It truly useful
    & it helped me out much. I hope to give something
    back and aid others like you helped me.

    My weblog; service based business

    ReplyDelete
  15. It's a pity you don't have a donate button! I'd definitely donate to this superb blog!
    I suppose for now i'll settle for bookmarking and adding your RSS feed to my Google account.
    I look forward to new updates and will talk about this website with my Facebook group.
    Chat soon!

    Feel free to surf to my webpage ... change individual search

    ReplyDelete
  16. Thank you for sharing your thoughts. I really appreciate your efforts and
    I will be waiting for your further post thanks once again.

    Also visit my blog: tefal plancha

    ReplyDelete
  17. Everyone loves it when folks come together and share views.
    Great site, stick with it!

    Look into my page: Socialite Pro Reviews

    ReplyDelete
  18. you are really a excellent webmaster. The site loading speed
    is incredible. It kind of feels that you're doing any distinctive trick.
    Moreover, The contents are masterwork. you have done a fantastic process on this subject!


    my blog ... how to sell house quickly uk

    ReplyDelete
  19. I used to be able to find good info from your blog articles.



    Take a look at my homepage professional negligence law

    ReplyDelete