Hhm, thanks for the advices.
There is one point in particular that puzzles me: whenever I visit a letter which is not the last, I change that letter to an empty "" so that I'm sure I will not visit that letter again when searching for neighbours in the adjacent letter. However, in Python it seems to me I'm forced to do a deepcopy of the current board, apply my changes in that deepcopy and start the search again, otherwise I would just copy the reference to the board and all changes would apply to the initial board, leading to errors.
This is presumably very costly, then again I wouldn't know how to efficiently differentiate between visited and not yet visited.

Also, I don't understand what you mean when you say "verify that you do not explore branches where you actually already know that there won"t be any match". How can know a priori? I can't figure a way to stop the execution beforehand without actually trying all possibilities.

Turns out you have to check for non-legal characters when you encrypt AND also when you decrypt

I have the very same problem. Did you happen to find out what we are supposed to throw?

Very interestingly, I found out for large test with large integers like the ones above, the CW compiler adds a space at the beginning of the string, but the same does not happen on my machine.
I was able to make it work by searching a space in the first position and eliminating it.

Could it be there's a space too much in the given string that my code brings at first position?

I think there might be some issue with the random test, as I'm able to pass the fixed tests without any problem, but then

Expected: equal to 104008 106342 210355 44521 7900 93104 162226 319043 32861 332183 13890 266232 229343 8924 490075 187065 445384 489034 64378 381959
Actual: 104008 106342 210355 44521 7900 93104 162226 319043 32861 332183 13890 266232 229343 8924 490075 187065 445384 489034 64378 381959

Expected: equal to 203001 71008 231821 445004 174702 146283 314880 175345 464074 146539 448480 497314 209659 415894 457537 137399 384479 369576 118999 399886
Actual: 203001 71008 231821 445004 174702 146283 314880 175345 464074 146539 448480 497314 209659 415894 457537 137399 384479 369576 118999 399886

and I don't have any initial or final hidden spaces

Looking at the other solutions, I seem to be the only one using the function replace(), so I believe in the end nothing is wrong with the translation.
If anything, complex ASCII characters seem not to be supported by replace() and this might or might not be a C++ bug.
All good then.

In the end I was able to solve the problem by writing each line with 'x' and 'o' characters and then changing them one by one with the corresponding square.
I suspect the whole fuss is caused by the function std::string.replace()

OMG, this is ridicolous...

BasicTest1
Expected: equal to
■
Actual:
■
BasicTest2
Expected: equal to
□□□
□■□
□□□
Actual:
□□□
□■□
□□□
BasicTest3
Expected: equal to
■■■■■
■□□□■
■□■□■
■□□□■
■■■■■
Actual:
■■■■■
■□□□■
■□■□■
■□□□■
■■■■■

I have tried in thousands of ways, my code runs properly with 'normal' characters, but the squares produce garbage output, such as

□□□□□□□□□□□�□□□□□□□
�■■■■■■■■■��□□□□□□□�□□□□□□□
��□□□□□□□�■■■■■■��□□□□□□□�□□□□□□□
���■■■■■□□□□□�■■■■■■��□□□□□□□�□□□□□□□
����□□□��■■■□□□□□�■■■■■■��□□□□□□□�□□□□□□□
�����■�□□��■■■□□□□□�■■■■■■��□□□□□□□�□□□□□□□
����□□□��■■■□□□□□�■■■■■■��□□□□□□□�□□□□□□□
���■■■■■□□□□□�■■■■■■��□□□□□□□�□□□□□□□
��□□□□□□□�■■■■■■��□□□□□□□�□□□□□□□
�■■■■■■■■■��□□□□□□□�□□□□□□□
□□□□□□□□□□□�□□□□□□□

while with more Christian characters I have the working solution

xxxxxxxxxxx
xooooooooox
xoxxxxxxxox
xoxoooooxox
xoxoxxxoxox
xoxoxoxoxox
xoxoxxxoxox
xoxoooooxox
xoxxxxxxxox
xooooooooox
xxxxxxxxxxx

Please provide some explanation on how to properly define and treat those squares, as they appear not to be in the usual ASCII range. Thanks

Oh wow, never seen anything like that.
Sadly, my code still produces garbage output, but thanks anyway.

As a matter of fact, I did copy paste the characters and I get a lot of garbage in the output, although it works well with "normal" characters. Care to explain how I can get the squares to display properly? Thanks :)

In C++ the sample test returned an error with 0 test passed, while the full test were ok