As title suggested, I built a solver for 4x4 Collapsi (with the updated rules, i.e starting position is essentially an Ace) that solves a given board configuration within 100ms (depending on hardware). On my machine, I can consistently get a solution within 10-20ms using 1-core on an intel i7-11800H. 

Essentially, the solver computes the winner of a given board configuration/arrangement and produces a "perfect" playing AI, which cannot be beaten (unless my code is buggy).

Here is the interactive web-based version: https://collapsi.onrender.com/ (note that this is hosted on free-plan with 0.1 vCPU, so it might takes a while to load)

Github link: https://github.com/huynd2210/Collapsi.

Since it almost instantaneously solves a board configuration, I think that it might be possible to solve every combinations for 4x4 board. 

There are in total 756,756,000 possible configurations. However, we only need to solve 756,756,000 / 16 = 47,297,250 configurations since each configuration can have up to 16 functionally identical form through shifting rows and columns.

However even so, that might be more than my computer can handle. 

Very nice!  You should read through some of the previous posts.  I also made a c++ solver, you may be interested in some of the data aggregation I did.

One optimization I think I see: You apply a heuristic by generating all replies for every single possible move.  This is potentially a lot of wasted recursive effort, especially if the first solution we check is valid anyways.  Just what I saw on sight read, I could very well be wrong. Otherwise it looks like a very clean recursive dfs implementation.  Especially compared to my  spaghetti-fied C-like abomination: 

int checkBoard(const int current_player, const int player_count, int player_locations[], int board[16], int depth, Metric &metrics, bool outputResult = false)