A Sudoku puzzle is a $9\times 9$ array of cells that when completed have the integers $1,2,\dots,9$ appearing exactly once in each row and each column. Also (and this is what makes the puzzles so fascinating), the numbers $1$, $2$, $3,\dots,9$ appear once in each of the nine $3\times 3$ subsquares identified by the darkened borders. To be considered a legitimate Sudoku puzzle, there should be a unique solution. In Figure 1.22, we show two Sudoku puzzles. The one on the right is fairly easy, and the one on the left is far more challenging.
The size of a Sudoku puzzle can be expanded in an obvious way, and many newspapers include a $16\times16$ Sudoku puzzle in their Sunday edition (just next to a challenging crosswords puzzle). How difficult would it be to solve a $1024\times1024$ Sudoku puzzle, even if you had access to a powerful computer?