The Sudoku solver code appearing in files below solves Sudoku puzzles - but not

Question

The Sudoku solver code appearing in files below solves Sudoku puzzles - but not very efficiently. Your job for this assignment is to improve the performance of the recursive algorithm at the heart of the weak solver (the solve method in the SudBoard class). In particular, with number-of-recursive-calls as your measure of efficiency, see how much better you can do than the 87,000 recursive calls the code below takes on BoardOne.txt.

A good way to start is to do an example or two using pencil and paper, and think about strategies as you work them (try solving BoardOne by hand, and observe how your approach differs from the way the code, as presented, works on this board). To run the given code you'll need to get all of the attached files, and you'll have to compile the .java files. A significant part of the work for this project is simply reading the code and mastering how it works.

Echo class:

Exception class:

Readboard class:

Sudboard class:

Sudsolve class:

Test case 1:

Test case 2:

Also: run the code on the three example boards (attached: BoardOne.txt, BoardTwo.txt, and BoardThree.txt). BoardThree is considered to be one of the hardest boards on the planet.

Another tip: think about how you choose the next cell to work on when you do the problem using pencil and paper, and compare how this is done in the SudBoard class. The wiggle method in SudBoard actually isn't used in the code as given, but it can be very helpful in your improved version.

Your job here, then, is to rework the SudBoard class so that it (significantly!) improves the performance (in terms of number of recursive calls) of the solve method in SudBoard.

Explanation / Answer

/** * The Sudoku class povides a static main * method allowing it to be called from the command line to print the * solution to a specified Sudoku problem. * *

The following is an example of a Sudoku problem: * *

  * -----------------------  * |   8   | 4   2 |   6   |  * |   3 4 |       | 9 1   |  * | 9 6   |       |   8 4 |  *  -----------------------  * |       | 2 1 6 |       |  * |       |       |       |  * |       | 3 5 7 |       |  *  -----------------------  * | 8 4   |       |   7 5 |  * |   2 6 |       | 1 3   |  * |   9   | 7   1 |   4   |  *  -----------------------  * 

* * The goal is to fill in the missing numbers so that * every row, column and box contains each of the numbers * 1-9. Here is the solution to the * problem above: * *

  *  -----------------------  * | 1 8 7 | 4 9 2 | 5 6 3 |  * | 5 3 4 | 6 7 8 | 9 1 2 |  * | 9 6 2 | 1 3 5 | 7 8 4 |  *  -----------------------  * | 4 5 8 | 2 1 6 | 3 9 7 |  * | 2 7 3 | 8 4 9 | 6 5 1 |  * | 6 1 9 | 3 5 7 | 4 2 8 |  *  -----------------------  * | 8 4 1 | 9 6 3 | 2 7 5 |  * | 7 2 6 | 5 8 4 | 1 3 9 |  * | 3 9 5 | 7 2 1 | 8 4 6 |  *  -----------------------  * 

* * Note that the first row 187492563 contains * each number exactly once, as does the first column * 159426873, the upper-left box * 187534962, and every other row, column * and box. * *

The {@link #main(String[])} method encodes a problem as an array * of strings, with one string encoding each constraint in the problem * in row-column-value format. Here is the problem again with * the indices indicated: * *

  *     0 1 2   3 4 5   6 7 8  *    -----------------------  * 0 |   8   | 4   2 |   6   |  * 1 |   3 4 |       | 9 1   |  * 2 | 9 6   |       |   8 4 |  *    -----------------------  * 3 |       | 2 1 6 |       |  * 4 |       |       |       |  * 5 |       | 3 5 7 |       |  *   -----------------------  * 6 | 8 4   |       |   7 5 |  * 7 |   2 6 |       | 1 3   |  * 8 |   9   | 7   1 |   4   |  *    -----------------------  * 

* * The 8 in the upper left box of the puzzle is encoded * as 018 (0 for the row, 1 for * the column, and 8 for the value). The 4 * in the lower right box is encoded as 874. * *

The full command-line invocation for the above puzzle is: * *

  * % java -cp . Sudoku 018 034 052 076   *                     113 124 169 171   *                     209 216 278 284   *                     332 341 356       *                     533 545 557       *                     608 614 677 685   *                     712 726 761 773   *                     819 837 851 874   * 

* *

See Wikipedia: * Sudoku for more information on Sudoku. * *

The algorithm employed is similar to the standard backtracking * eight * queens algorithm. * * @version 1.0 * @author Bob Carpenter */ public class Sudoku { /** * Print the specified Sudoku problem and its solution. The * problem is encoded as specified in the class documentation * above. * * @param args The command-line arguments encoding the problem. */ public static void main(String[] args) { int[][] matrix = parseProblem(args); writeMatrix(matrix); if (solve(0,0,matrix)) // solves in place writeMatrix(matrix); else System.out.println("NONE"); } static boolean solve(int i, int j, int[][] cells) { if (i == 9) { i = 0; if (++j == 9) return true; } if (cells[i][j] != 0) // skip filled cells return solve(i+1,j,cells); for (int val = 1; val

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.