백준 4574 c++ 스도미노쿠

https://www.acmicpc.net/problem/4574

4574번: 스도미노쿠

---

문제

스도쿠가 세계적으로 유행이 된 이후에, 비슷한 퍼즐이 매우 많이 나왔다. 게임 매거진 2009년 7월호에는 스도쿠와 도미노를 혼합한 게임인 스도미노쿠가 소개되었다. 

이 퍼즐은 스도쿠 규칙을 따른다. 스도쿠는 9×9 크기의 그리드를 1부터 9까지 숫자를 이용해서 채워야 한다. 스도쿠는 다음과 같은 조건을 만족하게 숫자를 채워야 한다.

• 각 행에는 1부터 9까지 숫자가 하나씩 있어야 한다.
• 각 열에는 1부터 9까지 숫자가 하나씩 있어야 한다.
• 3×3크기의 정사각형에는 1부터 9가지 숫자가 하나씩 있어야 한다.

스도미노쿠의 그리드에는 1부터 9까지 숫자가 쓰여져 있고, 나머지 72칸은 도미노 타일 36개로 채워야 한다. 도미노 타일은 1부터 9까지 서로 다른 숫자의 가능한 쌍이 모두 포함되어 있다. (1+2, 1+3, 1+4, 1+5, 1+6, 1+7, 1+8, 1+9, 2+3, 2+4, 2+5, ...) 1+2와 2+1은 같은 타일이기 때문에, 따로 구분하지 않는다. 도미노 타일은 회전 시킬 수 있다. 또, 3×3 크기의 정사각형의 경계에 걸쳐서 놓여질 수도 있다.

왼쪽 그림은 퍼즐의 초기 상태를 나타내고, 오른쪽은 퍼즐을 푼 상태이다.

스도미노쿠의 퍼즐의 초기 상태가 주어졌을 때, 퍼즐을 푸는 프로그램을 작성하시오.

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 채워져 있는 도미노의 개수 N이 주어진다. (10 ≤ N ≤ 35) 다음 N개 줄에는 도미노 하나를 나타내는 U LU V LV가 주어진다. U는 도미노에 쓰여 있는 한 숫자이고, LU는 길이가 2인 문자열로 U의 위치를 나타낸다. V와 LV는 도미노에 쓰여 있는 다른 숫자를 나타낸다. 도미노의 위치는 문제에 나와있는 그림을 참고한다. 입력으로 주어지는 도미노의 각 숫자 위치는 항상 인접해 있다.

N개의 도미노의 정보가 주어진 다음 줄에는 채워져 있는 숫자의 위치가 1부터 9까지 차례대로 주어진다. 위치는 도미노의 위치를 나타낸 방법과 같은 방법으로 주어진다.

모든 도미노와 숫자가 겹치는 경우는 없다.

입력의 마지막 줄에는 0이 하나 주어진다.

출력

각 퍼즐에 대해서, 스도쿠를 푼 결과를 출력한다. 항상 답이 유일한 경우만 입력으로 주어진다.

---

#include <iostream>
#include <string>
#include <cstring> //memset
using namespace std;


int arr[9][9];
bool row[9][10];//row[a][b] == true : a열에 b가 있다.
bool col[9][10];
bool miniArr[3][3][10]; //miniArr[a][b][c] == true : c가 [a,b] 3x3 타일안에 있다.
bool tile[10][10];//tile[a][b] == ture : a와 b가 세트인 타일이 있다.

bool fin;
int puzzle = 1;

void reset()
{
	fin = false;
	memset(arr, 0, sizeof(arr));
	memset(row, false, sizeof(row));
	memset(col, false, sizeof(col));
	memset(miniArr, false, sizeof(miniArr));
	memset(tile, false, sizeof(tile));
}

bool checkRow(int posX,int posY, int num1, int num2)//<가로>(posX,posY)에 num1, (posX, posY+1)에 num2를 넣어도 될까?
{
	if (row[posX][num1] == true || row[posX][num2]==true)
		return false;
	if (col[posY][num1] == true || col[posY + 1][num2] == true)
		return false;
	if (miniArr[posX / 3][posY / 3][num1] == true || miniArr[posX / 3][(posY + 1) / 3][num2] == true)
		return false;
	return true;

}

bool checkCol(int posX, int posY, int num1, int num2)//<세로>(posX,posY)에 num1, (posX+1, posY)에 num2를 넣어도 될까?
{
	if (row[posX][num1] == true || row[posX+1][num2] == true)
		return false;
	if (col[posY][num1] == true || col[posY][num2] == true)
		return false;
	if (miniArr[posX / 3][posY / 3][num1] == true || miniArr[(posX + 1) / 3][posY / 3][num2] == true)
		return false;
	return true;
}

void WriteRow(int posX, int posY, int num1, int num2, bool state)
{
	if (state == true)
	{
		arr[posX][posY] = num1;
		arr[posX][posY + 1] = num2;

		row[posX][num1] = true;
		row[posX][num2] = true;

		col[posY][num1] = true;
		col[posY + 1][num2] = true;

		miniArr[posX / 3][posY / 3][num1] = true;
		miniArr[posX / 3][(posY + 1) / 3][num2] = true;

		tile[num1][num2] = true;
		tile[num2][num1] = true;
	}
	else if (state == false)
	{
		arr[posX][posY] = 0;
		arr[posX][posY + 1] = 0;

		row[posX][num1] = false;
		row[posX][num2] = false;

		col[posY][num1] = false;
		col[posY + 1][num2] = false;

		miniArr[posX / 3][posY / 3][num1] = false;
		miniArr[posX / 3][(posY + 1) / 3][num2] = false;

		tile[num1][num2] = false;
		tile[num2][num1] = false;
	}
}

void WriteCol(int posX, int posY, int num1, int num2, bool state)
{
	if (state == true)
	{
		arr[posX][posY] = num1;
		arr[posX + 1][posY] = num2;

		row[posX][num1] = true;
		row[posX + 1][num2] = true;

		col[posY][num1] = true;
		col[posY][num2] = true;

		miniArr[posX / 3][posY / 3][num1] = true;
		miniArr[(posX + 1) / 3][posY / 3][num2] = true;

		tile[num1][num2] = true;
		tile[num2][num1] = true;
	}
	else if (state == false)
	{
		arr[posX][posY] = 0;
		arr[posX + 1][posY] = 0;

		row[posX][num1] = false;
		row[posX + 1][num2] = false;

		col[posY][num1] = false;
		col[posY][num2] = false;

		miniArr[posX / 3][posY / 3][num1] = false;
		miniArr[(posX + 1) / 3][posY / 3][num2] = false;

		tile[num1][num2] = false;
		tile[num2][num1] = false;
	}
}

void dfs(int count)
{
	if (fin)
		return;
	if (count == 81)
	{
		cout << "Puzzle " << puzzle<<'\n';
		for (int i = 0; i < 9; i++)
		{
			for (int j = 0; j < 9; j++)
			{
				cout << arr[i][j];
			}
			cout << '\n';
		}
		fin = true;
		puzzle++;
		return;
	}

	int x = count / 9;
	int y = count % 9;

	if (arr[x][y] != 0)//이미 차있으면 다음으로
		dfs(count + 1);
	else
	{
		//가로 판별
		if (y <= 7 && arr[x][y+1] == 0)
		{
			for (int i = 1; i <= 9; i++)
			{
				for (int j = i + 1; j <= 9; j++)
				{
					if (tile[i][j] == false)
					{
						if (checkRow(x, y, i, j))//가로 만족 시
						{
							WriteRow(x, y, i, j, true);
							dfs(count + 1);
							WriteRow(x, y, i, j, false);
						}
						if (checkRow(x, y, j, i))
						{
							WriteRow(x, y, j, i, true);
							dfs(count + 1);
							WriteRow(x, y, j, i, false);
						}
					}
				}
			}
		}

		//세로 판별 바꿔야됨
		if (x <= 7 && arr[x+1][y] == 0)
		{
			for (int i = 1; i <= 9; i++)
			{
				for (int j = i+1; j <= 9; j++)
				{
					if (tile[i][j] == false)
					{
						if (checkCol(x, y, i, j))//세로 만족 시
						{
							WriteCol(x, y, i, j, true);
							dfs(count + 1);
							WriteCol(x, y, i, j, false);
						}
						if (checkCol(x, y, j, i))
						{
							WriteCol(x, y, j, i, true);
							dfs(count + 1);
							WriteCol(x, y, j, i, false);
						}
					}
				}
			}
		}

	}
}


int main()
{
	//입력
	while (1)
	{
		int N;
		cin >> N;
		if (N == 0)
			break;
		
		for (int i = 0; i < N; i++)
		{
			int num1, num2;
			string pos1, pos2;
			cin >> num1 >> pos1 >> num2 >> pos2;
			int x = pos1[0] - 'A';
			int y = pos1[1] - '0' - 1;
			int x2 = pos2[0] - 'A';
			int y2 = pos2[1] - '0' - 1;

			arr[x][y] = num1;
			arr[x2][y2] = num2;

			//같은 행
			row[x][num1] = true;
			row[x2][num2] = true;
			//같은 열
			col[y][num1] = true;
			col[y2][num2] = true;
			//같은 3x3 칸
			miniArr[x/3][y/3][num1] = true;
			miniArr[x2/3][y2/3][num2] = true;
			//해당 타일 존재 여부
			tile[num1][num2] = true;
			tile[num2][num1] = true;
		}
		for (int i = 1; i <= 9; i++)
		{
			string pos;
			cin >> pos;
			int x = pos[0] - 'A';
			int y = pos[1] - '0' - 1;
			arr[x][y] = i;
			row[x][i] = true;
			col[y][i] = true;
			miniArr[x/3][y/3][i] = true;
		}

		dfs(0);
		reset();
	}
}