N-Queens in 140 characters

Have you heard of n-queens? It's one of the most exiting algorithms out there. It basically answers the questions, how many queens would fit in an n x n board without have the queens interfere with each other, i.e. no vertical, horizontal, or diagonal line-of-sight between queens.

There's a lot a ways in which you can arrive to solution. However, there's a solution that could fit in a tweet! That's right, less than 140 chars.

function q(n) {  
    x = 0, a = (1 << n) - 1;

    function i(l, c, r) {
        if (c == a) x++;
        var p = ~(l | c | r) & a,
            b;
        for (; p; p -= b) {
            b = p & -p;
            i((l | b) << 1, c | b, (r | b) >> 1)
        }
    }
    i();
    return x
}

I recommend reading this wired article to know more about his algorythm and about the world record holders for finding a solution for a really large board size.

comments powered by Disqus