Databases
StackOverflow2013
Postsdbo
PO
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PO
    primarykey
    data
    text
    <p>I've done combinatorial enumeration but not N queens specifically. Here's what I'd try (but again, as Morawski points out, lower your expectations).</p> <ol> <li><p>Replace <code>availableCols</code> with an array listing the remaining columns. Store the diagonals as bit arrays. If there are too many to fit into one word, it's probably worth it to handle separately the diagonals containing only the first few rows (i.e., the ones that are relevant only near the top of the tree). Ideally testing a new queen would take only a couple of instructions. It helps if N is known to an aggressively optimizing compiler.</p></li> <li><p>Use the available <a href="http://en.wikipedia.org/wiki/Dihedral_group" rel="nofollow">dihedral symmetry</a> to enumerate only the lexicographically least solution in each orbit. Recover the overall count via the <a href="http://www.wikipedia.org/wiki/Burnside%27s_lemma" rel="nofollow">lemma that's not Burnside's</a>. Symmetry breaking is expensive enough that there's an art to when to do it, but there's some low hanging fruit (e.g., don't place the queen in the first row in the upper columns). Placing by rows may not be the optimal strategy.</p></li> <li><p>Test <a href="http://www.constraint-programming.com/people/regin/papers/gcc.ps" rel="nofollow">generalized arc consistency</a> at interior nodes of the search tree. This is probably much too involved for homework, but I'm sure something like this is used in the really efficient computations behind the OEIS sequence.</p></li> </ol>
    singulars
    1. This table or related slice is empty.
    1. PO"Put N Queens", can it possible to run within acceptable time with N = 20?
      singulars
      1. PTQuestion
    1. PTAnswer
    1. This table or related slice is empty.
    1. USwizard
    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
    1. COThere is nothing like "remaining columns". There's only thye logic for the first line and symetry. On each new line each colunm is "remaining". Find samples on www and you see that the above implementation is the ideal. Ever tried bit operations versus integers? I think (tried it on my pc) 50 seconds is not bad at all. Eliminating rotations and mirrors again adds significantly to the time.
      singulars
      1. PO
      1. USMartin
    2. CO@Martin _There is nothing like "remaining columns"_ Each column has exactly one queen in the end. _Find samples on www_ These generally aren't written by people who know what they're doing. _Ever tried bit operations versus integers?_ Yes. Bit operations with word parallelism are significantly faster. _Eliminating rotations and mirrors again adds significantly to the time._ That's why there's an art to it. Here there's probably not much point since the max is 8x, but the low hanging fruit is worth it.
      singulars
      1. PO
      1. USwizard
    3. COProbably one can get most of the 8x by figuring out what's in the first and last rows and columns and choosing a suitable lex order that avoids checking beyond the first couple of layers of the tree.
      singulars
      1. PO
      1. USwizard
 

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