pku2918.cpp

这是ACM 方面的资料 是PKU的 北京大学的出来的

#include <stdio.h>
#include <string.h>

char map[9][10];
bool v_row[9][10], v_col[9][10], v_box[9][10];
int spx[81], spy[81], spcnt;
bool found;

int box_id(int i, int j)
{
	return (i / 3) * 3 + (j / 3);
}

void backset(int i, int j, int p)
{
	v_row[i][p] = 0;
	v_col[j][p] = 0;
	v_box[box_id(i, j)][p] = 0;
	map[i][j] = '0';
}

int set(int i, int j, int p)
{
	if (v_row[i][p])
		return 0;
	if (v_col[j][p])
		return 0;
	if (v_box[box_id(i, j)][p])
		return 0;
	v_row[i][p] = 1;
	v_col[j][p] = 1;
	v_box[box_id(i, j)][p] = 1;
	map[i][j] = p + '0';
	return 1;
}

void show()
{
	int i;
	for (i = 0; i < 9; i++)
		printf("%s\n", map[i]);
	printf("\n");
}

void init()
{
	int i, j;
	for (i = 0; i < 9; i++)
		scanf("%s", map[i]);
	memset(v_row, 0, sizeof(v_row));
	memset(v_col, 0, sizeof(v_col));
	memset(v_box, 0, sizeof(v_box));
	spcnt = 0;
	for (j = 0; j < 9; j++)
	{
		for (i = 0; i < 9; i++)
		{
			if (map[i][j] == '0')
			{
				spx[spcnt] = i;
				spy[spcnt] = j;
				spcnt++;
			}
			else
			{
				set(i, j, map[i][j] - '0');
			}
		}
	}
	found = 0;
}

void Solve(int n)
{
	int x, y, i;
	if (found)
		return;
	n--;
	if (n == -1)
	{
		found = 1;
		show();
		return;
	}
	x = spx[n];
	y = spy[n];
	for (i = 1; i <= 9; i++)
	{
		if (set(x, y, i))
		{
			Solve(n);
			backset(x, y, i);
		}
	}
}


int main()
{
	int T, t;
	scanf("%d", &T);
	t = 0;
	while (T--)
	{
		init();
		printf("Scenario #%d:\n", ++t);
		Solve(spcnt);
	}
	return 0;
}