{"id":5647,"date":"2022-12-03T00:01:30","date_gmt":"2022-12-03T08:01:30","guid":{"rendered":"https:\/\/c-for-dummies.com\/blog\/?p=5647"},"modified":"2022-11-26T11:23:56","modified_gmt":"2022-11-26T19:23:56","slug":"the-knights-tour","status":"publish","type":"post","link":"https:\/\/c-for-dummies.com\/blog\/?p=5647","title":{"rendered":"The Knight’s Tour"},"content":{"rendered":"

The task is truly complex: Navigating a knight around a chessboard, visiting each square but never the same square twice. It took me a while to code, and I don’t think my solution is particularly elegant, but it works.
\n
\nAs I wrote in last week’s Lesson<\/a>, my solution involves using the Warnsdorff\u2019s rule<\/a>. I found this heuristic to be solid enough that I didn’t need to use recursion: A simple loop counting all the squares in the chessboard is sufficient to solve the problem.<\/p>\n

Yes, using a loop instead of recursion frightened me, but the damn thing works, as seen by the animation in Figure 1.<\/p>\n

\"Animation,

Figure 1. An animation of my solution for the Knight’s Tour.<\/p><\/div>\n

In the figure, you see the Knight start at a random position. Values starting at zero plot the knight’s path around the chessboard, never visiting the same square twice. The final square is numbered 63.<\/p>\n

The first major change I made from the code in last week’s Lesson is to make the board[]<\/code> array (formerly in the chess_board()<\/em> function) external. While I’m not a fan of external variables, this move made calling the various functions a lot easier.<\/p>\n

Further, the chess_board()<\/em> function now has no arguments. It outputs the board setting numbers at the positions where the knight has already moved. An snprintf()<\/em> function outputs the knight’s movement values. If a square is set to -1, the initialization value, spaces are output.<\/p>\n

The moveto()<\/em> function is updated with a new test to confirm whether a square is occupied. The if-else<\/em> test looks like this:<\/p>\n

\r\nif( (r<0 || r>=SIZE) || (c<0 || c>=SIZE) )\r\n{\r\n    \/* square is out of bounds *\/<\/span>\r\n    m[x] = -1;\r\n}\r\nelse\r\n{\r\n    \/* plot position *\/<\/span>\r\n    m[x] = r * SIZE + c;\r\n    \/* confirm that square hasn't\r\n       already been occupied *\/<\/span>\r\n    if( board[m[x]] > -1 )\r\n        m[x] = -1;\r\n}<\/pre>\n
The if<\/em> test within the else<\/em> block – if( board[m[x]] > -1 )<\/code> – checks a square to see whether it’s been visited. If so, -1 is set, marking the square off-limits.<\/p>\n
The movecount()<\/em> function is unchanged.<\/p>\n
I added a new function, knightmove()<\/em> to relocate the knight. It contains statements previously found in the main()<\/em> function:<\/p>\n
\r\n\/* move the knight\r\n   s = square to move to\r\n   return the next square, the one\r\n   with the least number of next-moves *\/<\/span>\r\nint knight_move(int s)\r\n{\r\n    int x,lowest,newpos;\r\n    int moves[KM],next[KM],tally[KM];\r\n    struct plot {\r\n        int square;\r\n        int count;\r\n    } nextmove[KM];\r\n\r\n    \/* calculate where the piece can move *\/<\/span>\r\n    moveto(s,moves);\r\n    \/* calculate next moves *\/<\/span>\r\n    for( x=0; x<KM; x++ )\r\n    {\r\n        \/* only plot valid moves *\/<\/span>\r\n        if( moves[x] != -1 )\r\n        {\r\n            moveto(moves[x],next);\r\n            tally[x] = movecount(next);\r\n        }\r\n        else\r\n        {\r\n            \/* copy over the -1 *\/<\/span>\r\n            tally[x] = moves[x];\r\n        }\r\n    }\r\n\r\n    \/* build the structure to determine\r\n       where to move next *\/<\/span>\r\n    for( x=0; x<KM; x++ )\r\n    {\r\n        nextmove[x].square = moves[x];\r\n        nextmove[x].count = tally[x];\r\n    }\r\n\r\n    \/* move the knight to the lowest ranking position *\/<\/span>\r\n    lowest = 8;            \/* eight is the highest possible value *\/<\/span>\r\n    for( x=0; x<KM; x++ )\r\n    {\r\n        \/* find the square with the lowest count *\/<\/span>\r\n        if( nextmove[x].count<lowest && nextmove[x].count!=-1 )\r\n        {\r\n            lowest = nextmove[x].count;\r\n            newpos = nextmove[x].square;\r\n        }\r\n    }\r\n\r\n    return(newpos);\r\n}<\/pre>\n
This new function accomplishes three tasks:<\/p>\n
First, it builds the next[]<\/code> and tally[]<\/code> arrays to plot the knight’s next move.<\/p>\n
Second, it builds a structure to store potential moves, which is sorted.<\/p>\n
Third, it returns the desired square to move to, the one with the lowest count of succeeding moves (Warnsdorff\u2019s rule). No special decision is made when two squares have the same value.<\/p>\n
The updated main()<\/em> function initializes the board[]<\/code> array, randomly sets the knight’s starting location, then uses a for<\/em> loop to process all 64 squares:<\/p>\n
\r\n\/* move around the chess board *\/<\/span>\r\nfor( x=0; x<SIZE*SIZE; x++ )\r\n{\r\n    board[c] = x;\r\n    c = knight_move(c);\r\n    chess_board();\r\n    getchar();\r\n}<\/pre>\n
No recursion is used, as apparently my implementation of Warnsdorff\u2019s rule is sufficient to whisk the knight around the chessboard.<\/p>\n
Click here<\/a> to view the full code on GitHub. As I wrote earlier, I’m not proud of the code as it seems clunky to me. I tried to hone it further, making it more elegant. Alas, based on my approach a more poetic version of the program is beyond my reach.<\/p>\n
Even so, I was able to run the code on different size chessboards and, yes, it still works. I tried a 5-sided chessboard and a 12-sided chessboard. Thanks to Warnsdorff’s rule, the code properly propels the knight around the board, never hitting the same square twice.<\/p>\n
It’s been decades that I’ve known about this problem. I’m delighted that I’ve solved it. I’d still like to explore the Knight’s Tour concept, which I may return to someday. For now, it was fun.<\/p>\n","protected":false},"excerpt":{"rendered":"
Send a knight around a chessboard, visiting each square without repeating the same square twice. Yup, it can be done. Continue reading →<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[2],"tags":[],"class_list":["post-5647","post","type-post","status-publish","format-standard","hentry","category-main"],"_links":{"self":[{"href":"https:\/\/c-for-dummies.com\/blog\/index.php?rest_route=\/wp\/v2\/posts\/5647","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/c-for-dummies.com\/blog\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/c-for-dummies.com\/blog\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/c-for-dummies.com\/blog\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/c-for-dummies.com\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=5647"}],"version-history":[{"count":5,"href":"https:\/\/c-for-dummies.com\/blog\/index.php?rest_route=\/wp\/v2\/posts\/5647\/revisions"}],"predecessor-version":[{"id":5666,"href":"https:\/\/c-for-dummies.com\/blog\/index.php?rest_route=\/wp\/v2\/posts\/5647\/revisions\/5666"}],"wp:attachment":[{"href":"https:\/\/c-for-dummies.com\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=5647"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/c-for-dummies.com\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=5647"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/c-for-dummies.com\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=5647"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}