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;
}