CMIMC 2019 Power Problem 2.4

Prove that there exists a 3-approximation algorithm for Sudoku. Here we want an explicit algorithm in addition to a proof. High level pseudocode is acceptable.

Note: You may not use the next problem in the solution to this one.