Databases
StackOverflow2013
Postsdbo
PO
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PO
    primarykey
    data
    text
    <p>I do not know how you're going to solve the sudoku, but even if you use the brute force method (and so it sounds to me what you describe) you should consider that your data structure is not appropriate.</p> <p>With that I mean that every cell should not just be a number, but a set of numbers (that may be possibly placed there).</p> <p>Hence, the given numbers will be represented as singleton sets, while the empty ones you can initialize with {1,2,3,4,5,6,7,8,9}. And then the goal is to reduce the non-singleton cells until all cells are singletons.</p> <p>(Note that, while solving a sudoku with pencil and paper, one often writes small numbers in the blank cells to keep track of what numbers are possible there, as far as one has solved it.)</p> <p>And then, when "trying the next number" you take the next number from the set. Given cells have no next number, so you can't change them. This way, the difficulties you describe vanish (a bit, at least).</p> <p>------ EDIT, AFTER HAVING LEARNED THAT BRUTE FORCE IS REQUIRED.</p> <p>Your teacher obviously wants to teach you the wonders of recursion. Very good!</p> <p>In that case, we just need to know which cells are given, and which are not.</p> <p>A particular easy way that could be used here is to place a 0 in any non-given cell, as given cells are by definition one of 1,2,3,4,5,6,7,8,9.</p> <p>Now lets think about how to make the recursive brute force working.</p> <p>We have the goal to solve a sudoku with n empty cells. <em>If</em> we had a function that would solve a sudoku with n-1 empty cells (or signal that it is not solvable), then this task would be easy: </p> <pre><code>let c be some empty cell. let f be the function that solves a sudoku with one empty cell less. for i in 1..9 check if i can be placed in c without conflict if not continue with next i place i in c if f() == SOLVED then return SOLVED return NOTSOLVABLE </code></pre> <p>This pseudo code picks some empty cell, and then tries all numbers that fit there. Because a sudoku has - by definition - only a single solution, there are only the following cases:</p> <ul> <li>we picked the correct number. Then f() will find the rest of the solution and return SOLVED.</li> <li>we picked a wrong number: f() will signal that the sudoku is not solvable with that wrong number in our cell.</li> <li>we checked all numbers, but no one was correct: Then we have got an unsolvable sudoku ourselves and we signal this to our caller.</li> </ul> <p>Needless to say, the algorithm rests on the assumption that we only ever place numbers that are not conflicting with the current state. For example, we do not place a <code>9</code> there when in the same row, column or box there is already a <code>9</code>.</p> <p>If we now think about how our mysterious, yet unknown function <code>f()</code> looks like, it turns out that it will be almost the same as what we already have!<br> The only case we have not yet considered is a sudoku with 0 empty cells. This means, if we find that there are no more empty cells, we know that we have just solved the sudoku and return just SOLVED.</p> <p>This is the common trick when writing a recursive function that is supposed to solve a problem. We We are writing solve(), and we know, that the problem is solvable at all. Hence, we can already use the function we are just writing as long as we make sure that with every recursion, the problem somehow gets closer to the solution. At the end, we reach the so called base case, where we can give the solution without further recursion.</p> <p>In our case we know that Sudoku is solvable, moreover, we know it has <em>exactly one</em> solution. By placing a piece in an empty cell, we come closer to the solution (or to the diagnosis that there is none) and give the new, smaller problem recursively to the function we are just writing. The base case is the "Sudoku with 0 empty cells" which actually <strong>is the solution</strong>. </p> <p>(Things get a bit more complicated if there are many possible solutions, but we leave that for the next lesson.)</p>
    singulars
    1. This table or related slice is empty.
    1. POSudoku solver in Java, using backtracking and recursion
      singulars
      1. PTQuestion
    1. PTAnswer
    1. USIngo
    1. USIngo
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    2. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    3. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    1. COYes, I am using a brute force method, as is required by the assignment requirements. And the reason I chose this data structure, was because of a similar example that was in my textbook. We were told that we could implement our own solution, or use the one in the textbook as a starting place. The example in the textbook I am referring to is a backtracking, recursive solution to the '8 queens' problem, which is slightly different than implementing sudoku
      singulars
      1. PO
      1. USCarleton U
    2. COWell, in this case, you don't need a set, but maybe just a flag that tells you if the cell was given or not.
      singulars
      1. PO
      1. USIngo
    3. CODo you have any advice or hints on how such a flag could be implemented?
      singulars
      1. PO
      1. USCarleton U
 

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