This is the third part, of a series of blog posts, on the impossibility of finding efficient algorithms for certain problems.
In the first, we saw that for sudoku and many other puzzles, there is a single explanation for our inability to find polynomial time algorithms. The explanation is that, any one problem (say sudoku) that is NP-Complete, does not have a polynomial time algorithm. This is commonly known as the P $\neq$ NP assumption.
In the previous blog post, we saw that a computer as we know it, cannot help in solving many puzzles. But some of these puzzles need to be solved, routinely in real life programs. So should we give up hope? Is there another way out?
One way out, is to relax the conditions that is required of the solutions. For the sudoku puzzle, we might say that, we are happy with solutions with just the rows and columns having all distinct numbers and not the blocks.
Sudoku Above is an instance of the sudoku puzzle. The goal is to fill in numbers from $1$ to $9$ in the blanks such that, every row, column and $3 \times 3$ block has all the $9$ different numbers. Beside is a solution for the puzzle instance and it is easy to verify that the constraints on the rows, columns and sub blocks are satisfied.
Since very few numbers are given, it is difficult to solve.