Posted By

greymatters on 09/13/14


Tagged

calendar path tour cycle chess knights Knight puzzles hamiltonian


Versions (?)

KnightsTour.java


 / Published in: Java
 

This is a Java class for solving a knight's tour via Hamiltonian path and Hamiltonian cycle algorithms.

  1. package testknight;
  2.  
  3. import java.util.Arrays;
  4.  
  5. /**
  6.  *
  7.  * @author piguy
  8.  */
  9.  
  10. // Recommended reading on basics of graphs:
  11. // http://www.seas.gwu.edu/~simhaweb/alg/lectures/module7/module7.html
  12. //
  13. public class KnightsTour {
  14. private int[][] board;
  15. private int[] vertex;
  16. private int[][] adjMatrix;
  17. private int[] path;
  18. private int count, V;
  19. private boolean hasPrinted;
  20.  
  21. // Used in calendar match routine variation
  22. // Highest number of date-to-position matches
  23. private int calMatchRecord = 0;
  24.  
  25. // Create standard 8 by 8 chessboard using default constructor
  26. // No need to test for rectangular arrays, as it is being built rectangular
  27. // 1 denotes square onto which knight can be moved
  28. // 0 denotes square onto which knight cannot be moved (Not used in default construtor)
  29. //
  30. // board[][] is an 8 by 8 array of 1s,
  31. // denoting shape of the board
  32. //
  33. // vertex[X] = N, where X is the Xth legal square and
  34. // N is the Nth square in the shape[][] array,
  35. // starting from 0 in the upper left, reading across, THEN down.
  36. //
  37. // adjMatrix[][] (adjacency matrix) is an array used to denote which
  38. // vertices are adjacent to which other vertices
  39. // Note: Knight's Tour is always an
  40. // undirected graph with no self-loops
  41. // References:
  42. // http://en.wikipedia.org/wiki/Adjacency_matrix
  43. // http://mathworld.wolfram.com/AdjacencyMatrix.html
  44. public KnightsTour() {
  45. board = new int[8][8];
  46. vertex = new int[64];
  47. for (int i=0; i < 8; i++) {
  48. for (int j=0; j < 8; j++) {
  49. // Allow knight to be on this square
  50. board[i][j] = 1;
  51. // Record the location of this vertex (legal square for a knight)
  52. vertex[(8 * i) + j] = ((8 * i) + j);
  53. }
  54. }
  55.  
  56. // Build adjacency matrix
  57. //
  58. // Declare size of adjacency matrix
  59. adjMatrix = new int[vertex.length][vertex.length];
  60.  
  61. // Test for adjacency
  62. // between a current spot, vertex i whose coordinates are (x, y)
  63. // and a second test spot, vertex j whose coordinates are (x, y)
  64. for (int i=0; i < vertex.length; i++) {
  65. for (int j=0; j < vertex.length; j++) {
  66. // Convert vertex i's location into x and y coordinates
  67. int curSpotX = (int)(Math.floor(vertex[i] / (board[0].length)));
  68. int curSpotY = (vertex[i] % (board[0].length));
  69. // Convert vertex j's location into x and y coordinates
  70. int testSpotX = (int)(Math.floor(vertex[j] / (board[0].length)));
  71. int testSpotY = (vertex[j] % (board[0].length));
  72. // Calculate the absolute difference in x coordinates
  73. int xDiff = Math.abs(testSpotX - curSpotX);
  74. // Calculate the absolute difference in y coordinates
  75. int yDiff = Math.abs(testSpotY - curSpotY);
  76. // Is one difference 2 and the other difference 1?
  77. if (((xDiff == 2) && (yDiff == 1)) || ((xDiff == 1) && (yDiff == 2))) {
  78. // If so, consider them adjacent
  79. adjMatrix[i][j] = 1;
  80. }
  81. else {
  82. // If not, don't consider them adjacent
  83. adjMatrix[i][j] = 0;
  84. }
  85. }
  86. }
  87. }
  88.  
  89. // Create custom-shaped board using 2d integer array via custom constructor
  90. // "shape" is passed from 2d integer array
  91. // 1 denotes square onto which knight can be moved
  92. // 0 denotes square onto which knight cannot be moved
  93. //
  94. // board[][] is a copy of shape[][]
  95. //
  96. // vertex[X] = N, where X is the Xth legal square and
  97. // N is the Nth square in the board[][] array,
  98. // starting from 0 in the upper left, reading across, THEN down.
  99. //
  100. // adjMatrix[][] (adjacency matrix) is a 2D array used to denote which
  101. // vertices are adjacent to which other vertices
  102. // Note: Knight's Tour is always an
  103. // undirected graph with no self-loops
  104. // References:
  105. // http://en.wikipedia.org/wiki/Adjacency_matrix
  106. // http://mathworld.wolfram.com/AdjacencyMatrix.html
  107. public KnightsTour(int[][] shape) {
  108. // Test whether integer array is rectangular
  109. //
  110. // Get the length of the first row
  111. int width = shape[0].length;
  112. // Get height of array
  113. int height = shape.length;
  114. boolean passTest = true;
  115. for (int i = 1; i < height; i++) {
  116. // Is the length of this row different from the first row?
  117. if (shape[i].length != width) {
  118. // Mark the test as having failed
  119. passTest = false;
  120. break;
  121. }
  122. }
  123. if (passTest == false) {
  124. // If board is NOT rectangular, notify user and end program
  125. System.out.println("Error! Shape array is not rectangular!");
  126. System.exit(0);
  127. }
  128.  
  129. // Declare size of board
  130. board = new int[height][width];
  131.  
  132. // Count # of vertices for later array declaration
  133. int vertexCounter = 0;
  134. // Since board is rectangular, make it a new KnightsTourOrig object
  135. for (int i=0; i < height; i++) {
  136. for (int j=0; j < width; j++) {
  137. // Copy custom shape into board
  138. board[i][j] = shape[i][j];
  139. if (shape[i][j] == 1) {
  140. // If this square is a legal move for the knight,
  141. // add 1 to the vertex counter
  142. vertexCounter++;
  143. }
  144. }
  145. }
  146.  
  147. // Use number of vertices to declare vertex array
  148. vertex = new int[vertexCounter];
  149.  
  150. // Create list of vertices (squares onto which the knight can move)
  151. // starting with 0
  152. int vertexInc = 0;
  153. for (int i=0; i < height; i++) {
  154. for (int j=0; j < width; j++) {
  155. // Is this a legal square upon which the knight can move?
  156. if (board[i][j] == 1) {
  157. // Record the location of this vertex (legal square for a knight)
  158. vertex[vertexInc] = (width * i) + j;
  159. // Increment array counter for next vertex
  160. vertexInc++;
  161. }
  162. }
  163. }
  164.  
  165. // Build adjacency matrix
  166. //
  167. // Declare size of adjacency matrix
  168. adjMatrix = new int[vertex.length][vertex.length];
  169.  
  170. // Test for adjacency
  171. // between a current spot, vertex i whose coordinates are (x, y)
  172. // and a second test spot, vertex j whose coordinates are (x, y)
  173. for (int i=0; i < vertex.length; i++) {
  174. for (int j=0; j < vertex.length; j++) {
  175. // Convert vertex i's location into x and y coordinates
  176. int curSpotX = (int)(Math.floor(vertex[i] / (board[0].length)));
  177. int curSpotY = (vertex[i] % (board[0].length));
  178. // Convert vertex j's location into x and y coordinates
  179. int testSpotX = (int)(Math.floor(vertex[j] / (board[0].length)));
  180. int testSpotY = (vertex[j] % (board[0].length));
  181. // Calculate the absolute difference in x coordinates
  182. int xDiff = Math.abs(testSpotX - curSpotX);
  183. // Calculate the absolute difference in y coordinates
  184. int yDiff = Math.abs(testSpotY - curSpotY);
  185. // Is one difference 2 and the other difference 1?
  186. if (((xDiff == 2) && (yDiff == 1)) || ((xDiff == 1) && (yDiff == 2))) {
  187. // If so, consider them adjacent
  188. adjMatrix[i][j] = 1;
  189. }
  190. else {
  191. // If not, don't consider them adjacent
  192. adjMatrix[i][j] = 0;
  193. }
  194. }
  195. }
  196. }
  197.  
  198. // return number of vertices on board
  199. public int getNumOfVertices() {
  200. return vertex.length;
  201. }
  202.  
  203. // Display board shape
  204. public void displayBoard() {
  205. int rows = board.length;
  206. int cols = board[0].length;
  207. for (int i=0; i < rows; i++) {
  208. for (int j=0; j < cols; j++) {
  209. if (board[i][j] == 1) {
  210. System.out.print("X ");
  211. }
  212. else {
  213. System.out.print(" ");
  214. }
  215. }
  216. System.out.println();
  217. }
  218. }
  219.  
  220. // Display adjMatrix contents
  221. public void displayAdjMatrix() {
  222. int n = vertex.length;
  223. for (int i=0; i < n; i++) {
  224. for (int j=0; j < n; j++) {
  225. System.out.print(adjMatrix[i][j]);
  226. }
  227. System.out.println();
  228. }
  229. }
  230.  
  231. // Backtracking algorithm to
  232. // find 1 closed Knight's Tour
  233. // AKA a Hamiltonian cycle
  234. public void findAClosedKnightsTour() {
  235. // Variable used to ensure only one solution is printed
  236. hasPrinted = false;
  237. // Get size of adjacency matrix
  238. V = adjMatrix.length;
  239. // Set path to size of adjacency matrix
  240. path = new int[V];
  241.  
  242. // Fill path with -1s to start
  243. Arrays.fill(path, -1);
  244.  
  245. // Use 0 as starting point
  246. // Since we're looking for a cycle
  247. // It doesn't matter which point is chosen
  248. path[0] = 0;
  249.  
  250. if (singleTourUtil(1, "closed") == false) {
  251. System.out.println("No closed Knight's Tours found on this board.");
  252. }
  253. }
  254.  
  255. // Backtracking algorithm to
  256. // find 1 closed Knight's Tour
  257. // starting at a given vertex
  258. // AKA a Hamiltonian cycle
  259. public void findAClosedKnightsTour(int start) {
  260. // Variable used to ensure only one solution is printed
  261. hasPrinted = false;
  262. // Get size of adjacency matrix
  263. V = adjMatrix.length;
  264. // Set path to size of adjacency matrix
  265. path = new int[V];
  266.  
  267. // Fill path with -1s to start
  268. Arrays.fill(path, -1);
  269.  
  270. // Use 0 as starting point
  271. // Since we're looking for a cycle
  272. // It doesn't matter which point is chosen
  273. path[0] = start;
  274.  
  275. if (singleTourUtil(1, "closed") == false) {
  276. System.out.println("No closed Knight's Tours found on this board starting at vertex #" + start + ".");
  277. }
  278. }
  279.  
  280. // Backtracking algorithm to
  281. // find all closed Knight's Tours
  282. // AKA Hamiltonian cycles
  283. public void findAllClosedKnightsTours() {
  284. // Clear count of open Knight's Tour paths
  285. count = 0;
  286. // Get size of adjacency matrix
  287. V = adjMatrix.length;
  288. // Set path to size of adjacency matrix
  289. path = new int[V];
  290.  
  291. // Fill path with -1s to start
  292. Arrays.fill(path, -1);
  293.  
  294. // Use 0 as starting point
  295. // Since we're looking for a cycle
  296. // It doesn't matter which point is chosen
  297. path[0] = 0;
  298.  
  299. multiToursUtil(1, "closed");
  300. if (count != 0) {
  301. System.out.println("Found " + count + " closed Knight's Tours on this board.");
  302. }
  303. else {
  304. System.out.println("No closed Knight's Tours found on this board.");
  305. }
  306. }
  307.  
  308. // Backtracking algorithm to
  309. // find all closed Knight's Tours
  310. // starting at a given vertex
  311. // AKA Hamiltonian cycles
  312. public void findAllClosedKnightsTours(int start) {
  313. // Clear count of open Knight's Tour paths
  314. count = 0;
  315. // Get size of adjacency matrix
  316. V = adjMatrix.length;
  317. // Set path to size of adjacency matrix
  318. path = new int[V];
  319.  
  320. // Fill path with -1s to start
  321. Arrays.fill(path, -1);
  322.  
  323. // Use 0 as starting point
  324. // Since we're looking for a cycle
  325. // It doesn't matter which point is chosen
  326. path[0] = start;
  327.  
  328. multiToursUtil(1, "closed");
  329. if (count != 0) {
  330. System.out.println("Found " + count + " closed Knight's Tours on this board starting at vertex #" + start + ".");
  331. }
  332. else {
  333. System.out.println("No closed Knight's Tours found on this board starting at vertex #" + start + ".");
  334. }
  335. }
  336.  
  337. // Backtracking algorithm to
  338. // find 1 open Knight's Tour
  339. // starting at a given vertex
  340. // AKA a Hamiltonian path
  341. public void findAnOpenKnightsTour(int start) {
  342. // Variable used to ensure only one solution is printed
  343. hasPrinted = false;
  344. // Get size of adjacency matrix
  345. V = adjMatrix.length;
  346. // Set path to size of adjacency matrix
  347. path = new int[V];
  348.  
  349. // Fill path with -1s to start
  350. Arrays.fill(path, -1);
  351.  
  352. // Set starting point
  353. path[0] = start;
  354.  
  355. if (singleTourUtil(1, "open") == false) {
  356. System.out.println("No open Knight's Tours found on this board starting at vertex #" + start + ".");
  357. }
  358. }
  359.  
  360. // Backtracking algorithm to
  361. // find all open Knight's Tours
  362. // starting at a given vertex
  363. // AKA Hamiltonian paths
  364. public void findAllOpenKnightsTours(int start) {
  365. // Clear count of open Knight's Tour paths
  366. count = 0;
  367. // Get size of adjacency matrix
  368. V = adjMatrix.length;
  369. // Set path to size of adjacency matrix
  370. path = new int[V];
  371.  
  372. // Fill path with -1s to start
  373. Arrays.fill(path, -1);
  374.  
  375. // Set starting point
  376. path[0] = start;
  377.  
  378. multiToursUtil(1, "open");
  379. if (count != 0) {
  380. System.out.println("Found " + count + " open Knight's Tours on this board starting at vertex #" + start + ".");
  381. }
  382. else {
  383. System.out.println("No open Knight's Tours found on this board starting at vertex #" + start + ".");
  384. }
  385. }
  386.  
  387. // Backtracking algorithm to
  388. // find all Knight's Tours starting
  389. // at a given vertex
  390. // AKA Hamiltonian paths AND cycles
  391. public void findAllKnightsTours(int start) {
  392. // Clear count of open Knight's Tour paths
  393. count = 0;
  394. // Get size of adjacency matrix
  395. V = adjMatrix.length;
  396. // Set path to size of adjacency matrix
  397. path = new int[V];
  398.  
  399. // Fill path with -1s to start
  400. Arrays.fill(path, -1);
  401.  
  402. // Set starting point
  403. path[0] = start;
  404.  
  405. multiToursUtil(1, "all");
  406. if (count != 0) {
  407. System.out.println("Found " + count + " Knight's Tours on this board starting at vertex #" + start + ".");
  408. }
  409. else {
  410. System.out.println("No Knight's Tours found on this board starting at vertex #" + start + ".");
  411. }
  412. }
  413.  
  414. // Recursive backtracking routine to
  415. // build and check paths for the first
  416. // Knights Tour it can find
  417. // "open" = open Knight's Tour (Hamiltonian path)
  418. // "closed" = closed Knight's Tour (Hamiltonian cycle)
  419. // "all" = either an open or closed Knight's Tour
  420. private boolean singleTourUtil(int pos, String type) {
  421. // Are all vertices included in the cycle?
  422. if (pos == V) {
  423. // Can you move from the final position to the start?
  424. if (adjMatrix[path[pos-1]][path[0]] == 1) {
  425. if (((type.equals("closed")) || (type.equals("all"))) && (hasPrinted == false)) {
  426. displayKnightsTour("CLOSED TOUR:");
  427. hasPrinted = true;
  428. return true;
  429. }
  430. else {
  431. return false;
  432. }
  433. }
  434. else {
  435. if (((type.equals("open")) || (type.equals("all"))) && (hasPrinted == false)) {
  436. displayKnightsTour("OPEN TOUR:");
  437. hasPrinted = true;
  438. return true;
  439. }
  440. else {
  441. return false;
  442. }
  443. }
  444. }
  445.  
  446. // Try different vertices as a next candidate in Hamiltonian Cycle
  447. for (int v = 0; v < V; v++) {
  448. // Can this vertex be added to the path?
  449. if (isSafe(v, pos)) {
  450. // Add this vertex to the path
  451. path[pos] = v;
  452.  
  453. // Recur to construct the rest of the path
  454. if (singleTourUtil(pos+1, type) == true) {
  455. return true;
  456. }
  457.  
  458. // If program makes it here, adding vertex v
  459. // didn't lead to a solution, so remove it
  460. path[pos] = -1;
  461. }
  462. }
  463.  
  464. // If program makes it here, then
  465. // no vertex can be added
  466. return false;
  467. }
  468.  
  469. // Recursive backtracking routine to
  470. // build and check paths for multiple
  471. // Knights Tours
  472. // "open" = open Knight's Tour (Hamiltonian path)
  473. // "closed" = closed Knight's Tour (Hamiltonian cycle)
  474. // "all" = both open and closed Knight's Tours
  475. private void multiToursUtil(int pos, String type) {
  476. // Are all veritces included in the cycle?
  477. if (pos == V) {
  478. // Can you move from the final position to the start?
  479. if (adjMatrix[path[pos-1]][path[0]] == 1) {
  480. if ((type.equals("closed")) || (type.equals("all"))) {
  481. count++;
  482. if (type.equals("all")) {
  483. displayKnightsTour("CLOSED:");
  484. }
  485. else {
  486. displayKnightsTour("");
  487. }
  488. }
  489. return;
  490. }
  491. else {
  492. if ((type.equals("open")) || (type.equals("all"))) {
  493. count++;
  494. if (type.equals("all")) {
  495. displayKnightsTour("OPEN:");
  496. }
  497. else {
  498. displayKnightsTour("");
  499. }
  500. }
  501. return;
  502. }
  503. }
  504.  
  505. // Try different vertices as a next candidate in Hamiltonian Cycle
  506. for (int v = 0; v < V; v++) {
  507. // Can this vertex be added to the path?
  508. if (isSafe(v, pos)) {
  509. // Add this vertex to the path
  510. path[pos] = v;
  511.  
  512. // Recur to construct the rest of the path
  513. multiToursUtil(pos + 1, type);
  514.  
  515. // If program makes it here, adding vertex v
  516. // didn't lead to a solution, so remove it
  517. path[pos] = -1;
  518. }
  519. }
  520. }
  521.  
  522. // Check whether vertex v can be added
  523. // at index pos in the path constructed so far
  524. // Used in tour-finding algorithms
  525. private boolean isSafe(int v, int pos) {
  526. // Is this vertex NOT adjacent to the previously added vertex?
  527. if (adjMatrix[path[pos-1]][ v ] == 0) {
  528. return false;
  529. }
  530.  
  531. // Loop to check whether vertex has already been included
  532. for (int i = 0; i < pos; i++) {
  533. // If vertex is already in path
  534. if (path[i] == v) {
  535. // report that it isn't safe
  536. return false;
  537. }
  538. }
  539.  
  540. // vertex passed all the tests
  541. return true;
  542. }
  543.  
  544. private void displayKnightsTour(String type) {
  545. // Get and display row and column information
  546. int rows = board.length;
  547. int cols = board[0].length;
  548. int temp1 = 0;
  549. int temp2 = 0;
  550. // If needed, add label to tour
  551. // Currently used to denoted whether
  552. // a tour is open or closed
  553. if (!type.equals("")) {
  554. System.out.println(type);
  555. }
  556. for (int i=0; i < rows; i++) {
  557. for (int j=0; j < cols; j++) {
  558. int n = (cols * i) + j;
  559. // Is it legal for the knight to be on this square?
  560. if (board[i][j] == 1) {
  561. // Find out which vertex this is
  562. for (int k = 0; k < vertex.length; k++) {
  563. if (vertex[k] == n) {
  564. // Save the vertex as temp1
  565. temp1 = k;
  566. break;
  567. }
  568. }
  569. // Find the index of this vertex in path[]
  570. for (int k = 0; k < path.length; k++) {
  571. if (path[k] == temp1) {
  572. // Save the index as temp2
  573. temp2 = k;
  574. break;
  575. }
  576. }
  577. // Display move as starting from 1, not 0
  578. System.out.printf("%2d", (temp2 + 1));
  579. System.out.print(" ");
  580. }
  581. else {
  582. System.out.print(" ");
  583. }
  584. }
  585. System.out.println();
  586. }
  587. System.out.println();
  588. }
  589.  
  590.  
  591. // Beyond here are various methods
  592. // which can be deleted, if desired
  593.  
  594.  
  595. // Find tours with matches to their dates
  596. // Inspired by:
  597. // http://forums.xkcd.com/viewtopic.php?f=3&t=62580
  598.  
  599. // Backtracking algorithm to
  600. // find all Knight's Tours starting
  601. // at a given vertex
  602. // AKA Hamiltonian paths (including Hamiltonian cycles)
  603. public void findAllKnightsToursCalendars(int start) {
  604. // Clear count of open Knight's Tour paths
  605. count = 0;
  606. // Get size of adjacency matrix
  607. V = adjMatrix.length;
  608. // Set path to size of adjacency matrix
  609. path = new int[V];
  610.  
  611. // Fill path with -1s to start
  612. Arrays.fill(path, -1);
  613.  
  614. // Set starting point
  615. path[0] = start;
  616.  
  617. multiToursCalUtil(1, "all");
  618. if (count != 0) {
  619. System.out.println("Found " + count + " Knight's Tours on this board starting at vertex #" + start + ".");
  620. }
  621. else {
  622. System.out.println("No Knight's Tours found on this board starting at vertex #" + start + ".");
  623. }
  624. }
  625.  
  626. // Recursive backtracking routine to
  627. // build and check paths for multiple
  628. // Knights Tours
  629. // "open" = open Knight's Tour (Hamiltonian path)
  630. // "closed" = closed Knight's Tour (Hamiltonian cycle)
  631. // "all" = both open and closed Knight's Tours
  632. private void multiToursCalUtil(int pos, String type) {
  633. // Are all veritces included in the cycle?
  634. if (pos == V) {
  635. // Can you move from the final position to the start?
  636. if (adjMatrix[path[pos-1]][path[0]] == 1) {
  637. if ((type.equals("closed")) || (type.equals("all"))) {
  638. count++;
  639. if (type.equals("all")) {
  640. displayKnightsTourCalendar("CLOSED:");
  641. }
  642. else {
  643. displayKnightsTourCalendar("");
  644. }
  645. }
  646. return;
  647. }
  648. else {
  649. if ((type.equals("open")) || (type.equals("all"))) {
  650. count++;
  651. if (type.equals("all")) {
  652. displayKnightsTourCalendar("OPEN:");
  653. }
  654. else {
  655. displayKnightsTourCalendar("");
  656. }
  657. }
  658. return;
  659. }
  660. }
  661.  
  662. // Try different vertices as a next candidate in Hamiltonian Cycle
  663. for (int v = 0; v < V; v++) {
  664. // Can this vertex be added to the path?
  665. if (isSafe(v, pos)) {
  666. // Add this vertex to the path
  667. path[pos] = v;
  668.  
  669. // Recur to construct the rest of the path
  670. multiToursCalUtil(pos + 1, type);
  671.  
  672. // If program makes it here, adding vertex v
  673. // didn't lead to a solution, so remove it
  674. path[pos] = -1;
  675. }
  676. }
  677. }
  678.  
  679. private void displayKnightsTourCalendar(String type) {
  680. // Get and display row and column information
  681. int rows = board.length;
  682. int cols = board[0].length;
  683. int temp1 = 0;
  684. int temp2 = 0;
  685. // calOffset = Code for day of week of the 1st
  686. // Code: 0=Sunday, 1=Monday, 2=Tuesday, 3=Wednesday
  687. // 4=Thursday, 5=Friday, 6=Saturday,
  688. int calOffset = 3;
  689. // Counter for number of date-to-position matches
  690. int calMatchCounter = 0;
  691. // If needed, add label to tour
  692. // Currently used to denoted whether
  693. // a tour is open or closed
  694. if (!type.equals("")) {
  695. System.out.println(type);
  696. }
  697. for (int i=0; i < rows; i++) {
  698. for (int j=0; j < cols; j++) {
  699. int n = (cols * i) + j;
  700. // Is it legal for the knight to be on this square?
  701. if (board[i][j] == 1) {
  702. // Find out which vertex this is
  703. for (int k = 0; k < vertex.length; k++) {
  704. if (vertex[k] == n) {
  705. // Save the vertex as temp1
  706. temp1 = k;
  707. break;
  708. }
  709. }
  710. // Find the index of this vertex in path[]
  711. for (int k = 0; k < path.length; k++) {
  712. if (path[k] == temp1) {
  713. // Save the index as temp2
  714. temp2 = k;
  715. break;
  716. }
  717. }
  718. // Display move as starting from 1, not 0
  719. System.out.printf("%2d", (temp2 + 1));
  720. // Do date and move number match?
  721. if ((temp2 + calOffset) == n) {
  722. calMatchCounter++;
  723. System.out.print("* ");
  724. }
  725. else {
  726. System.out.print(" ");
  727. }
  728. }
  729. else {
  730. System.out.print(" ");
  731. }
  732. }
  733. System.out.println();
  734. }
  735. // Print out number of date-to-move matches
  736. System.out.println(calMatchCounter + " matches.");
  737. // Determine whether this is a record
  738. if (calMatchCounter > calMatchRecord) {
  739. calMatchRecord = calMatchCounter;
  740. System.out.println(calMatchRecord + " is a new record!");
  741. }
  742. System.out.println();
  743. }
  744.  
  745. // Return the number of highest matches
  746. // of moves and dates
  747. public int getMostMatches() {
  748. return calMatchRecord;
  749. }
  750. }

Report this snippet  

You need to login to post a comment.