Brute Force

If the Sudoku grading program runs through all algorithms without being able to apply any of them when the grid is not yet solved, there is a substantial issue at hand. It is important to know if the puzzle actually can be solved. Because the grading algorithm does not concern itself with strategies more difficult than Swordfish, it is paramount to know at least that the puzzle has a solution in order to differentiate between giving the highest strategic difficulty score and alerting the user that the puzzle is in fact impossible. To solve this requires a new solving technique: brute force.

Programming the brute force solving technique can be done in many ways, some of which will run quicker than others. A decent brute force technique that, while not the fastest available, is recursive backtracking. The idea behind this approach is to take the grid, guess a value for the first spot, and if the grid is still valid, guess a value for the next empty spot until the grid is filled (Jensen 1). If the grid is not valid, then another guess for the value will be inserted into the empty space. If no guesses result in a valid grid, then the guessing continues at the previous empty cell in the same manner. This process repeats itself in a recursive fashion, backtracking whenever it creates an invalid grid. If the grid is never filled, then the puzzle cannot possibly have any solutions. Alternatively, editing the logic slightly, one can also determine if a puzzle is impossible because it has multiple valid solutions. With a means of finding the puzzle’s strategic difficulty, it is time to begin constructing the grader’s scale.

Posted in Sudoku Solving Strategies and Techniques at April 26th, 2009. Trackback URI: trackback

One Response to “Brute Force”

  1. September 10th, 2010 at 8:14 pm #JAMIE

    CheapTabletsOnline.Com. Canadian Health&Care.No prescription online pharmacy.Special Internet Prices.Best quality drugs. Low price pills. Buy drugs online

    Buy:SleepWell.Seroquel.Amoxicillin.Prozac.Lipitor.Wellbutrin SR.Buspar.Cozaar.Female Cialis.Lasix.Nymphomax.Acomplia.Zetia.Ventolin.Advair.Female Pink Viagra.Lipothin.Zocor.Benicar.Aricept….