# Untitled

a guest
Nov 1st, 2015
128
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. #ifndef _LIBS_NAMESPACES
2.
3. #include <stdlib.h>
4. #include <iostream>
5. #include <iomanip>
6.
7. using namespace std;
8.
9. #endif // _LIBS_NAMESPACES
10.
11. #ifndef _LOCAL_CONSTANTS
12.
14. #define START_ROW 0
15. #define START_COL 0
16.
17. #define TOP_LEFT(row, col) row - 2, col - 1
18. #define TOP_RIGHT(row, col) row - 2, col + 1
19. #define BOT_LEFT(row, col) row + 2, col - 1
20. #define BOT_RIGHT(row, col) row + 2, col + 1
21. #define LEFT_TOP(row, col) row - 1, col - 2
22. #define LEFT_BOT(row, col) row + 1, col - 2
23. #define RIGHT_TOP(row, col) row - 1, col + 2
24. #define RIGHT_BOT(row, col) row + 1, col + 2
25.
26. #endif // _LOCAL_CONSTANTS
27.
28. #ifndef _STRUCTS_ENUMS
29.
30. typedef enum
31. {
32.     eTopLeft,
33.     eTopRight,
34.     eBotLeft,
35.     eBotRight,
36.     eRightTop,
37.     eRightBot,
38.     eLeftTop,
39.     eLeftBot,
40.     eInvalidMove
41. } Move;
42.
43. #endif // _STRUCTS_ENUMS
44.
45. #ifndef _FUNCTION_PROTOTYPES
46.
47. void CalculateKnightsTour(int startRow, int startCol);
48. bool ProcessMove(Move nextMove, int * row, int * col);
49. Move FindOptimalMoveChoice(int row, int col);
50. int CalculatePossibleMoves(int row, int col);
51. bool IsPossibleMove(int row, int col);
52. bool IsFreeCell(int row, int col);
53. void ProcessInput();
54. void PrintBoard();
55. void InitializeResources();
56. void DisposeResources();
57.
58. #endif // _FUNCTION_PROTOTYPES
59.
60. #ifndef _LOCAL_DATA
61.
62. static int ** board;
63.
64. static int boardSize;
65. static int currentStep = 1;
66.
67. #endif // _LOCAL_DATA
68.
69. #ifndef _MAIN
70.
71. int main()
72. {
73.     ProcessInput();
74.     InitializeResources();
75.     CalculateKnightsTour(START_ROW, START_COL);
76.     PrintBoard();
77.
78.     DisposeResources();
79.
80.     return 0;
81. }
82.
83. #endif // _MAIN
84.
85. #ifndef _ALGO_IMPLEMENTATION
86.
87. void CalculateKnightsTour(int startRow, int startCol)
88. {
89.     int currentRow = startRow;
90.     int currentCol = startCol;
91.
92.     bool resultFound;
93.
94.     do
95.     {
96.         resultFound = false;
97.         Move nextMove = FindOptimalMoveChoice(currentRow, currentCol);
98.         resultFound = ProcessMove(nextMove, &currentRow, &currentCol);
99.
100.     } while(resultFound);
101. }
102.
103. bool ProcessMove(Move nextMove, int * row, int * col)
104. {
105.     switch (nextMove)
106.     {
107.         case eTopLeft:
108.             (*row) -= 2;
109.             (*col) -= 1;
110.             break;
111.         case eTopRight:
112.             (*row) -= 2;
113.             (*col) += 1;
114.             break;
115.         case eBotLeft:
116.             (*row) += 2;
117.             (*col) -= 1;
118.             break;
119.         case eBotRight:
120.             (*row) += 2;
121.             (*col) += 1;
122.             break;
123.         case eLeftTop:
124.             (*row) -= 1;
125.             (*col) -= 2;
126.             break;
127.         case eLeftBot:
128.             (*row) += 1;
129.             (*col) -= 2;
130.             break;
131.         case eRightTop:
132.             (*row) -= 1;
133.             (*col) += 2;
134.             break;
135.         case eRightBot:
136.             (*row) += 1;
137.             (*col) += 2;
138.             break;
139.         default:
140.             return false;
141.     }
142.
143.     board[(*row)][(*col)] = ++currentStep;
144.     return true;
145. }
146.
147. // Implementing the Warnsdorf's rule
148. Move FindOptimalMoveChoice(int row, int col)
149. {
150.     int minMoves = INT_MAX;
151.     int previousMoves = INT_MAX;
152.     Move nextMove = eInvalidMove;
153.
154.     // Top right
155.     minMoves = min(minMoves, CalculatePossibleMoves(TOP_RIGHT(row, col)));
156.     nextMove = minMoves != previousMoves ? eTopRight : nextMove;
157.     previousMoves = minMoves;
158.
159.     // Right top
160.     minMoves = min(minMoves, CalculatePossibleMoves(RIGHT_TOP(row, col)));
161.     nextMove = minMoves != previousMoves ? eRightTop : nextMove;
162.     previousMoves = minMoves;
163.
164.     // Right bot
165.     minMoves = min(minMoves, CalculatePossibleMoves(RIGHT_BOT(row, col)));
166.     nextMove = minMoves != previousMoves ? eRightBot : nextMove;
167.     previousMoves = minMoves;
168.
169.     // Bot right
170.     minMoves = min(minMoves, CalculatePossibleMoves(BOT_RIGHT(row, col)));
171.     nextMove = minMoves != previousMoves ? eBotRight : nextMove;
172.     previousMoves = minMoves;
173.
174.     // Bot left
175.     minMoves = min(minMoves, CalculatePossibleMoves(BOT_LEFT(row, col)));
176.     nextMove = minMoves != previousMoves ? eBotLeft : nextMove;
177.     previousMoves = minMoves;
178.
179.     // Left bot
180.     minMoves = min(minMoves, CalculatePossibleMoves(LEFT_BOT(row, col)));
181.     nextMove = minMoves != previousMoves ? eLeftBot : nextMove;
182.     previousMoves = minMoves;
183.
184.     // Left top
185.     minMoves = min(minMoves, CalculatePossibleMoves(LEFT_TOP(row, col)));
186.     nextMove = minMoves != previousMoves ? eLeftTop : nextMove;
187.     previousMoves = minMoves;
188.
189.     // Top left
190.     minMoves = min(minMoves, CalculatePossibleMoves(TOP_LEFT(row, col)));
191.     nextMove = minMoves != previousMoves ? eTopLeft : nextMove;
192.     previousMoves = minMoves;
193.
194.     return nextMove;
195. }
196.
197. int CalculatePossibleMoves(int row, int col)
198. {
199.     if (!IsPossibleMove(row, col) || !IsFreeCell(row, col))
200.     {
201.         return INT_MAX;
202.     }
203.
204.     int cnt = 0;
205.
206.     if (IsPossibleMove(TOP_RIGHT(row, col)) && IsFreeCell(TOP_RIGHT(row, col)))
207.     {
208.         ++cnt;
209.     }
210.
211.     if (IsPossibleMove(TOP_LEFT(row, col)) && IsFreeCell(TOP_LEFT(row, col)))
212.     {
213.         ++cnt;
214.     }
215.
216.     if (IsPossibleMove(BOT_RIGHT(row, col)) && IsFreeCell(BOT_RIGHT(row, col)))
217.     {
218.         ++cnt;
219.     }
220.
221.     if (IsPossibleMove(BOT_LEFT(row, col)) && IsFreeCell(BOT_LEFT(row, col)))
222.     {
223.         ++cnt;
224.     }
225.
226.     if (IsPossibleMove(RIGHT_TOP(row, col)) && IsFreeCell(RIGHT_TOP(row, col)))
227.     {
228.         ++cnt;
229.     }
230.
231.     if (IsPossibleMove(RIGHT_BOT(row, col)) && IsFreeCell(RIGHT_BOT(row, col)))
232.     {
233.         ++cnt;
234.     }
235.
236.     if (IsPossibleMove(LEFT_TOP(row, col)) && IsFreeCell(LEFT_TOP(row, col)))
237.     {
238.         ++cnt;
239.     }
240.
241.     if (IsPossibleMove(LEFT_BOT(row, col)) && IsFreeCell(LEFT_BOT(row, col)))
242.     {
243.         ++cnt;
244.     }
245.
246.     return cnt;
247. }
248.
249. bool IsFreeCell(int row, int col)
250. {
251.     return board[row][col] == 0;
252. }
253.
254. bool IsPossibleMove(int row, int col)
255. {
256.     return row >= 0 &&
257.            row < boardSize &&
258.            col >= 0 &&
259.            col < boardSize;
260. }
261.
262. #endif // _ALGO_IMPLEMENTATION
263.
264. #ifndef _IO_PROCESSING
265.
266. void ProcessInput()
267. {
268.     cin >> boardSize;
269. }
270.
271. void PrintBoard()
272. {
273.     for (int row = 0; row < boardSize; ++row)
274.     {
275.         for (int col = 0; col < boardSize; ++col)
276.         {
277.             cout << setfill(' ') << setw(PAD_LENGTH) << board[row][col];
278.         }
279.
280.         cout << endl;
281.     }
282. }
283.
284. #endif // _IO_PROCESSING
285.
286. #ifndef _RESOURCES_MANAGEMENT
287.
288. void InitializeResources()
289. {
290.     board = (int**)malloc(sizeof(int*) * boardSize);
291.
292.     for (int row = 0; row < boardSize; ++row)
293.     {
294.         board[row] = (int*)malloc(sizeof(int) * boardSize);
295.
296.         for (int col = 0; col < boardSize; ++col)
297.         {
298.             board[row][col] = 0;
299.         }
300.     }
301.
302.     board[0][0] = 1;
303. }
304.
305. void DisposeResources()
306. {
307.     for (int row = 0; row < boardSize; ++row)
308.     {
309.         free(board[row]);
310.     }
311.
312.     free(board);
313. }
314.
315. #endif // _RESOURCES_MANAGEMENT