+/* Recursively try all possible moves, starting from (y,x) */
+static int
+recurBack(SQUARES squares, int y, int x, int total)
+{
+ int longest = total;
+ int best_x = x;
+ int best_y = y;
+ int result;
+
+ if (total < maxmoves) {
+ int try_x, try_y;
+ unsigned k;
+
+ for (k = 0; k < MAX_OFFSET; k++) {
+ try_x = x + offsets[k].x;
+ try_y = y + offsets[k].y;
+ if (isUnusedYX(squares, try_y, try_x)) {
+ ++test_test;
+ squares[try_y][try_x] = total + 1;
+ result = recurBack(squares, try_y, try_x, total + 1);
+ if (result > longest) {
+ longest = result;
+ best_x = try_x;
+ best_y = try_y;
+ }
+ if (result >= maxmoves)
+ break;
+ squares[try_y][try_x] = 0; /* allow retry... */
+ }
+ }
+ }
+
+ result = total;
+ if (longest > total) {
+ result = longest;
+ squares[best_y][best_x] = total + 1;
+ (void) recurBack(squares, best_y, best_x, total + 1);
+ if (result < maxmoves)
+ squares[best_y][best_x] = 0;
+ }
+
+ return result;
+}
+
+/*
+ * Solve the Knight Tour problem using backtracking, returning the length of
+ * the resulting solution. If this is invoked from a point where the remaining
+ * choices cannot complete the tour, the result will fall short.
+ */
+static int
+useBacktracking(SQUARES result, HISTORY * doneData, int doneSize)
+{
+ int y = 0, x = 0, n;
+ SQUARES squares;
+ int total;
+ int actual = doneSize - 1;
+
+ memset(squares, 0, sizeof(squares));
+ for (n = 1; n <= actual; ++n) {
+ y = doneData[n].y;
+ x = doneData[n].x;
+ squares[y][x] = n;
+ }
+
+ total = recurBack(squares, y, x, actual);
+ if (total > actual) {
+ for (y = 0; y < ylimit; ++y) {
+ for (x = 0; x < xlimit; ++x) {
+ result[y][x] = squares[y][x];
+ if ((n = squares[y][x]) != 0) {
+ doneData[n].y = y;
+ doneData[n].x = x;
+ }
+ }
+ }
+ }
+ return total;
+}
+
+static int
+reviewHistory(HISTORY * history, int count_moves, int review, int *ny, int *nx)
+{
+ if (review < 0) {
+ beep();
+ review = 0;
+ } else if (review > count_moves - 2) {
+ beep();
+ review = count_moves - 2;
+ } else {
+ *ny = history[count_moves - review - 1].y;
+ *nx = history[count_moves - review - 1].x;
+ wprintw(msgwin, "\nReview %d:%d.", count_moves - review - 1,
+ count_moves - 1);
+ wrefresh(msgwin);
+ }
+ return review;
+}
+