2239 sudoku

์•Œ๊ณ ๋ฆฌ์ฆ˜(๋ฐฑํŠธ๋ž˜ํ‚น)

1. ์นธ์„ ํ•˜๋‚˜์”ฉ ํƒ๋ฐฉํ•˜๋ฉด์„œ, 0์œผ๋กœ ๊ธฐ๋ก๋ผ์žˆ๋‹ค๋ฉด ์ˆ˜์ง, ์ˆ˜ํ‰, 3x3์‚ฌ๊ฐํ˜•์„ ๊ฒ€์‚ฌํ•˜์—ฌ ๊ฐ€๋Šฅํ•œ ์ˆซ์ž๋ฅผ ํ•˜๋‚˜์”ฉ ๋ฝ‘์•„์„œ ๋„ฃ๊ณ  ๋‹ค์Œ ์นธ ๊ฒ€์‚ฌ
2. ๋งŒ์•ฝ 0์œผ๋กœ ๊ธฐ๋ก๋˜์ง€์•Š์€ ์นธ์œผ๋กœ ๊ฐ”๋‹ค๋ฉด ๋‹ค์Œ์นธ์œผ๋กœ ๋„˜๊ฒจ์ฃผ๋˜, ๋งˆ์ง€๋ง‰ ์นธ์ผ ๊ฒฝ์šฐ ์Šค๋„์ฟ ๊ฐ€ ์™„์„ฑ๋œ ๊ฒƒ์ด๋ฏ€๋กœ true๋ฅผ ๋ฐ˜ํ™˜ํ•œ๋‹ค.
3. ๋งˆ์ฐฌ๊ฐ€์ง€๋กœ, ๋„ฃ๊ณ  ๋‹ค์Œ ์นธ์œผ๋กœ ์ด๋™ํ•˜๋Š”๋ฐ, ๋งˆ์ง€๋ง‰์นธ์ผ ๊ฒฝ์šฐ ์Šค๋„์ฟ ๊ฐ€ ์™„์„ฑ๋œ ๊ฒƒ์ด๋ฏ€๋กœ true๋ฅผ ๋ฐ˜ํ™˜ํ•œ๋‹ค.
4. ์ตœ์†Œ์ผ๋•Œ๋ฅผ ๋ฐ˜ํ™˜ํ•˜๋Š” ๊ฒƒ์ด๋ฏ€๋กœ ๋จผ์ € ๊ฒ€์‚ฌํ•˜๋Š” ์นธ์„ ์™ผ์ชฝ ์œ„๋กœํ•˜๊ณ , 1๋ถ€ํ„ฐ ๊ฒ€์‚ฌํ•˜์—ฌ ๊ฐ€๋Šฅํ•œ ๊ฑธ ๋„ฃ์œผ๋ฉด ๋œ๋‹ค.

๊ตฌํ˜„

1. ๋‚ด๊ฐ€ ๊ตฌํ˜„ํ•œ ๊ฑด ๋งจ์ฒ˜์Œ์— ๊ฐ€๋Šฅํ•œ ์ˆซ์ž๋ฅผ ๋จผ์ € ๋ฝ‘๊ณ , ๊ทธ ๊ฐ€๋Šฅํ•œ ์ˆซ์ž๋งŒ ๊ฐ€์ง€๊ณ  ๊ฒ€์‚ฌํ•˜๊ณ  ๋„ฃ๊ณ  ๋นผ๊ณ  ํ–ˆ๋‹ค.
2. ๋•๋ถ„์— ์‹œ๊ฐ„์ด ์ข€ ์ค„์—ˆ์ง€๋งŒ, ์ฒดํฌํ•˜๋Š”๋ฐ ๋งค๋ฒˆ ์ฒดํฌํ•˜์—ฌ ์‹œ๊ฐ„์ด ์ข€ ๊ฑธ๋ฆฐ ๊ฑฐ ๊ฐ™๋‹ค.
3. ์ฒดํฌํ•˜๋Š” ๊ฑธ ์ข€ ๋” ๊ฐ„๊ฒฐํžˆ ํ•˜๋Š” ๋ฐฉ๋ฒ•์€ ๊ฐ ์นธ๋งˆ๋‹ค 3๊ฐœ์˜ 9๊ฐœ์˜ int์›์†Œ๋ฅผ ๊ฐ€์ง€๋Š” ๋ฐฐ์—ด์„ ๊ฐ€์ง„๋‹ค.
	ex) int checkMap[WIDTH][WIDTH][3][WIDTH+1];
 ๊ทธ๋ฆฌ๊ณ  ๋งจ ์ฒ˜์Œ์—, ์ˆซ์ž๋ฅผ ๋„ฃ์—ˆ์„ ๋•Œ๋งˆ๋‹ค ๊ฐ๊ฐ ์ˆ˜์ง, ์ˆ˜ํ‰, 3x3 ์‚ฌ๊ฐํ˜•์˜ ๊ฐ ์นธ์— ์›๋ž˜ ๊ฐ€์ง€๊ณ  ์žˆ๋˜ ์ˆซ์ž ๋˜๋Š” ๋„ฃ์€ ์ˆซ์ž๋ฅผ ๊ธฐ๋กํ•œ๋‹ค.
 ์ˆ˜ํ‰์ผ ๊ฒฝ์šฐ checmMap[row][col][0][value], ์ˆ˜์ง์ผ ๊ฒฝ์šฐ checkMap[row][col][1][value], ์‚ฌ๊ฐํ˜•์ผ๊ฒฝ์šฐ checkMap[row][col][2][value]
 ์ด๋ ‡๊ฒŒํ•˜๋ฉด ๋„ฃ์„ ์ˆ˜ ์žˆ๋Š”์ง€ ๊ฒ€์‚ฌํ•  ๋•Œ ๊ทธ๋ƒฅ 3๊ฐœ์˜ ๋ฐฐ์—ด์„ ๊ฒ€์‚ฌํ•˜์—ฌ ์žˆ๋Š”์ง€๋งŒ ํ™•์ธํ•˜๋ฉด ๋˜๋ฏ€๋กœ ๋” ๊ฐ„๊ฒฐํ•ด์ง„๋‹ค.
 ๋˜, ์ฒ˜์Œ์— ๊ฐ€๋Šฅํ•œ ์ˆซ์ž๋ฅผ ๋จผ์ € ๋ฝ‘์ง€ ์•Š์•„๋„ ๋œ๋‹ค.  ๋ฌผ๋ก  false๊ฐ€ ๋ฐ˜ํ™˜๋์„ ์‹œ, ๋‹ค์‹œ 0์œผ๋กœ ๋ฐ”๊ฟ”์ค„ ํ•„์š”๋„ ์žˆ๋‹ค.
-> ๋‚ด์ผ ํ•ด๋ณด์ž.

์ฝ”๋“œ

#include <iostream>
#include <cstring>
#include <cmath>
#define WIDTH 9
 
using namespace std;
 
int map[WIDTH][WIDTH];
int possibleNum[WIDTH][WIDTH][WIDTH+1];
 
void generatePossibleNum();
bool solveSudoku(int row, int col);
bool checkVertical(int row, int col, int value);
bool checkHorizontal(int row, int col, int value);
bool checkSquare(int row, int col, int value);
 
int main() {
	int input[WIDTH];
	for (int i = 0; i < WIDTH; i++)
			cin >> input[i];
	for (int i = 0; i < WIDTH; i++) {
		for (int j = WIDTH - 1; j >=0; j--) {
			map[i][j] = input[i] % 10;
			input[i] /= 10;
		}
	}
	generatePossibleNum();
	solveSudoku(0,0);
 
	for (int i = 0; i < WIDTH; i++) {
		for (int j = 0; j < WIDTH; j++)
			cout << map[i][j];
		cout << endl;
	}
}
 
void generatePossibleNum() {
	for (int i = 0; i < WIDTH; i++)
		for (int j = 0; j < WIDTH; j++)
			if (map[i][j] == 0) {
				for (int k = 1; k <= WIDTH; k++)
					possibleNum[i][j][k] = k;
				for (int vert = 0; vert < WIDTH; vert++)
					possibleNum[i][j][map[vert][j]] = 0;
				for (int horiz = 0; horiz < WIDTH; horiz++)
					possibleNum[i][j][map[i][horiz]] = 0;
			}
 
	for (int i = 0; i < 3; i++) {
		for (int j = 0; j < 3; j++) {
			int row = i * 3, col = j * 3;
			for (int r = 0; r < 3; r++) {
				for (int c = 0; c < 3; c++) {
					for (int r2 = 0; r2 < 3; r2++)
						for (int c2 = 0; c2 < 3; c2++)
							possibleNum[row + r][col + c][map[row + r2][col + c2]] = 0;
				}
			}
		}
	}
}
 
bool solveSudoku(int row, int col) {
	if (map[row][col] != 0) {
		if (col < WIDTH - 1)
			return solveSudoku(row, col + 1);
		else if (row < WIDTH - 1)
			return solveSudoku(row + 1, 0);
		else
			return true;
	}
 
	for (int i = 1; i <= WIDTH; i++) {
		if (possibleNum[row][col][i] != 0 && checkVertical(row, col, i) && checkHorizontal(row, col, i) && checkSquare(row, col, i)) {
			map[row][col] = i;
			if (col < WIDTH - 1) {
				if (solveSudoku(row, col + 1))
					return true;
			}
			else if (row < WIDTH - 1) {
				if (solveSudoku(row + 1, 0))
					return true;
			}
			else
				return true;
			map[row][col] = 0;
		}
	}
	return false;
}
 
bool checkVertical(int row, int col, int value) {
	for (int vert = 0; vert < WIDTH; vert++) {
		if (map[vert][col] == value)
			return false;
	}
	return true;
}
bool checkHorizontal(int row, int col, int value) {
	for (int horiz = 0; horiz < WIDTH; horiz++) {
		if (map[row][horiz] == value)
			return false;
	}
	return true;
}
bool checkSquare(int row, int col, int value) {
	int sr = row / 3, sc = col / 3;
	sr *= 3;
	sc *= 3;
 
	for (int r = 0; r < 3; r++) {
		for (int c = 0; c < 3; c++) {
			if (map[sr + r][sc + c] == value)
				return false;
		}
	}
	return true;
}