I would very much like to see your diagram but the link is dead...

I start from scratch without knowing the existance of the Euler's theorem. After long ways of modifying my code back and forth, I ended up with my own version of Euler's theorem, but less succinct. So I think the best way to solve this problem is by applying the theorem directly. The key part is that for a^n where both a and n are large, you don't need to worry about a actually. It's easy to do exponential on very large number a as long as n is small. So you can easily do a^0, a^1, a^2, a^3 as long as n is reduced to range(4).

This solution seems very clear but I can't follow it...

I missed the important clue "all tested puzzle are determinable" and spent several days trying to solve a general puzzle. The blog "Solving Every Sudoku Puzzle" by Peter Norvig is a good guide for general case. For this "easy test", it's much simplier...

I looked into constrained programming but ended up with brute-force search... I guess implementing a general solution(not brute-force) to 6by6 or more will be much more tedious. I think it's a good idea to tackle the Sudoku solver beforing trying the 6by6 one

I think this kata doesn't fit in 4kyu. It should be 5kyu or maybe 6kyu.

By printing step by step I can see it works. But I don't quite understand how it get over with iterating to an dead end...

You're not the only one that feel like this...