How to solve black & white knights problem in 3×3 grid – Artificial Intelligence

An important aspect is that the number of possible positions is rather small :

420 = Binomial(8,2) * Binomial(6, 2)

A consequence is that whatever which the algorithm is selected, you have to pay attention not to go through the same node several times , i.e. through the same position. Traditionally, chess programmes use hash tables when analyzing positions with a low number of pieces. Here, taking into account the small number of possible positions, it is possible to select a perfect hashing, i.e. with no collusion.

Concerning the algorithms:

• Hill climbing method provides a local minimum, not an absolute one. It should not answer the question here
• DFS (e.g. implemented with backtracking) does not seem the best here, as you take the risk to go deeply in a false route
• A* algorithm are often very efficient. However, it relies of a good heuristic estimation of a given node. Here, after having looking for a solution by hand, it is clear that the Knights have to turn around a long time in a short surface (crazy horses). Difficult to find a good heuristic in this situation
• BFS generally has the drawback that it can generate a very large amount of memory and consequently a large time spent visiting these nodes. Here, it won’t be the case, due to the limited number of possible nodes (positions) and due to the hashing. Moreover, with BFS, as soon as we get a solution, we are certain it is the shortest one

I have therefore implemented the BFS in C++. The result is provided about instantaneously.

The 16 half-moves are given hereafter:

+---+---+---+  +---+---+---+  +---+---+---+  +---+---+---+  
| W |   | W |  |   |   | W |  |   |   | W |  |   |   |   |
+---+---+---+  +---+---+---+  +---+---+---+  +---+---+---+  
|   |   |   |  |   |   |   |  |   |   | B |  | W |   | B |
+---+---+---+  +---+---+---+  +---+---+---+  +---+---+---+  
| B |   | B |  | B | W | B |  |   | W | B |  |   | W | B |
+---+---+---+  +---+---+---+  +---+---+---+  +---+---+---+  

+---+---+---+  +---+---+---+  +---+---+---+  +---+---+---+  
| B |   |   |  | B |   | W |  | B | B | W |  | B | B | W |
+---+---+---+  +---+---+---+  +---+---+---+  +---+---+---+  
| W |   |   |  | W |   |   |  | W |   |   |  |   |   |   |
+---+---+---+  +---+---+---+  +---+---+---+  +---+---+---+  
|   | W | B |  |   |   | B |  |   |   |   |  |   |   | W |
+---+---+---+  +---+---+---+  +---+---+---+  +---+---+---+  

+---+---+---+  +---+---+---+  +---+---+---+  +---+---+---+  
| B |   | W |  | B | W | W |  | B | W | W |  | B | W |   |
+---+---+---+  +---+---+---+  +---+---+---+  +---+---+---+  
|   |   |   |  |   |   |   |  |   |   | B |  | W |   | B |
+---+---+---+  +---+---+---+  +---+---+---+  +---+---+---+  
| B |   | W |  | B |   |   |  |   |   |   |  |   |   |   |
+---+---+---+  +---+---+---+  +---+---+---+  +---+---+---+  

+---+---+---+  +---+---+---+  +---+---+---+  +---+---+---+  +---+---+---+  
|   | W |   |  |   | W |   |  |   | W | B |  |   |   | B |  | B |   | B |
+---+---+---+  +---+---+---+  +---+---+---+  +---+---+---+  +---+---+---+  
| W |   | B |  |   |   | B |  |   |   | B |  |   |   | B |  |   |   |   |
+---+---+---+  +---+---+---+  +---+---+---+  +---+---+---+  +---+---+---+  
|   | B |   |  |   | B | W |  |   |   | W |  | W |   | W |  | W |   | W |
+---+---+---+  +---+---+---+  +---+---+---+  +---+---+---+  +---+---+---+  

And the programme:

#include    <iostream>
#include    <array>
#include    <vector>
#include    <tuple>
#include    <algorithm>

int depl[9][2] = {
    {5,7}, {6,8}, {3,7}, {2,8}, {-1,-1},
    {0,6}, {1,5}, {0,2}, {1,3}};

struct position {
    std::array<int, 2> B;
    std::array<int, 2> W;
    int hash;
    position *up = nullptr;
    position (int w0, int w1, int b0, int b1) {
        if (w0 > w1) std::swap (w0, w1);
        if (b0 > b1) std::swap (b0, b1);
        B[0] = b0;
        B[1] = b1;
        W[0] = w0;
        W[1] = w1;
        cal_hash();
    }
    position() {};
    void cal_hash () {
        hash = 1000*B[0] + 100*B[1] + 10*W[0] + W[1];
    }
    std::vector<position> gene_mov (int white_black) {
        std::vector<position> res;
        if (!white_black) {     // White
            for (int i = 0; i < 2; ++i) {
                for (int j = 0; j < 2; ++j) {
                    int pos = depl[W[i]][j];
                    bool test = (pos == W[1-i]) || (pos == B[0]) || (pos == B[1]);
                    if (!test) {
                        res.push_back (position(pos, W[1-i], B[0], B[1]));
                    }
                }
            }
        } else {                // Black
            for (int i = 0; i < 2; ++i) {
                for (int j = 0; j < 2; ++j) {
                    int pos = depl[B[i]][j];
                    bool test = (pos == B[1-i]) || (pos == W[0]) || (pos == W[1]);
                    if (!test) {
                        res.push_back (position(W[0], W[1], pos, B[1-i]));
                    }
                }
            }           
        }
        return res;
    }
    void print (int shift = 0) {
        char displ[3][3] = {{' ',' ',' '},
                            {' ',' ',' '},
                            {' ',' ',' '}};
        displ[1][1] = ' ';
        displ[2 - W[0]/3][W[0]%3] = 'W';
        displ[2 - W[1]/3][W[1]%3] = 'W';
        displ[2 - B[0]/3][B[0]%3] = 'B';
        displ[2 - B[1]/3][B[1]%3] = 'B';
        Wshift(shift);
        std::cout << "+---+---+---+n";
        for (int i = 0; i < 3; ++i) {
            Wshift(shift);
            for (int j = 0; j < 3; j++) {
                std::cout << "| " << displ[i][j] << " ";
            }
            std::cout << "|n";
            Wshift(shift);
            std::cout << "+---+---+---+n";
        }
        std::cout << "n";
    }
    void Wshift (int shift) {
        for (int i = 0; i < shift; ++i)
            std::cout << " ";
    }
};

std::tuple<bool, int, std::vector<position>> find_moves (position &first, position &end) {
    std::vector<position> moves;
    std::array<bool, 10000> pos_found = {false};
    std::vector<std::vector<position>> dfs;
    using pvector = std::vector<position>;
    dfs.push_back(pvector(1, first));

    int iter = 1;
    int white_black = 0;
    while (true) {
        int n = dfs[iter-1].size();
        if (n == 0) return std::make_tuple(false, 0, moves);
        dfs.push_back(pvector(0));
        for (int i = 0; i < n; ++i) {
            auto candidates = dfs[iter-1][i].gene_mov(white_black);
            for (auto &c: candidates) {
                if (pos_found[c.hash]) continue;
                c.up = &dfs[iter-1][i];
                if (c.hash == end.hash) {   // Last position attained: get the previous moves
                        moves.resize(iter+1);
                        moves[iter] = c;
                        for (int i = iter - 1; i >= 0; i--) {
                            moves[i] = *(moves[i+1].up);
                        }
                        return std::make_tuple(true, iter, moves);
                }
                pos_found[c.hash] = true;
                dfs[iter].push_back (c);
            }
        }
        iter++;
        white_black = 1 - white_black;
    }

    return std::make_tuple(false, -1, moves);
}

int main () {
    position first(6, 8, 0, 2);
    position end(0, 2, 6, 8);

    bool success;
    int n_iter;
    std::vector<position> moves;
    std::tie (success, n_iter, moves) = find_moves (first, end);
    std::cout << "success = " << success << "n";
    std::cout << "n_iter = " << n_iter << "n";

    for (auto &m: moves) {
        m.print();
        std::cout << "n";
    }
    return 0;
}