- Decision-tree pruning
**Decision-tree pruning**is traversing and utilization methods ofArtificial Intelligence . They are used in many programs including maps with shortest route calculations, WebMD, Law sites, and Chess. TheSudoku puzzles can also benefit from an efficient solution search since the toughest puzzles seemed to defy logic (i.e., the infamous "Qassim Hamza"). [*Lewis, R (2007) "Metaheuristics Can Solve Sudoku Puzzles" Journal of Heuristics, vol. 13 (4), pp 387-401.*]Some think you can create a valid Sudoku puzzle that can't be solved with

logic . That statement itself is not logical since, assuming its a fair puzzle (i.e., it has a valid starting point in which givens were removed), the puzzle was created using a logical and repeatable approach, thus it should be impossible to create an unsolvable puzzle much like you can never scramble aRubic's Cube to a point that it can't be solved.With a decision-tree pruning method, a human could solve the "Qassim Hamza" in 1599 logical steps. Each step involves scanning rows, columns, and squares, and maintaining a log of candidates for each cell, and counting and comparing the candidates to decide the next value to test. A person working quickly can complete a step in 45 to 60 seconds so the total solve time is estimated to be between 20 to 27 hours of continuous working time.

Below are the human logic steps and a link to a computer solver that uses the same logic. It will produce a proof in clear text for any puzzle you type in.

For humans, use this method:

1. Determine all possible values for each ungiven square. Use the standard scanning method which checks the section, row and column for possible values and givens already in them and not in them. This step alone can solve most puzzles.

2. For puzzles that deadend using step 1, you next should find the square with the least possible outcomes and secondary effects so the shortest solution path is found. You do this by adding the number of outcomes for the current square, section, row, and column for each square on the board having more than one possible value (squares with only one value is either a given or a resolved square). Compute this value for all unsolved squares and choose the one with the smallest number. In case of a tie, choose either one.

3. Now that you have determined the best square to start your search, choose the first value of the square and go to step 1 to see if the solution is found. If you deadend without producing an invalid value, you recurse forward into step 2 and 3. If you produce an invalid, you backtrack and try the next value.

Remember, one of those values is correct. They have to be since you placed all the possible values that square can have for the givens of that puzzle. Sometimes the first value turns out to be the correct one. For the Qassim Hamza puzzle, this is not the case. In fact, the proof shows you'll need to recurse 6 cells deep to find the correct solution. This is why its a difficult puzzle.

To solve any 4X4, 9X9, and 16X16 Sudoku puzzle, go to this [

*http://solveanysudoku.com/ Sudoku Solver*]**References**

*Wikimedia Foundation.
2010.*