Databases
StackOverflow2013
Postsdbo
POOptimizing the backtracking algorithm solving Sudoku
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POOptimizing the backtracking algorithm solving Sudoku
    primarykey
    data
    text
    <p>I'm hoping to optimize my backtracking algorithm for my Sudoku Solver.</p> <hr> <p>What it does now:</p> <p>The recursive solver function takes a sudoku puzzle with various given values.</p> <p>I will scour through all the empty slots in the puzzle, looking for the slot that has the least possibilities, and get the list of values.</p> <p>From the list of values, I will loop through it by placing one of the values from the list in the slot, and recursively solve it, until the entire grid is filled.</p> <hr> <p>This implementation still takes incredibly long for some puzzles and I hope to further optimize this. Does anyone have any ideas how I might be able to further optimize this?</p> <hr> <p>Here's my code in Java if you're interested.</p> <pre class="lang-java prettyprint-override"><code>public int[][] Solve(int[][] slots) { // recursive solve v2 : optimization revision int[] least = new int[3]; least[2] = Integer.MAX_VALUE; PuzzleGenerator value_generator = new PuzzleGenerator(); LinkedList&lt;Integer&gt; least_values = null; // 1: find a slot with the least possible solutions // 2: recursively solve. // 1 - scour through all slots. int i = 0; int j = 0; while (i &lt; 9) { j = 0; while (j &lt; 9) { if (slots[i][j] == 0) { int[] grid_posi = { i, j }; LinkedList&lt;Integer&gt; possible_values = value_generator .possibleValuesInGrid(grid_posi, slots); if ((possible_values.size() &lt; least[2]) &amp;&amp; (possible_values.size() != 0)) { least[0] = i; least[1] = j; least[2] = possible_values.size(); least_values = possible_values; } } j++; } i++; } // 2 - work on the slot if (least_values != null) { for (int x : least_values) { int[][] tempslot = new int[9][9]; ArrayDeepCopy(slots, tempslot); tempslot[least[0]][least[1]] = x; /*ConsoleInterface printer = new gameplay.ConsoleInterface(); printer.printGrid(tempslot);*/ int[][] possible_sltn = Solve(tempslot); if (noEmptySlots(possible_sltn)) { System.out.println("Solved"); return possible_sltn; } } } if (this.noEmptySlots(slots)) { System.out.println("Solved"); return slots; } slots[0][0] = 0; return slots; } </code></pre>
    singulars
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. PTQuestion
    1. USPang
    1. USnubela
    plurals
    1. This table or related slice is empty.
    1. PL
      singulars
      1. LTLinked
    1. This table or related slice is empty.
    1. PO
      singulars
      1. PTAnswer
    2. PO
      singulars
      1. PTAnswer
    3. PO
      singulars
      1. PTAnswer
    1. VO
      singulars
      1. POOptimizing the backtracking algorithm solving Sudoku
      1. USIndy9000
      1. VTFavorite
    2. VO
      singulars
      1. POOptimizing the backtracking algorithm solving Sudoku
      1. This table or related slice is empty.
      1. VTUpMod
    3. VO
      singulars
      1. POOptimizing the backtracking algorithm solving Sudoku
      1. This table or related slice is empty.
      1. VTUpMod
    1. COSee also: http://stackoverflow.com/questions/1518335/
      singulars
      1. POOptimizing the backtracking algorithm solving Sudoku
      1. USJonathan Leffler
    2. COJust as a comment on style, why use the 'i = 0; while (i < 9) { ++i; }' instead of 'for (i = 0 ; i < 9 ; ++i)'. The latter is more conventional and makes the code quicker to understand.
      singulars
      1. POOptimizing the backtracking algorithm solving Sudoku
      1. USSkizz
    3. COJust out of interest, how long is "incredibly long"? How fast does the program run for other puzzles?
      singulars
      1. POOptimizing the backtracking algorithm solving Sudoku
      1. USDan Dyer
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload