Add C, C++ & D solutions to challenge 118

6 files changed, 978 insertions, 0 deletions

diff --git a/challenge-118/paulo-custodio/c/ch-1.c b/challenge-118/paulo-custodio/c/ch-1.c
new file mode 100644
index 0000000000..855abe857f
--- /dev/null
+++ b/challenge-118/paulo-custodio/c/ch-1.c
@@ -0,0 +1,55 @@
+/*
+Challenge 118
+
+TASK #1 - Binary Palindrome
+Submitted by : Mohammad S Anwar
+You are given a positive integer $N.
+
+Write a script to find out if the binary representation of the given integer
+is Palindrome.Print 1 if it is otherwise 0.
+
+Example
+Input: $N = 5
+Output : 1 as binary representation of 5 is 101 which is Palindrome.
+
+Input : $N = 4
+Output : 0 as binary representation of 4 is 100 which is NOT Palindrome.
+*/
+
+#include <stdio.h>
+#include <stdlib.h>
+#include <stdbool.h>
+#include <string.h>
+
+#define MAXLINE 1024
+
+void int_to_rev_binary(char* buffer, int n) {
+    buffer[0] = '\0';
+    while (n > 0) {
+        strcat(buffer, n & 1 ? "1" : "0");
+        n >>= 1;
+    }
+}
+
+void reverse_string(char* dst, const char* src) {
+    int len = strlen(src);
+    for (int i = 0; i < len; i++)
+        dst[len - 1 - i] = src[i];
+    dst[len] = '\0';
+}
+
+bool is_palindrome(int n) {
+    char n_str[MAXLINE], rev_n_str[MAXLINE];
+    int_to_rev_binary(rev_n_str, n);
+    reverse_string(n_str, rev_n_str);
+    if (strcmp(n_str, rev_n_str) == 0)
+        return true;
+    else
+        return false;
+}
+
+int main(int argc, char* argv[]) {
+    int n = 0;
+    if (argc == 2) n = atoi(argv[1]);
+    printf("%d\n", is_palindrome(n) ? 1 : 0);
+}
diff --git a/challenge-118/paulo-custodio/c/ch-2.c b/challenge-118/paulo-custodio/c/ch-2.c
new file mode 100644
index 0000000000..b3e1a10af6
--- /dev/null
+++ b/challenge-118/paulo-custodio/c/ch-2.c
@@ -0,0 +1,276 @@
+/*
+Challenge 118
+
+TASK #2 - Adventure of Knight
+Submitted by : Cheok - Yin Fung
+A knight is restricted to move on an 8×8 chessboard.The knight is denoted by
+N and its way of movement is the same as what it is defined in Chess.
+* represents an empty square. x represents a square with treasure.
+
+The Knight’s movement is unique.It may move two squares vertically and one
+square horizontally, or two squares horizontally and one square vertically
+(with both forming the shape of an L).
+
+There are 6 squares with treasures.
+
+Write a script to find the path such that Knight can capture all treasures.
+The Knight can start from the top - left square.
+
+      a b c d e f g h
+    8 N * * * * * * * 8
+    7 * * * * * * * * 7
+    6 * * * * x * * * 6
+    5 * * * * * * * * 5
+    4 * * x * * * * * 4
+    3 * x * * * * * * 3
+    2 x x * * * * * * 2
+    1 * x * * * * * * 1
+      a b c d e f g h
+
+https://en.m.wikipedia.org/wiki/Knight%27s_tour
+*/
+
+#include <assert.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <stdbool.h>
+#include <string.h>
+#include <stdarg.h>
+#include <ctype.h>
+
+#define NROWS       8
+#define NCOLS       8
+#define BOARD_SIZE  (NROWS*NCOLS)
+#define PATH_SIZE   ((BOARD_SIZE*3)+1)
+#define MAXLINE     1024
+#define MAX_MOVES   8
+
+void die(const char* fmt, ...) {
+    va_list ap;
+    va_start(ap, fmt);
+    vfprintf(stderr, fmt, ap);
+    va_end(ap);
+    exit(EXIT_FAILURE);
+}
+
+typedef struct Board {
+    char cells[NROWS];
+} Board;
+
+void board_clear(Board* board) {
+    memset(board->cells, 0, NROWS);
+}
+
+bool board_empty(Board* board) {
+    for (int i = 0; i < NROWS; i++)
+        if (board->cells[i] != 0)
+            return false;
+    return true;
+}
+
+void board_set(Board* board, int row, int col) {
+    assert(row >= 0 && row < NROWS);
+    assert(col >= 0 && col < NCOLS);
+    int mask = 1 << col;
+    board->cells[row] |= mask;
+}
+
+void board_reset(Board* board, int row, int col) {
+    assert(row >= 0 && row < NROWS);
+    assert(col >= 0 && col < NCOLS);
+    int mask = 1 << col;
+    board->cells[row] &= ~mask;
+}
+
+bool board_peek(Board* board, int row, int col) {
+    assert(row >= 0 && row < NROWS);
+    assert(col >= 0 && col < NCOLS);
+    int mask = 1 << col;
+    return (board->cells[row] & mask) == 0 ? false : true;
+}
+
+
+typedef struct Game {
+    int row, col;
+    Board visited, treasure;
+    char path[PATH_SIZE];
+} Game;
+
+void game_clear(Game* game) {
+    memset(game, 0, sizeof(Game));
+}
+
+void game_set_visited(Game* game, int row, int col) {
+    board_set(&game->visited, row, col);
+}
+
+bool game_peek_visited(Game* game, int row, int col) {
+    return board_peek(&game->visited, row, col);
+}
+
+bool game_peek_treasure(Game* game, int row, int col) {
+    return board_peek(&game->treasure, row, col);
+}
+
+void game_set_treasure(Game* game, int row, int col) {
+    board_set(&game->treasure, row, col);
+}
+
+void game_clear_treasure(Game* game, int row, int col) {
+    board_reset(&game->treasure, row, col);
+}
+
+bool game_done(Game* game) {
+    return board_empty(&game->treasure);
+}
+
+void game_move(Game* game, int row, int col) {
+    game_set_visited(game, row, col);
+    game_clear_treasure(game, row, col);
+    sprintf(game->path + strlen(game->path), "%c%d ", 'a' + col, NROWS - row);
+    game->row = row;
+    game->col = col;
+}
+
+void game_print(Game* game) {
+    printf("  a b c d e f g h\n");
+    for (int row = 0; row < NROWS; row++) {
+        printf("%d", NROWS - row);
+        for (int col = 0; col < NCOLS; col++) {
+            if (game_peek_treasure(game, row, col))
+                printf(" x");
+            else if (game->row == row && game->col == col)
+                printf(" N");
+            else if (game_peek_visited(game, row, col))
+                printf(" .");
+            else
+                printf(" *");
+        }
+        printf(" %d\n", NROWS - row);
+    }
+    printf("  a b c d e f g h\n");
+    printf("\n> %s\n\n", game->path);
+}
+
+void game_parse_header(void) {
+    char line[MAXLINE];
+
+    if (!fgets(line, MAXLINE, stdin))
+        die("expected header or footer\n");
+    const char* p = line;
+    while (*p && isspace(*p)) p++;
+    if (strncmp(p, "a b c d e f g h", 15) != 0)
+        die("invalid header or footer\n");
+}
+
+void game_parse_row(Game* game, int row) {
+    char line[MAXLINE];
+
+    if (!fgets(line, MAXLINE, stdin))
+        die("expected row %d\n", NROWS - row);
+
+    const char* p = line;
+    while (*p && isspace(*p)) p++;
+    if (!isdigit(*p) || *p - '0' != NROWS - row)
+        die("invalid row %d\n", NROWS - row);
+    p++;
+    for (int col = 0; col < NCOLS; col++) {
+        while (*p && isspace(*p)) p++;
+        switch (*p) {
+        case 'N': game_move(game, row, col); break;
+        case 'x': game_set_treasure(game, row, col); break;
+        case '*': break;
+        default: die("invalid row %d\n", NROWS - row);
+        }
+        p++;
+    }
+}
+
+void game_parse(Game* game) {
+    game_clear(game);
+    game_parse_header();
+    for (int row = 0; row < NROWS; row++)
+        game_parse_row(game, row);
+    game_parse_header();
+}
+
+
+typedef struct Move {
+    int row, col, num_moves;
+} Move;
+
+void try_move(int* num_moves, Move* moves, Game* game, int nrow, int ncol) {
+    if (nrow < 0 || nrow >= NROWS) return;
+    if (ncol < 0 || ncol >= NCOLS) return;
+    if (game_peek_visited(game, nrow, ncol)) return;
+
+    moves[*num_moves].row = nrow;
+    moves[*num_moves].col = ncol;
+    moves[*num_moves].num_moves = 0;
+    (*num_moves)++;
+}
+
+void try_num_moves(int* num_moves, Move* moves, Game* game, int row, int col) {
+    *num_moves = 0;
+    try_move(num_moves, moves, game, row + 2, col + 1);
+    try_move(num_moves, moves, game, row + 2, col - 1);
+    try_move(num_moves, moves, game, row - 2, col + 1);
+    try_move(num_moves, moves, game, row - 2, col - 1);
+    try_move(num_moves, moves, game, row + 1, col + 2);
+    try_move(num_moves, moves, game, row - 1, col + 2);
+    try_move(num_moves, moves, game, row + 1, col - 2);
+    try_move(num_moves, moves, game, row - 1, col - 2);
+}
+
+int next_moves(Move* moves, Game* game) {
+    // try first step
+    int num_moves = 0;
+    try_num_moves(&num_moves, moves, game, game->row, game->col);
+
+    // for each target location count number of further steps
+    int min_moves = MAX_MOVES + 1;
+    for (int i = 0; i < num_moves; i++) {
+        Move temp_moves[MAX_MOVES];
+        try_num_moves(&moves[i].num_moves, temp_moves, game, moves[i].row, moves[i].col);
+        if (min_moves > moves[i].num_moves) min_moves = moves[i].num_moves;
+    }
+
+    // remove all moves with targets > min_moves
+    int j = 0;
+    for (int i = 0; i < num_moves; i++) {
+        if (moves[i].num_moves == min_moves)
+            moves[j++] = moves[i];
+    }
+    num_moves = j;
+
+    return num_moves;
+}
+
+void solve(Game* solution, Game* game) {
+    if (game_done(game)) {
+        if (strlen(solution->path) == 0 ||
+            strlen(solution->path) > strlen(game->path)) {
+//          game_print(game);
+            *solution = *game;
+        }
+    }
+    else {
+        Move moves[MAX_MOVES];
+        int num_moves = next_moves(moves, game);
+        for (int i = 0; i < num_moves; i++) {
+            Game new_game = *game;
+            game_move(&new_game, moves[i].row, moves[i].col);
+            solve(solution, &new_game);
+        }
+    }
+}
+
+int main(void) {
+    Game game, solution;
+    game_clear(&game);
+    game_clear(&solution);
+
+    game_parse(&game);
+    solve(&solution, &game);
+    printf("%s\n", solution.path);
+}
diff --git a/challenge-118/paulo-custodio/cpp/ch-1.cpp b/challenge-118/paulo-custodio/cpp/ch-1.cpp
new file mode 100644
index 0000000000..003cda67bc
--- /dev/null
+++ b/challenge-118/paulo-custodio/cpp/ch-1.cpp
@@ -0,0 +1,52 @@
+/*
+Challenge 118
+
+TASK #1 - Binary Palindrome
+Submitted by : Mohammad S Anwar
+You are given a positive integer $N.
+
+Write a script to find out if the binary representation of the given integer
+is Palindrome.Print 1 if it is otherwise 0.
+
+Example
+Input: $N = 5
+Output : 1 as binary representation of 5 is 101 which is Palindrome.
+
+Input : $N = 4
+Output : 0 as binary representation of 4 is 100 which is NOT Palindrome.
+*/
+
+#include <iostream>
+#include <string>
+using namespace std;
+
+string int_to_binary(int n) {
+    string bin;
+    while (n > 0) {
+        bin = string(n & 1 ? "1" : "0") + bin;
+        n >>= 1;
+    }
+    return bin;
+}
+
+string reverse_string(const string& src) {
+    string out;
+    for (int i = static_cast<int>(src.size()) - 1; i >= 0; i--)
+        out += src[i];
+    return out;
+}
+
+bool is_palindrome(int n) {
+    string n_str = int_to_binary(n);
+    string rev_n_str = reverse_string(n_str);
+    if (n_str == rev_n_str)
+        return true;
+    else
+        return false;
+}
+
+int main(int argc, char* argv[]) {
+    int n = 0;
+    if (argc == 2) n = atoi(argv[1]);
+    cout << (is_palindrome(n) ? 1 : 0) << endl;
+}
diff --git a/challenge-118/paulo-custodio/cpp/ch-2.cpp b/challenge-118/paulo-custodio/cpp/ch-2.cpp
new file mode 100644
index 0000000000..e82e6b045f
--- /dev/null
+++ b/challenge-118/paulo-custodio/cpp/ch-2.cpp
@@ -0,0 +1,282 @@
+/*
+Challenge 118
+
+TASK #2 - Adventure of Knight
+Submitted by : Cheok - Yin Fung
+A knight is restricted to move on an 8×8 chessboard.The knight is denoted by
+N and its way of movement is the same as what it is defined in Chess.
+* represents an empty square. x represents a square with treasure.
+
+The Knight’s movement is unique.It may move two squares vertically and one
+square horizontally, or two squares horizontally and one square vertically
+(with both forming the shape of an L).
+
+There are 6 squares with treasures.
+
+Write a script to find the path such that Knight can capture all treasures.
+The Knight can start from the top - left square.
+
+  a b c d e f g h
+8 N * * * * * * * 8
+7 * * * * * * * * 7
+6 * * * * x * * * 6
+5 * * * * * * * * 5
+4 * * x * * * * * 4
+3 * x * * * * * * 3
+2 x x * * * * * * 2
+1 * x * * * * * * 1
+  a b c d e f g h
+
+https://en.m.wikipedia.org/wiki/Knight%27s_tour
+*/
+
+#include <cassert>
+#include <cctype>
+#include <cstring>
+#include <iostream>
+#include <string>
+#include <vector>
+using namespace std;
+
+#define NROWS       8
+#define NCOLS       8
+#define MAX_MOVES   8
+
+struct Board {
+    Board() {
+        clear();
+    }
+
+    void clear() {
+        memset(cells, 0, NROWS);
+    }
+
+    bool empty() const {
+        for (int i = 0; i < NROWS; i++)
+            if (cells[i] != 0)
+                return false;
+        return true;
+    }
+
+    void set(int row, int col) {
+        assert(row >= 0 && row < NROWS);
+        assert(col >= 0 && col < NCOLS);
+        int mask = 1 << col;
+        cells[row] |= mask;
+    }
+
+    void reset(int row, int col) {
+        assert(row >= 0 && row < NROWS);
+        assert(col >= 0 && col < NCOLS);
+        int mask = 1 << col;
+        cells[row] &= ~mask;
+    }
+
+    bool peek(int row, int col) const {
+        assert(row >= 0 && row < NROWS);
+        assert(col >= 0 && col < NCOLS);
+        int mask = 1 << col;
+        return (cells[row] & mask) == 0 ? false : true;
+    }
+
+    char cells[NROWS];
+};
+
+struct Game {
+    Game() {
+        clear();
+    }
+
+    void clear() {
+        row = col = 0;
+        visited.clear();
+        treasure.clear();
+        path.clear();
+    }
+
+    void set_visited(int row, int col) {
+        visited.set(row, col);
+    }
+
+    bool peek_visited(int row, int col) const {
+        return visited.peek(row, col);
+    }
+
+    void set_treasure(int row, int col) {
+        treasure.set(row, col);
+    }
+
+    void clear_treasure(int row, int col) {
+        treasure.reset(row, col);
+    }
+
+    bool peek_treasure(int row, int col) const {
+        return treasure.peek(row, col);
+    }
+
+    bool done() const {
+        return treasure.empty();
+    }
+
+    void move(int row, int col) {
+        set_visited(row, col);
+        clear_treasure(row, col);
+        path += 'a' + col;
+        path += to_string(NROWS - row);
+        path += " ";
+        this->row = row;
+        this->col = col;
+    }
+
+    friend ostream& operator<<(ostream& os, const Game& game) {
+        os << "  a b c d e f g h" << endl;
+        for (int row = 0; row < NROWS; row++) {
+            os << NROWS - row;
+            for (int col = 0; col < NCOLS; col++) {
+                if (game.peek_treasure(row, col))
+                    os << " x";
+                else if (game.row == row && game.col == col)
+                    os << " N";
+                else if (game.peek_visited(row, col))
+                    os << " .";
+                else
+                    os << " *";
+            }
+            os << " " << NROWS - row << endl;
+        }
+        os << "  a b c d e f g h" << endl;
+        os << endl << "> " << game.path << endl;
+        return os;
+    }
+
+    void parse_header() {
+        string line;
+        if (!getline(cin, line)) {
+            cerr << "expected header or footer" << endl;
+            exit(EXIT_FAILURE);
+        }
+        const char* p = line.c_str();
+        while (*p && isspace(*p)) p++;
+        if (strncmp(p, "a b c d e f g h", 15) != 0) {
+            cerr << "invalid header or footer" << endl;
+            exit(EXIT_FAILURE);
+        }
+    }
+
+    void parse_row(int row) {
+        string line;
+        if (!getline(cin, line)) {
+            cerr << "expected row " << NROWS - row << endl;
+            exit(EXIT_FAILURE);
+        }
+        const char* p = line.c_str();
+        while (*p && isspace(*p)) p++;
+        if (!isdigit(*p) || *p - '0' != NROWS - row) {
+            cerr << "invalid row " << NROWS - row << endl;
+            exit(EXIT_FAILURE);
+        }
+        p++;
+        for (int col = 0; col < NCOLS; col++) {
+            while (*p && isspace(*p)) p++;
+            switch (*p) {
+                case 'N': move(row, col); break;
+                case 'x': set_treasure(row, col); break;
+                case '*': break;
+                default:
+                    cerr << "invalid row " << NROWS - row << endl;
+                    exit(EXIT_FAILURE);
+            }
+            p++;
+        }
+    }
+
+    void parse() {
+        clear();
+        parse_header();
+        for (int row = 0; row < NROWS; row++)
+            parse_row(row);
+        parse_header();
+    }
+
+    int row{ 0 }, col{ 0 };
+    Board visited, treasure;
+    string path;
+};
+
+struct Move {
+    int row, col, num_moves;
+
+    Move(int row = 0, int col = 0, int num_moves = 0)
+        : row(row), col(col), num_moves(num_moves) {}
+};
+
+void try_move(vector<Move>& moves, Game& game, int nrow, int ncol) {
+    if (nrow < 0 || nrow >= NROWS) return;
+    if (ncol < 0 || ncol >= NCOLS) return;
+    if (game.peek_visited(nrow, ncol)) return;
+
+    moves.push_back(Move(nrow, ncol, 0));
+}
+
+void try_num_moves(vector<Move>& moves, Game& game, int row, int col) {
+    moves.clear();
+    try_move(moves, game, row + 2, col + 1);
+    try_move(moves, game, row + 2, col - 1);
+    try_move(moves, game, row - 2, col + 1);
+    try_move(moves, game, row - 2, col - 1);
+    try_move(moves, game, row + 1, col + 2);
+    try_move(moves, game, row - 1, col + 2);
+    try_move(moves, game, row + 1, col - 2);
+    try_move(moves, game, row - 1, col - 2);
+}
+
+vector<Move> next_moves(Game& game) {
+    vector<Move> moves;
+
+    // try first step
+    try_num_moves(moves, game, game.row, game.col);
+
+    // for each target location count number of further steps
+    int min_moves = MAX_MOVES + 1;
+    for (size_t i = 0; i < moves.size(); i++) {
+        vector<Move> temp_moves;
+        try_num_moves(temp_moves, game, moves[i].row, moves[i].col);
+        moves[i].num_moves = temp_moves.size();
+        if (min_moves > moves[i].num_moves) min_moves = moves[i].num_moves;
+    }
+
+    // remove all moves with targets > min_moves
+    size_t j = 0;
+    for (size_t i = 0; i < moves.size(); i++) {
+        if (moves[i].num_moves == min_moves)
+            moves[j++] = moves[i];
+    }
+    moves.resize(j);
+
+    return moves;
+}
+
+void solve(Game& solution, Game& game) {
+    if (game.done()) {
+        if (solution.path.size() == 0 || solution.path.size() > game.path.size()) {
+            // cout << game;
+            solution = game;
+        }
+    }
+    else {
+        vector<Move> moves = next_moves(game);
+        for (size_t i = 0; i < moves.size(); i++) {
+            Game new_game = game;
+            new_game.move(moves[i].row, moves[i].col);
+            solve(solution, new_game);
+        }
+    }
+}
+
+int main(void) {
+    Game game, solution;
+    game.parse();
+
+    solve(solution, game);
+    cout << solution.path << endl;
+}
diff --git a/challenge-118/paulo-custodio/d/ch_1.d b/challenge-118/paulo-custodio/d/ch_1.d
new file mode 100644
index 0000000000..87d924d1ed
--- /dev/null
+++ b/challenge-118/paulo-custodio/d/ch_1.d
@@ -0,0 +1,44 @@
+/*
+Challenge 118
+
+TASK #1 - Binary Palindrome
+Submitted by : Mohammad S Anwar
+You are given a positive integer $N.
+
+Write a script to find out if the binary representation of the given integer
+is Palindrome.Print 1 if it is otherwise 0.
+
+Example
+Input: $N = 5
+Output : 1 as binary representation of 5 is 101 which is Palindrome.
+
+Input : $N = 4
+Output : 0 as binary representation of 4 is 100 which is NOT Palindrome.
+*/
+
+import std.stdio;
+import std.conv;
+import std.algorithm.mutation;
+
+string int_to_binary(int n) {
+    string bin;
+    while (n > 0) {
+        bin = (n & 1 ? "1" : "0") ~ bin;
+        n >>= 1;
+    }
+    return bin;
+}
+
+bool is_palindrome(int n) {
+    string n_str = int_to_binary(n);
+    string rev_n_str = n_str.dup.reverse;
+    if (n_str == rev_n_str)
+        return true;
+    else
+        return false;
+}
+
+void main(string[] args) {
+    auto n = to!int(args[1]);
+    writeln(is_palindrome(n) ? 1 : 0);
+}
diff --git a/challenge-118/paulo-custodio/d/ch_2.d b/challenge-118/paulo-custodio/d/ch_2.d
new file mode 100644
index 0000000000..122b253812
--- /dev/null
+++ b/challenge-118/paulo-custodio/d/ch_2.d
@@ -0,0 +1,269 @@
+/*
+Challenge 118
+
+TASK #2 - Adventure of Knight
+Submitted by : Cheok - Yin Fung
+A knight is restricted to move on an 8x8 chessboard.The knight is denoted by
+N and its way of movement is the same as what it is defined in Chess.
+* represents an empty square. x represents a square with treasure.
+
+The Knight's movement is unique.It may move two squares vertically and one
+square horizontally, or two squares horizontally and one square vertically
+(with both forming the shape of an L).
+
+There are 6 squares with treasures.
+
+Write a script to find the path such that Knight can capture all treasures.
+The Knight can start from the top - left square.
+
+  a b c d e f g h
+8 N * * * * * * * 8
+7 * * * * * * * * 7
+6 * * * * x * * * 6
+5 * * * * * * * * 5
+4 * * x * * * * * 4
+3 * x * * * * * * 3
+2 x x * * * * * * 2
+1 * x * * * * * * 1
+  a b c d e f g h
+
+https://en.m.wikipedia.org/wiki/Knight%27s_tour
+*/
+
+import std.stdio;
+import std.conv;
+import core.stdc.stdlib : exit;
+
+enum NROWS     = 8;
+enum NCOLS     = 8;
+enum MAX_MOVES = 8;
+
+struct Board {
+    ubyte[NROWS] cells;
+
+    void clear() {
+        cells[] = 0;
+    }
+
+    bool empty() const {
+        for (int i = 0; i < NROWS; i++)
+            if (cells[i] != 0)
+                return false;
+        return true;
+    }
+
+    void set(int row, int col) {
+        assert(row >= 0 && row < NROWS);
+        assert(col >= 0 && col < NCOLS);
+        int mask = 1 << col;
+        cells[row] |= mask;
+    }
+
+    void reset(int row, int col) {
+        assert(row >= 0 && row < NROWS);
+        assert(col >= 0 && col < NCOLS);
+        int mask = 1 << col;
+        cells[row] &= ~mask;
+    }
+
+    bool peek(int row, int col) const {
+        assert(row >= 0 && row < NROWS);
+        assert(col >= 0 && col < NCOLS);
+        int mask = 1 << col;
+        return (cells[row] & mask) == 0 ? false : true;
+    }
+}
+
+struct Game {
+    int row, col;
+    Board visited, treasure;
+    string path;
+
+    void clear() {
+        row = col = 0;
+        visited.clear();
+        treasure.clear();
+        path = "";
+    }
+
+    void set_visited(int row, int col) {
+        visited.set(row, col);
+    }
+
+    bool peek_visited(int row, int col) const {
+        return visited.peek(row, col);
+    }
+
+    void set_treasure(int row, int col) {
+        treasure.set(row, col);
+    }
+
+    void clear_treasure(int row, int col) {
+        treasure.reset(row, col);
+    }
+
+    bool peek_treasure(int row, int col) const {
+        return treasure.peek(row, col);
+    }
+
+    bool done() const {
+        return treasure.empty();
+    }
+
+    void move(int row, int col) {
+        set_visited(row, col);
+        clear_treasure(row, col);
+        path ~= 'a' + col;
+        path ~= to!string(NROWS - row);
+        path ~= " ";
+        this.row = row;
+        this.col = col;
+    }
+
+    void print() {
+        writeln("  a b c d e f g h");
+        for (int row = 0; row < NROWS; row++) {
+            write(NROWS - row);
+            for (int col = 0; col < NCOLS; col++) {
+                if (peek_treasure(row, col))
+                    write(" x");
+                else if (this.row == row && this.col == col)
+                    write(" N");
+                else if (peek_visited(row, col))
+                    write(" .");
+                else
+                    write(" *");
+            }
+            writeln(" ", NROWS - row);
+        }
+        writeln("  a b c d e f g h");
+        writeln("");
+        writeln("> ", path);
+    }
+
+    void parse_header() {
+        string line;
+        if ((line = readln()) is null) {
+            stderr.writeln("expected header or footer");
+            exit(1);
+        }
+        auto p = 0;
+        while (p < line.length && line[p] == ' ') p++;
+        if (line[p .. p+15] != "a b c d e f g h") {
+            stderr.writeln("invalid header or footer");
+            exit(1);
+        }
+    }
+
+    void parse_row(int row) {
+        string line;
+        if ((line = readln()) is null) {
+            stderr.writeln("expected row ", NROWS - row);
+            exit(1);
+        }
+        auto p = 0;
+        while (p < line.length && line[p] == ' ') p++;
+        if (line[p] - '0' != NROWS - row) {
+            stderr.writeln("invalid row ", NROWS - row);
+            exit(1);
+        }
+        p++;
+        for (int col = 0; col < NCOLS; col++) {
+            while (p < line.length && line[p] == ' ') p++;
+            switch (line[p]) {
+                case 'N': move(row, col); break;
+                case 'x': set_treasure(row, col); break;
+                case '*': break;
+                default:
+                    stderr.writeln("invalid row ", NROWS - row);
+                    exit(1);
+            }
+            p++;
+        }
+    }
+
+    void parse() {
+        clear();
+        parse_header();
+        for (int row = 0; row < NROWS; row++)
+            parse_row(row);
+        parse_header();
+    }
+
+}
+
+struct Move {
+    int row, col, num_moves;
+}
+
+void try_move(Move[]* moves, Game* game, int nrow, int ncol) {
+    if (nrow < 0 || nrow >= NROWS) return;
+    if (ncol < 0 || ncol >= NCOLS) return;
+    if (game.peek_visited(nrow, ncol)) return;
+
+    *moves = *moves ~ [Move(nrow, ncol, 0)];
+}
+
+void try_num_moves(Move[]* moves, Game* game, int row, int col) {
+    *moves = [];
+    try_move(moves, game, row + 2, col + 1);
+    try_move(moves, game, row + 2, col - 1);
+    try_move(moves, game, row - 2, col + 1);
+    try_move(moves, game, row - 2, col - 1);
+    try_move(moves, game, row + 1, col + 2);
+    try_move(moves, game, row - 1, col + 2);
+    try_move(moves, game, row + 1, col - 2);
+    try_move(moves, game, row - 1, col - 2);
+}
+
+Move[] next_moves(Game* game) {
+    Move[] moves;
+
+    // try first step
+    try_num_moves(&moves, game, game.row, game.col);
+
+    // for each target location count number of further steps
+    int min_moves = MAX_MOVES + 1;
+    for (int i = 0; i < moves.length; i++) {
+        Move[] temp_moves;
+        try_num_moves(&temp_moves, game, moves[i].row, moves[i].col);
+        moves[i].num_moves = temp_moves.length;
+        if (min_moves > moves[i].num_moves) min_moves = moves[i].num_moves;
+    }
+
+    // remove all moves with targets > min_moves
+    int j = 0;
+    for (int i = 0; i < moves.length; i++) {
+        if (moves[i].num_moves == min_moves)
+            moves[j++] = moves[i];
+    }
+    moves = moves[0 .. j];
+
+    return moves;
+}
+
+void solve(Game* solution, Game* game) {
+    if (game.done()) {
+        if (solution.path.length == 0 ||
+            solution.path.length > game.path.length) {
+                //game.print();
+                *solution = *game;
+            }
+    }
+    else {
+        Move[] moves = next_moves(game);
+        for (int i = 0; i < moves.length; i++) {
+            Game new_game = *game;
+            new_game.move(moves[i].row, moves[i].col);
+            solve(solution, &new_game);
+        }
+    }
+}
+
+void main() {
+    Game game, solution;
+    game.parse();
+
+    solve(&solution, &game);
+    writeln(solution.path);
+}