We implement a smart contract to outsource solving Sudoku puzzles on Bitcoin, utilizing the paradigm we published earlier. The general problem of solving Sudoku puzzles is computationally intensive as grid size increases. In fact, it is known to be NP-complete, same as the Travelling Salesman Problem we introduced previously. The advantage of solving it on Bitcoin is that we only have to verify if the proposed solution is valid, which can be done efficiently. The intense computation of solving the puzzle is done off chain.
