|
leonardo - July 29th, 2008
|
| This page shows various algorithms to solve the N-Queens problem:
http://c2.com/cgi/wiki?EightQueensInManyProgrammingLanguages
This is the shorter solver written in C that I have composed (from the original C code of that page), it's 195 bytes long:
typedef unsigned u;u s(u L,u C,u R,u N){u b;if(~C)for(u
S=L|C|R;~0U!=S;b=~S&(S+1),S|=b,N=s((L|b)<<1,C|b,(R|b)>>
1,N));else N++;return N;}main(int n,char**v){printf("%u"
,s(0,~0U>>atoi(v[1]),0,0));}
It accepts the board size in input, and outputs the number of queens.
Using GCC you can compile it with this (ignoring the warnings):
gcc -O3 -s -std=c99 -fprofile-generate nq.c -o nq
Followed by a run with n for example 16, followed by:
gcc -O3 -s -std=c99 -fprofile-use nq.c -o nq
Beside being very short it's pretty fast too. You have to work a lot to write a faster solver. For example, with N=16 finds the correct result 14_772_512 in 17.85 seconds on a 2 GHz Dual Core CPU, using 1 core, 32 bit compiled.
The program as is works up to N=18, finding the 666_090_624 solutions. The result for N=19 requires more than 32 bits to be represented, so you have to replace the 0U with 0UL, atoi() with atol(), the u with typedef unsigned long logn (and maybe a litte more, it may need around 2 hours of time to compute the result with N=19 because each times N grows by one, it requires about 8.1 times more time to run, so I haven't tested it much for sych inputs), this makes the code a little longer.
The same algorithm for the Python Psyco runs about 100 times slower (but it's fast still for being a Python program), but you need to add a & 0xFFFFFFFF to reduce the precision of the numbers (note that on 32-bit Python version 2.x the value 0xFFFFFFFF is a long):
import psyco, sys
def search(lb, cb, rb, cnt):
if cb == 0xFFFFFFFF:
cnt += 1
else:
bs = lb | cb | rb
while bs != 0xFFFFFFFF:
b = ~bs & (bs + 1)
bs |= b
cnt = search(((lb | b) << 1) & 0xFFFFFFFF,
cb | b, (rb | b) >> 1, cnt)
return cnt
psyco.full()
print search(0, 0xFFFFFFFF >> int(sys.argv[1]), 0, 0)
The faster C program I have found (http://jsomers.com/nqueen_demo/nqueens.html ) needs about 8 seconds with N=16, so it's just a little more then two times faster (but it's more complex and much longer, around 400 lines with comments). | comments: Leave a comment   |
| In the last versions of my D language libs I have re-written maybe for the 4-th time the function and the iterator to flatten a given iterable in an eager/lazy way, and this time I think the code may be as flexible and fast as it gets.
Here I show only a summary of the code relative to the xflatten, that's more interesting. I have removed some checks and extra capabilities, so for the full version take a look into the source code itself (func.d module):
http://www.fantascienza.net/leonardo/so/libs_d.zip
The Xflatten (there's an helper function template xflatten that I don't show here), given a n-dimensional iterable, yields the bottom level items. So for example:
xflatten([1.1, 2.1, 3.1]) ==> 1.1 2.1 3.1
xflatten([[[1, 2], [3]], [[4], [5, 6]]]) ==> 1 2 3 4 5 6
xflatten([xrange(2), xrange(3)]) ==> 0 1 0 1 2
The summarized code is very short:
class Xflatten(TyItems) {
this(TyItems items) {
this.items = items;
}
int opApply(int delegate(ref BaseType!(TyItems)) dg) {
int result;
mixin(XflattenHelper!("items", "result = dg(", "); if (result) goto END;",
IterableLevels!(typeof(items))));
END:
return result;
}
}
XflattenHelper!() is a template that computes a string at compile time, the mixin in D is similar to C macros, it allows to mix-in the string in place, as normal code that will be compiled.
XflattenHelper takes as input the name of an iterable, two parts of a string that contains the instructions to perform on the leaves of the iterable, and the number of levels of the iterable. This number is computed at compile time by another template, IterableLevels. The XflattenHelper code is:
template XflattenHelper(string iterable, string yield_p1, string yield_p2, int level) {
static if (level == 0) {
const string XflattenHelper = "{ " ~ yield_p1 ~ iterable ~ yield_p2 ~ " }";
} else {
const string XflattenHelper = "foreach(" ~ iterable ~ "_x; " ~ iterable ~ ")\n" ~
XflattenHelper!(iterable ~ "_x", yield_p1, yield_p2, level-1);
}
}
So given an iterable like this, that's an array of lazy iterables that yield integers:
[xrange(2), xrange(3)]
Then at compile time XflattenHelper produces code like:
foreach(items_x; items)
foreach(items_x_x; items_x)
{ result = dg(items_x_x); if (result) goto END; }
That's the general and faster way to iterate on the leaves and yield them from the opApply (opApply is the iteration protocol in D).
IterableLevels too is short, but it uses more complex templates:
template IterableLevels(TyIter) {
static if (IsIterable!(TyIter))
const int IterableLevels = 1 + IterableLevels!(BaseType1!(TyIter));
else
const int IterableLevels = 0;
}
Where IsIterable!() is a template that becomes true at compile time if TyIter is the type of something that can be iterated, like an array, a lazy generator class/struct, etc. BaseType1!() allows to "go down one level", and it works with most kind of iterables. For the full code of such tree of templates you can see into the templates.d module of the libs. | | comments: Leave a comment |
| |
|
leonardo - July 29th, 2008
|
|