Isn't one of the main properties of bitcoin its immutability?
Yes. It is probabilistically immutable. In theory there could be a re-org right back to the genesis block but the probability of this happening is effectively zero (but not exactly zero).
If so, how is it possible for it to work with pen and paper, since then it's not immutable?
In a similar way this would be probabilistically immutable. To do a x block re-org you would need to solve x proof of work challenges or sudoku puzzles. It does rely on the public square though which brings some centralization into it. With Bitcoin, transactions, blocks and proof of work solutions are broadcast globally with no single central point of failure. If someone dropped a nuclear bomb on the public square in this example that might kill this pen and paper solution.
What would mining even look like? Solving sudoku puzzles by hand?
Effectively. You wouldn't want to calculate outputs from hash function by hand so solving a sufficiently hard sudoku puzzle (with the dimensions of the puzzle adjusting depending on the number of sudoku puzzle solvers) to give you the ability to present a newly mined block could be the way to do it.
So in theory this scheme could work but it already relies on a central public square so in practice you would ditch this scheme and use more efficient centralized schemes.
