스도쿠풀기
문제 해석
Cross-hatching 방법을 이용하여 푸는 프로그램을 작성하는 문제입니다.
Cross-hatching 방법은 다음의 과정을 거칩니다.
- 숫자를 하나 고릅니다.
- 그 숫자가 등장하는 가로줄이나 세로줄 또는 3x3박스에 선을 긋습니다.
- 3x3박스에 고른 숫자가 들어갈 수 있는 칸이 한 칸일 때, 그 숫자를 채웁니다.
입력으로 주어지는 스도쿠 퍼즐이 규칙을 지키지 않는 경우가 입력으로 주어질 수 있습니다.
만약 올바른 스도쿠 퍼즐이고, 모순이 일어나지 않는다면 cross-hatching만을 이용해서 푼 결과를 출력합니다.
그렇지 않다면 “ERROR”를 출력합니다.
설계(20)
생각할 점이 많은 구현문제입니다.
우선, 각 행과 열 그리고 3x3칸에 포함된 숫자를 확인할 수 있는 col,row,cross배열을 사용합니다.
그 후, 다음 두가지 동작을 반복실행합니다.
-
스도쿠퍼즐의 모순 확인
- 이전에 스도쿠 상태를 체크할 때, 모순이 되는지 먼저 체크합니다.(이미 체크되어있는 상태가 다시 나오는 경우)
- 3x3박스를 기준으로 아직 들어있지 않은 숫자를 최소 한군데 이상에 집어넣을 수 있는지 체크합니다.
- 만약 한군데에도 넣을 수 없는 경우에 “ERROR”를 출력합니다.
-
cross-hatching 기법 사용
- 먼저, 3x3박스를 기준(index=0~8)으로 탐색을 진행합니다.
- 3x3박스에 들어있는 숫자를 제외한 모든 숫자를 기준으로 각 col,row가 체크되어있거나 어떠한 숫자가 채워져있으면 cnt를 증가시킵니다.
- 위의 조건에 맞지않는(비어있는) 칸의 좌표를 저장해놓습니다.
- 각 숫자를 기준으로하여 체크를 한 후, 만약 cnt==8이면 저장해놓은 좌표에 숫자를 저장하도록합니다.
- cnt == 8인 뜻은, 해당 숫자에 대하여 cross checking했을 때 3x3박스에 한 자리만 남는 것을 뜻합니다.
구현(100)
코드
#include <iostream>
using namespace std;
#define MAXN 9
int sdoku[MAXN][MAXN];
bool col[MAXN+1][MAXN];
bool row[MAXN+1][MAXN];
bool cross[MAXN+1][MAXN];
int check(int x, int y){
int idx = 3*(x/3)+y/3;
int tx= x;
int ty = y;
for (int k = 1; k <= 9; k++){
int cnt = 0;
if (cross[k][idx]) continue;
for (int i = 3*(idx/3); i< 3*(idx/3)+3; i++){
for (int j = 3*(idx%3); j <3*(idx%3)+3; j++){
if (col[k][j] || row[k][i] || sdoku[i][j]) cnt++;
else {
tx = i;
ty = j;
}
}
}
if (cnt == 8) {
sdoku[tx][ty] = k;
col[k][ty] = true;
row[k][tx] = true;
cross[k][idx] = true;
return 1;
}
}
return 0;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
for (int i = 0 ; i < MAXN; i++){
for (int j= 0;j<MAXN; j++){
char tmp;
cin >> tmp;
if (tmp>='1' && tmp <='9') sdoku[i][j] = tmp-'0';
}
}
for (int i = 0;i <MAXN; i++){
for (int j= 0;j<MAXN; j++){
if (!sdoku[i][j]) continue;
if (col[sdoku[i][j]][j] || row[sdoku[i][j]][i] || cross[sdoku[i][j]][3*(i/3)+j/3]) {
cout << "ERROR\n";
return 0;
}
col[sdoku[i][j]][j] = true;
row[sdoku[i][j]][i] = true;
cross[sdoku[i][j]][3*(i/3)+j/3] = true;
}
}
while (1){
for (int idx = 0 ; idx < 9; idx++){
int i = 3*(idx/3);
int j = 3*(idx%3);
for (int k = 1; k<=9; k++){
bool possible = false;
if (cross[k][idx]) continue;
for (int x = i; x < i+3 &&!possible; x++){
for (int y = j; y < j+3; y++){
if (!sdoku[x][y]&&!col[k][y] &&!row[k][x]) {
possible = true;
break;
}
}
}
if (!possible){
cout << "ERROR\n";
return 0;
}
}
}
bool flag = false;
for (int idx = 0 ; idx < 9; idx++){
int i = 3*(idx/3);
int j = 3*(idx%3);
int num = check(i,j);
if (num>0){
flag = true;
break;
}
else if (num == -1){
cout <<"ERROR\n";
return 0;
}
}
if (!flag) break;
}
for (int i = 0 ; i<MAXN; i++){
for (int j= 0;j<MAXN; j++){
if (!sdoku[i][j]) cout <<".";
else cout << sdoku[i][j] ;
}
cout <<"\n";
}
return 0;
}
디버깅
주어진 입력의 모순만 체크하는 실수를 하였습니다.
어떠한 경우에 cross-hatching방법으로 숫자를 넣었을 때 모순이 되는 경우가 생길 수 있습니다.
따라서, 매번 체크해주는 수밖에 없습니다.
코드 (대회 solution)
다음 코드는 COCI2008/2009 에 게시된 솔루션 코드입니다.
정말 문제에서 하라는데로 정확히 깔끔하게 구현한 것을 볼 수 있습니다.
모순을 찾는 과정도 반복할 때마다 선언되는 지역변수 배열을 이용하여 쉽게 구현하였습니다.
#include <iostream>
#include <vector>
using namespace std;
char ploca[9][10];
bool cross(int z) {
bool bar_jednom = false;
int red[9] = {0}, stupac[9] = {0}, blok[3][3] = 0;
for ( int r=0; r<9; ++r ) {
for ( int s=0; s<9; ++s ) {
if ( ploca[r][s] == '0'+z ) {
if ( red[r]++ > 0 ) throw 1;
if ( stupac[s]++ > 0 ) throw 1;
if ( blok[r/3][s/3]++ > 0 ) throw 1;
}
}
}
for ( int i=0; i<3; ++i ) {
for ( int j=0; j<3; ++j ) {
if ( blok[i][j] ) continue;
vector<pair<int, int> > mog;
for ( int r=0; r<3; ++r ) {
for ( int s=0; s<3; ++s ) {
if ( ploca[3*i+r][3*j+s] == '.' &&
!red[3*i+r] && !stupac[3*j+s] )
mog.push_back( make_pair(3*i+r, 3*j+s) );
}
}
if ( mog.empty() ) throw 1;
if ( mog.size() == 1 ) {
int r = mog[0].first, s = mog[0].second;
ploca[r][s] = '0'+z;
red[r] = stupac[s] = blok[i][j] = 1;
bar_jednom = true;
}
}
}
return bar_jednom;
}
int main() {
for ( int i=0; i<9; ++i ) cin >> ploca[i];
try {
for ( ;; ) {
bool gotovo = true;
for ( int i=1; i<=9; ++i )
gotovo &= !cross(i);
if ( gotovo ) break;
}
} catch(...) {
puts("ERROR");
return 0;
}
for ( int i=0; i<9; ++i ) cout << ploca[i] << endl;
return 0;
}
제출결과
0 ms
마무리
단순 구현문제였지만 모순을 체크하는 부분에서 논리적 오류를 유발하였습니다.
이를 찾기까지 대회용 test case를 전부 디버깅해서 겨우 통과했기 때문에 사실상 풀지 못한 문제나 매한가지입니다.
추후에, 리뷰를 다시 해봐야할 것 같습니다.