The link to Wikipedia describes the puzzle, and the solution. The axiom of choice is used to pick a sequence from each equivalence class, which the prisoners memorize beforehand.
However, the answer says "When they are put into their line, each prisoner can see what equivalence class the actual sequence of hats belongs to."
Why not wait until the prisoners see which equivalence class they are in. Then, pick a sequence from this equivalence class? This would avoid having to use the axiom of choice, or am I mistaken?