Databases
StackOverflow2013
Postsdbo
PO
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PO
    primarykey
    data
    text
    <p>I'd think of somehow taking into account that most solutions are nothing else but mirrored or rotated versions of other solutions. For example, you don't need to try and put the first queen in every column from left to right. It's probably enough if you only go from left to middle. This would already cut the time by half. If I am not mistaken, then for a 8x8 board, for example, putting the queen in 7th column is going to yield the same set of results as putting it in the 2nd column, only flipped. Why wouldn't it?</p> <p><strong>Adressing the exponential complexity problem:</strong> to be honest, 20 queens on a 20x20 board creates such a huge tree that I don't think there's any optimization capable of getting you an exact result in reasonable time. I just looked it up and there's almost 40 bilions solutions for n=20. See <a href="http://oeis.org/A000170" rel="nofollow">oeis.org/A000170</a> - n=20 has about 17 thousand times more solutions than n=15. I don't think we can optimize your algorithm by this factor. So even if we did our best and got down to as little as 2 seconds for n=15... it still means nearly 10 hours for n=20.</p> <p>You can also think about it this way. If there's 39 029 188 884 solutions for 20x20 board with 20 queens, how much data is it? To remember each solution, you need to store 20 numbers from 1 to 20 (the horizontal position, or the x coordinate of each queen). You need 5 bits to represent a number &lt; 20, hence 5*20 = 100 bits for each solution. 100 bits times 39 029 188 884 means 3634 gigabytes.</p> <p>And that's the amount of data your program would have to generate (I know you don't need to save the solutions, you're just counting them: but you need to generate each of them so you can tick it off). Your teacher cannot reasonably expect you to write a program generating 3634 gigabytes of meaningful data in a heartbeat.</p> <p>There are ways of estimating such a result - for example spreading the queens randomly over and over, and counting how many times you happen to get them in a position satisfying the criteria (none of them attack eachother); maybe 0.0013% of times, for example. Then multiply it by <strong>(n*n)! / (n*(n-1))!</strong> - the number of all possible configurations, and you get an estimation. But that's only an estimation, obviously. The longer you're spreading them haphazardly, the more accurate this estimation will be.</p>
    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. USKonrad Morawski
    1. USKonrad Morawski
    plurals
    1. This table or related slice is empty.
    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. 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. COJust have a problem with my computer and re-install Windows, I'm downloading VB.NET, so I haven't tested yet. But, as you say, the calculate time maybe reduced by half. But, in this case, N = 15 still takes 25s, so if N = 16, how many seconds will it take? I believe not under 2 minutes. And can it run with N = 20?
      singulars
      1. PO
      1. USLuke Vo
    2. COWow, nice, why don't you edit it into your answer, so we can discuss about it without such long comments?
      singulars
      1. PO
      1. USLuke Vo
    3. CO@W.N. OK I did.
      singulars
      1. PO
      1. USKonrad Morawski
 

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