Есть здесь кто-нибудь с Google Code Jam?

Задача следующая:

Задано квадратное шахматная доска заданного размера, некторые клетки 
сломаны, т.е. на них ставить слонов нельзя. Требуется подсчитать 
сколькими способами можно расставить на доске k слонов, чтобы они 
друг друга не били. Вернуть только младшие 4 десятичных разряда этого
числа.

Размер доски до 16. Легко сделать тупой перебор, что я собственно и
сделал, но он уже на доске размером 6 начинает тупить.

Говорят что можно сделать умный перебор. Т.е. разделить доску на
чёрные и белые клетки и решать эти задачи отдельно.

А ещё есть и одно ацкое решение, которое я никак не могу понять,
хотя даже есть исходник...

Например:

".."
".."

Можно расставить 0 слонов одним способом. 
Одного слона четырьмя способами.
Двух слонов четырьмя способами.
Трёх и более слонов нулём способов.

"..."
"..."
"..."

Трёх слонов можно расставить 26 способами.

"..."
".##"
"..."

Одного слона сожно расставить 7 способами.

Есть решение, хорошее, победитель в моём дивизионе:

#include <iostream>
#include <sstream>
#include <string>
#include <vector>

using namespace std;

int n, k;
char a[15][15];
int memo[15][1<<15];

class Bishops
{
public:
	int rec(int d1, int placed, int used)
	{
		if (d1 == 2 * n - 1)
			return placed == k;
		int &ret = memo[d1][used];
		if (ret >= 0)
			return ret;
		
		ret = rec(d1 + 1, placed, used);

		for (int d2 = 0; d2 < 2 * n - 1; ++d2)
		{
			if ((used >> d2) & 1)
				continue;
			if ((d1 + d2 - n + 1) % 2)
				continue;
			int c = (d1 + d2 - n + 1) / 2;
			int r = d1 - c;
			if (r < 0 || r >= n || c < 0 || c >= n)
				continue;
			if (a[r][c] == '#')
				continue;
			ret += rec(d1 + 1, placed + 1, used | (1 << d2));
		}
		ret %= 1000;
		return ret;
	}

	int count(int K, vector<string> board)
	{
		k = K;
		n = board.size();
		for (int i = 0; i < n; ++i)
			for (int j = 0; j < n; ++j)
				a[i][j] = board[i][j];
		if ( k > 15 )
			return 0;

		memset(memo, -1, sizeof memo);
		return rec(0, 0, 0);
	}
};

int main()
{
	vector<string> board;
	board.push_back("#");
//	board.push_back("#");
//	board.push_back("#.");

	Bishops bishops;

	cout << bishops.count(1, board) << endl;

	return 0;
}

Тут мутят что-то хитрое, т.е. перебор идёт по диагоналям, т.е. сразу
понятно что одну диагональ может занимать только один слон. 

Используется кэш и рекурсия. И вот что собственно говоря мы кэшируем
и как работает эта рекурсия до меня никак и не доходит... :-(

Насколько я понял функция rec() обозначает что-то типа количество вариантов какими можно расставить слонов на поле, начиная с диагонали
d1 при условии что уже placed слонов размещено и used это битовая
маска занятых перпендикулярных диагоналей...

klaus, тебя звать не Константин? :-)

Там это качественно описано. И доходчиво.

Я спросил есть ли здесь кто-нибудь с CodeJam, кто наверное, уже мог решить эту задачу. Хотел поговорить на эту тему. Русские там есть. Могли и на ЛОРе тусоваться.