글 읽기 - 스도쿠

hs9200 3년 전 1

0으로 도배하면 답이 안 나옵니다. (왜 그렇죠?)

0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0

#include <stdio.h>
#include <algorithm>
#define M 1000
using namespace std;
pair <int, int> v[M + 1];
int a[M + 1][M + 1];
int n, m;
int ok = 0;
int b = 0;
bool isok(int ans, int y, int x)
{
	int i, j;
	for (i = 1; i <= 9; i++) 
	{
		if (a[y][i] == ans && x != i)
		{
			return false;
		}
		if (a[i][x] == ans && y != i)
		{
			return false;
		}
	}
	for (i = (((y - 1) / 3) + 1) * 3 - 2; i <= (((y - 1) / 3) + 1) * 3; i++)
	{
		for (j = (((x - 1) / 3) + 1) * 3 - 2; j <= (((x - 1) / 3) + 1) * 3; j++)
		{
			if (a[i][j] == ans && !(y == i && x == j))
			{
				return false;
			}
		}
	}
	return true;
}
void process(int lev)
{
	int i;
	if (lev > b)
	{
		ok = 1;
	}
	else
	{
		for (i = 1; i <= 9 && !ok; i++)
		{
			a[v[lev].first][v[lev].second] = i;
			bool k = isok(i, v[lev].first, v[lev].second);
			if (k == true)
			{
				process(lev + 1);
			}
		}
	}
}
int main(void)
{
	int i, j;
	for (i = 1; i <= 9; i++)
	{
		for (j = 1; j <= 9; j++)
		{
			scanf("%d", &a[i][j]);
			if (a[i][j] == 0)
			{
				b++;
				v[b].first = i;
				v[b].second = j;
			}
		}
	}
	process(1);
	for (i = 1; i <= 9; i++)
	{
		for (j = 1; j <= 9; j++)
		{
			printf("%d ", a[i][j]);
		}
		printf("\n");
	}
	return 0;
}

seico75 3년 전 0

47에 값을 a에 써넣는데, 조건에 맞지 않아서 다시 몇단계 (이전 몇개의 숫자를) 돌아가야하면..

저 써놓은 값 때문에 isok 에서 오 동작을 합니다. (실패가 아닌데 실패로 판단..)

1 2 3 4 5 6 7 8 9

4 5 6 1 2 3 . . .

이렇게 가다가 . . . 에서 모두 실패를 해서 돌아가는데. 그때 . . . 은 다 9로 채워지게 됩니다.

4 5 6 7 8 x 9 9 9

이 단계에서 x에 9가 들어갈 차례인데 이미 뒤에 9들을 채워 놓은 것이 있어서 9가 못들어가면서 위 두줄이 다 9로 차고 실패 (ok == 0)으로 끝납니다.

52.5 라인에 답을 못 찾았으면 0으로 되돌리는 코드를 넣으면 될 것 같습니다.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

스도쿠

hs9200 3년 전 1

seico75 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말