A 9×9 sudoku solver in C. The algorithm incorporates backtracking. Backtracking is a great technique to use when the problem is NP complete and the state space isn’t huge. It takes only a few seconds to solve a hard 9×9 sudoku puzzle on a 1.4GHz machine. The program in txt can be found here. Sadly I can only upload image files so the file is a PDF.
The program first reads in the sudoku puzzle from a file named “myfile.txt”. The algorithm begins by recursively fills up the puzzle, and if no feasible input can be found for an empty block before a solution is reached, it returns to the previous empty block and attempts with another feasible input. The heuristic is very straighforward, it just ensures the input does not appear in the same row, the same column, and the same square.
An important lesson I learnt after is that for NP complete problems, if brute force isn’t working, that’s because you’re not using enough, or you just need more hardware.