Please note: the language of this site will now be ENGLISH. Please do not use another language since visitors from different countries will participate in training.

How to get the queens problem to be solven even faster?

I am trying http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&category=315&problem=2136 but I'm running in to the problem of my program not being fast enough, I am timing it on my own computer by letting it count how many possibilities there are without restrictions and my program is able to calculate it within 5 seconds for up to 14, with 15 it's about 25 seconds..

I'm keeping track of which diagonals, columns and rows are taken using an array so calculating whether as position is taken takes linear time, I'm using backtracking per column like has been explained so I'm kind of running out of ideas, does anyone have a hint they can give me?

asked Jun 27, 2012 in Algorithms / Data Structures by bvdbijl

2 Answers

0 votes

Same problem here. First optimalization for me was to just place one queen per column. Second was to keep track of which rows and which 'diagonal rows' were already used, where the coordinate of the first diagonal row is calculated with x+y, the second with x-y.

answered Jun 28, 2012 by niomaster
0 votes

I had this problem too and used the same technique. After using bits in an integer (with binary operators), instead of a boolean array, my program finished in time (about 4.8 seconds).

But I'm interested how people managed to solve it in less then a second. I think they do something like pre-generating, but I'm not sure about that.

answered Jun 29, 2012 by Koensw
NL: NIO UK: BIO Int: IOI
...