title: Brute-force sudoku solver: backtracking?
body: <p>An implementation of <a href="http://en.wikipedia.org/wiki/Algorithmics_of_sudoku#Solving_sudokus_by_a_brute-force_algorithm" rel="nofollow noreferrer">a brute-force algorithm</a> to solve Sudoku puzzles fails if a cell is discovered in which placing any of the digits 1-9 would be an illegal move.</p>
  
  <p>The implementation is written in C, with the board represented by a 9x9 array. The solver counts down from 9 until a legal number's reached, and if none can be reached, it outputs a zero in its place.</p>
  
  <p>A zero also represents a cell to be filled in. Here's the output (truncated) if a string of zeros (an empty board) is the input:</p>
  
  <pre><code>9 8 7 6 5 4 3 2 1
  6 5 4 9 8 7 0 0 0
  </code></pre>
  
  <p>Those last three zeros are there because the values filled in previously aren't changing. <strong><a href="http://www.angusj.com/sudoku/hints.php" rel="nofollow noreferrer">How</a> can I stop the solver from failing like this?</strong></p>