Can error correction codes constitute an entertaining game?

Question

Whenever I play Sudoko, I see the finished puzzle as an overspecified version of the original input. Like 8b/10b, Reed-Solomon codes, turbo codes, or low-density parity-check codes. With ECC the computer has to solve a puzzle to produce the correct data, and with Sudoku the human has to solve a puzzle to produce 81 digits of fun.

Do you think any of these ECC codes would make a good pencil and paper game? (8b/10b -- the home version!)

Is there a good way to represent data as Sudoku puzzles to make the most ridiculous ECC available?

Answer 1

Another way to look at the overspecification in the final result is to consider the original state as the result of a compression algorithm.

Nonograms are another example of a very information-sparse result being represented in the form of an information-dense puzzle.

Answer 2

Representing arbitrary data as a sudoku puzzle is not particularly feasible as the total number of sudoku grids (and thus, the number of distinct pieces of information that could be represented by a puzzle) is far too low (approx 6E21) to encode a significant amount of data (more than about 9 bytes).

Add to this the computational difficulty of producing a non-ambiguous puzzle for a given solution, and the widely varying data density of the optimal puzzle for different solutions.