These days, I spend a lot of time doing cross-platform development. Meaning, I write a lot of native (C/C++) which then gets compiled for all sorts of platforms (Windows, Linux, Android, iOS with x86, x64, ARM, ARM64 architectures). There are so many little things I have learnt in the past two years at work. I want to document some of those things so it can help others.

To make it a little interesting, I am going to use the 8-queens problem as a starting point. In the future, I may expand it to use something more complicated.

8 queens problem

Crux of the problem is placing 8 Queens on a chess table without any conflicts. Interestingly, there are quite a few combinations. In fact, a total of 92 combinations are possible. As a fun aside, I have written a javascript version of the same algorithm and an HTML page that loops through all the possible solutions. The algorithm to solve it is quite simple. We use backtracking. One possible solution is given below in C++. It is quite a rudimentary backtracking algorithm and is self explanatory. Instead of 8 queens, I have made the algorithm generic for N-queens. At the end of the program, I print out the number of solutions possible.

#include <iostream>
#include <vector>

using namespace std;

class NQueens
{
public:
    NQueens(int _N) : N(_N)
    {
        board.resize(N*N);
        curr = 0;
        solve(0);
    }
    int count()
    {
        return solutions.size();
    }
private:
    int N;
    int curr;
    vector<char> board;
    vector<vector<char> > solutions;
    int a(int i, int j)
    {
        return i*8+j;
    }

    bool is_pos_valid(int row, int col)
    {
        int i = 0, j = 0;

        /* Only placed queens till row-1, no need to search further */
        for(i = 0; i < row; i++)
        {
            if(board[a(i,col)]) return false;
        }
        /* Go above current row, towards the left diagonal */
        for(i = row, j = col; i  >= 0 && j >= 0; i--, j--)
        {
            if(board[a(i,j)]) return false;
        }
        /* Go above current row, towards the right diagonal */
        for(i = row, j = col; i >= 0 && j < N; i--, j++)
        {
            if(board[a(i,j)]) return false;
        }

        return true;
    }

    void solve(int row)
    {
        if(row == N)
        {
            solutions.push_back(board);
            return;
        }

        for(int i = 0; i < N; i++)
        {
            if(is_pos_valid(row, i))
            {
                board[a(row, i)] = true;
                solve(row+1);
                board[a(row, i)] = false;
            }
        }
    }
};

int main(int argc, char *argv[])
{
  NQueens n(8);
  cout << "Num solutions = " << n.count() << endl;
  return 0;
}

What next?

For the frontend code, I have rewritten the code in some basic Javascript. Since it is javascript, anyone can inspect the code. In the next post, I will show how we can reuse our native C++ code and still show the results on the HTML page using Webassembly. With an added side benefit of protecting our source code!