算数オリンピック問題をバックトラックしてみた

ひさしぶりに日記。
タグとか書き方忘れた。。

はてな若手エンジニアが「算数オリンピック」の問題を解いてみた - はてなブックマークニュース

http://b.hatena.ne.jp/articles/201101/2261
を見て、プログラムで解いてみた。

結果こんな感じ。
７×７マスから結構時間かかる。アルゴリズム悪いのかも。。

placeable patterns of 3 stones in a 2 * 2 cell : 4
time : 0.000000

placeable patterns of 4 stones in a 3 * 3 cell : 45
time : 0.000000

placeable patterns of 5 stones in a 4 * 4 cell : 432
time : 0.000000

placeable patterns of 6 stones in a 5 * 5 cell : 4200
time : 0.125000

placeable patterns of 7 stones in a 6 * 6 cell : 43200
time : 5.562000

placeable patterns of 8 stones in a 7 * 7 cell : 476280
time : 343.938000

ソースコード

#include <cstdio>
#include <memory>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <vector>
#include <deque>
#include <ctime>

using namespace std;

//typedef vector<bool> BoolList;
//typedef deque<bool> BoolList;
typedef vector<int> BoolList;

void print(BoolList cell, const int height, const int width)
{
	printf("\n");
	for(int i=0; i<width; ++i)
	{
		for(int j=0; j<height; ++j)
		{
			printf("%d ", cell[i*width+j]);
		}
		printf("\n");
	}
}

bool check(BoolList cell, const int height, const int width)
{
	// horizontal
	for(int i=0; i<height; ++i)
	{
		bool ok = false;
		for(int j=0; j<width; ++j)
		{
			if (cell[i*width+j])
			{
				ok = true;
				break;
			}
		}
		if (!ok)
			return false;
	}

	// vertical
	for(int i=0; i<width; ++i)
	{
		bool ok = false;
		for(int j=0; j<height; ++j)
		{
			if (cell[i+j*width])
			{
				ok = true;
				break;
			}
		}
		if (!ok)
			return false;
	}

	return true;
}

void place(BoolList cell, const int height, const int width, const int start, const int stone, int *const pPatternNum)
{
	if (!pPatternNum) return;

	if (0==stone)
	{
		if (check(cell, height, width))
		{
			//print(cell);
			++(*pPatternNum);
		}
	}
	else
	{
		for(int i=start; i<height*width; ++i)
		{
			cell[i] = true;
			place(cell, height, width, i+1, stone-1, pPatternNum);
			cell[i] = false;
		}
	}
}

int place_and_countup(const int height, const int width, const int stones)
{
	// initialize
	const int size = height*width;
	BoolList cell(size);
	int patternNum = 0;

	// palce and count patterns
	place(cell, height, width, 0, stones, &patternNum);

	return patternNum;
}

int main()
{
	for(int edge=2; edge<8; ++edge)
	{
		double start = clock();

		int stones = edge+1;
		int patterns = place_and_countup(edge, edge, stones);

		double end = clock();
		double time = (end-start)/CLOCKS_PER_SEC;

		printf("placeable patterns of %d stones in a %d * %d cell : %d\n", stones, edge, edge, patterns);
		printf("time : %f\n", time);
	}

	return 0;
}

アルゴリズムオーダーくらい見積もれるようにならないとなあ・・・