백준 - Sudoku(2239)

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

2239번: 스도쿠

 

 

오랜만에 재밌게 푼 문제

스도쿠 빈칸을 주면 채워주면 된다.

 

파란색 값을 구한다고 하면

가로, 세로, 박스 안에서 겹치지 않는 숫자를 채워주어야 한다.

그럼 가능한 숫자는 여러 개이므로

이를 백트래킹으로 빈칸이 없는 스도쿠가 완성될 때까지 계속 돌려준다.

 

#include <iostream>
#include <vector>
#include <string>
using namespace std;
vector<vector<int>> sudoku;
vector<pair<int, int>> zero_position;

void display();
void backtracking(int idx);
void display() {
	for (int i = 0; i < 9; i++) {
		for (int j = 0; j < 9; j++) {
			cout << sudoku[i][j];
		}
		cout << endl;
	}
}

bool ispossible(int y, int x, int data) {

	for (int i = 0; i < 9; i++) {
		if (i == y) continue;
		if (sudoku[i][x] == data)
			return false;
	}

	for (int i = 0; i < 9; i++) {
		if (i == x) continue;
		if (sudoku[y][i] == data)
			return false;
	}
	int box_y = y / 3;
	int box_x = x / 3;

	for (int i = box_y * 3; i < box_y * 3 + 3; i++) {
		for (int j = box_x * 3; j < box_x * 3 + 3; j++) {
			if (i == y && j == x) continue;
			if (sudoku[i][j] == data) return false;
		}
	}

	return true;
}

void backtracking(int idx) {
	if (idx == zero_position.size()) {
		display();
		exit(0);
	}
	int y = zero_position[idx].first;
	int x = zero_position[idx].second;
	for (int i = 1; i <= 9; i++) {
		if (ispossible(y, x, i)) {
			sudoku[y][x] = i;
			backtracking(idx + 1);
			sudoku[y][x] = 0;
		}
	}
	return;
}

int main() {
	for (int i = 0; i < 9; i++) {
		vector<int> temp_vec;
		string temp;
		cin >> temp;
		for (int k = 0; k < 9; k++)
		{
			temp_vec.push_back(temp[k] - '0');		
			if ((temp[k] - '0') == 0)
				zero_position.push_back(pair<int, int>(i, k));				
		}
		sudoku.push_back(temp_vec);
	}
	backtracking(0);
}