Databases
StackOverflow2013
Postsdbo
PO
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PO
    primarykey
    data
    text
    <p>Instead of trying to place a queen for each square, which is very inefficient (<code>2^(n*n)</code>), you might want to modify the second <code>solveQueens</code> function to try placing at most one queen for each row. In other words, the longer <code>solveQueens</code> function will try every possible column per row, and move on to the next row.</p> <p>Another point is, the <code>board</code> variable to the second <code>solveQueens</code> function is modified in place, so we dont actually have to return it. Instead, we can simply return a <code>true</code> or <code>false</code> value to indicate if there is a solution.</p> <p>So the first <code>solveQueens</code> function can be changed to:</p> <pre><code>static void solveQueens(int n) { boolean[][] board = new boolean[n][n]; // boolean return value from second solveQueens function boolean solved = solveQueens(board, n); if (solved) { for (int i = 0; i &lt; board.length; i++) { for (int j = 0; j &lt; board.length; j++) { if (board[i][j]) { System.out.printf("%s %s\n", i, j); } } } else { System.out.printf("No solution for board of size %d\n", n); } } </code></pre> <p>And the second modified <code>solveQueens</code> function, which recursively goes down each row, and tries all possible columns for each row:</p> <pre><code>static boolean solveQueens(boolean[][] board, int row, int n) { // we have a queen for each row, done if (row &gt;= n) { return board; } // for the current row, try placing a queen at column 0 // if that fails, try placing a queen at column 1 // if that fails, try placing a queen at column 2, and so on for (int j = 0; j &lt; board.length; j++) { board[row][j] = true; if (isValid(board)) { // placing at (row, j) is valid, try next row boolean boardSolved = solveQueens(board, row + 1, n); if (boardSolved) { // board is solved, yay return boardSolved; } } // cannot place queen at (row, j) with current board configuration. // set board[row][j] back to false board[i][j] = false; } // tried every column in current row and still cant solve, return false return false; } </code></pre> <p>For this portion of the <code>isValid</code> function:</p> <pre><code>//Diagonals for (int i = 0; i &lt; board.length; i++) { for (int j = 0; j &lt; board.length; j++) { if (board[i][j]) { for (int k = 0; k &lt; board.length; k++) { for (int l = 0; l &lt; board.length; l++) { if (((i - k) == (j - l)) &amp;&amp; board[k][l] &amp;&amp; !(k == i &amp;&amp; l == j)) { return false; } } } } } } return true; </code></pre> <p>In the innermost <code>if</code>, you will have to use <code>(abs(i - k) == abs(j - l))</code> instead of <code>(i - k) == (j - l)</code>. An example where the original code will fail is when <code>i = 0</code>, <code>j = 3</code>, <code>k = 3</code>, <code>l = 0</code> (a queen is at row 0 column 3, and a second queen is on row 3 column 0), so <code>(i - k) == 0 - 3 == -3</code> and <code>(j - l) == 3 - 0 == 3</code>, and even though these 2 queens are diagonal to each other, the innermost <code>if</code> will fail to detect it. Using <code>abs(i - k) == abs(j - l)</code> will turn the row distance (<code>i - k</code>) and column distance (<code>j - l</code>) into absolute values, and hence will work.</p> <p>So just change this line:</p> <pre><code>if (((i - k) == (j - l)) &amp;&amp; board[k][l] &amp;&amp; !(k == i &amp;&amp; l == j)) { </code></pre> <p>to:</p> <pre><code>if ((abs(i - k) == abs(j - l)) &amp;&amp; board[k][l] &amp;&amp; !(k == i &amp;&amp; l == j)) { </code></pre> <p>and the <code>isValid</code> function should be fine.</p> <p>Hope that helps!</p>
    singulars
    1. This table or related slice is empty.
    1. POn-queens, checking for a valid board
      singulars
      1. PTQuestion
    1. PTAnswer
    1. USyanhan
    1. USyanhan
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. POn-queens, checking for a valid board
      singulars
      1. PTQuestion
    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. VTAcceptedByOriginator
    1. COYep that fixed it! Thank you so much!
      singulars
      1. PO
      1. USBrandonM
    2. COhaha no problem =)
      singulars
      1. PO
      1. USyanhan
 

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