BaekJoon 2580 스도쿠

Link https://www.acmicpc.net/problem/2580

소스결과 1988 KB / 104 ms

출처 Backjoon, 한국정보올림피아드 시,도 지역본선 초등부, 중등부

언어 C++ 17

 

설명

두뇌 회전으로 많이 푸는 스도쿠를 백트래킹을 이용해서 정답을 찾는 문제

스도쿠의 규칙인 가로, 세로, 박스 안에는 1 ~ 9 까지 단 1개씩만 들어가야 한다. 를 만족시키기만 하면 된다.

 

가로에서 필요한 값과 세로에서 필요한 값, 박스에서 필요한 값으로 나누어서 세 개 에서 전부 필요한 값만 사용하면 된다.

스도쿠 규칙만 안다면 크게 어렵지는 않았다.

 

어렵지는 않지만 그래도 한번에 통과하니 뿌-듯

 

알고리즘

1. 스도쿠 배열을 입력 받으면서 빈 칸의 위치 따로 저장한다.

2. 저장한 빈칸의 위치를 확인하면서 빈칸의 위치의 가로, 세로, 박스 안에서 이미 사용된 값을 확인한다.

3. 가로, 세로, 박스 에서 전부 사용되지 않은 값을 1부터 순서대로 넣으며 재귀 호출한다.

4. 마지막 위치까지 간 경우 출력하고 종료시킨다.

 

소스코드

#include <iostream>

using namespace std;

struct Point
{
	short x;
	short y;

	Point() {};
	Point(short x, short y) : x(x), y(y) {};
};

bool isOver;
short board[9][9];
Point emptySpace[81];
int zeroCount;

void func(int pos)
{
	if (pos == zeroCount)
	{
		for (int i = 0; i < 9; i++)
		{
			for (int j = 0; j < 9; j++)
				cout << board[i][j] << ' ';
			cout << '\n';
		}
		isOver = true;
	}
	else
	{
		short curX = emptySpace[pos].x;
		short curY = emptySpace[pos].y;

		bool row[10] = {};
		bool col[10] = {};
		bool box[10] = {};

		for (int i = 0; i < 9; i++)
			row[board[curX][i]] = true;

		for (int i = 0; i < 9; i++)
			col[board[i][curY]] = true;

		for (int i = 0; i < 3; i++)
			for (int j = 0; j < 3; j++)
				box[board[(curX / 3) * 3 + i][(curY / 3) * 3 + j]] = true;

		for (int i = 1; i < 10; i++)
			if (!row[i] && !col[i] && !box[i] && !isOver)
			{
				board[curX][curY] = i;
				func(pos + 1);
				board[curX][curY] = 0;
			}
	}
}


int main()
{
	int startX = -1, startY = -1;

	for (int i = 0 ;i < 9; i++)
		for (int j = 0; j < 9; j++)
		{
			cin >> board[i][j];
			if (board[i][j] == 0)
				emptySpace[zeroCount++] = Point(i, j);
		}

	func(0);
	
	return 0;
}