NeoMind

NeoMind

I am Ironman.

Hits

[백준/텍스트] 12095번 가장 오래 걸리는 스도쿠 풀이

업데이트:

문제 정보


풀이

문제

백준이는 2580번 스도쿠 문제를 풀기 위해 아래와 같은 코드를 작성했다.

#include <iostream>
using namespace std;
int a[10][10];
bool c[10][10];
bool c2[10][10];
bool c3[10][10];
int n=9;
int cnt=0;
int square(int x, int y) {
    return (x/3)*3+(y/3);
}
bool go(int z) {
    cnt += 1;
    if (cnt >= 10000000) {
        return true;
    }
    if (z == 81) {
        for (int i=0; i<n; i++) {
            for (int j=0; j<n; j++) {
                cout << a[i][j] << ' ';
            }
            cout << '\n';
        }
        return true;
    }
    int x = z/n;
    int y = z%n;
    if (a[x][y] != 0) {
        return go(z+1);
    } else {
        for (int i=1; i<=9; i++) {
            if (c[x][i] == 0 && c2[y][i] == 0 && c3[square(x,y)][i]==0) {
                c[x][i] = c2[y][i] = c3[square(x,y)][i] = true;
                a[x][y] = i;
                if (go(z+1)) {
                    return true;
                }
                a[x][y] = 0;
                c[x][i] = c2[y][i] = c3[square(x,y)][i] = false;
            }
        }
    }
    return false;
}
int main() {
    for (int i=0; i<n; i++) {
        for (int j=0; j<n; j++) {
            cin >> a[i][j];
            if (a[i][j] != 0) {
                c[i][a[i][j]] = true;
                c2[j][a[i][j]] = true;
                c3[square(i,j)][a[i][j]] = true;
            }
        }
    }
    go(0);
    return 0;
}

변수 cnt에 저장된 값이 가장 큰 스도쿠 퍼즐을 출력하는 프로그램을 작성하시오. 문제의 점수는 cnt에 저장된 값이다.

  • 자세한 문제 및 입출력 예제는 상단의 문제 출처(백준 홈페이지)를 참조해주세요

코드

8 0 0 0 0 0 0 0 0
0 0 3 6 0 0 0 0 0
0 7 0 0 9 0 2 0 0
0 5 0 0 0 7 0 0 0
0 0 0 0 4 0 7 0 0
0 0 0 1 0 0 0 3 0
0 0 1 0 0 0 0 0 8
0 0 8 5 0 0 0 1 0
0 9 0 0 0 0 4 0 0

설명

코드가 적혀있지만 딱히 해석할 필요 없이, 그냥 푸는데 가장 오래걸리는 스도쿠를 출력하면 됩니다.

개인적으로 만들어서 제출해봤으나 역시 관련 이론도 잘 모르고 테스트도 안해본 상태로는 통과가 되지 않더군요

저는 링크에 나오는 아래와 같은 스도쿠

를 제출했었는데, 72097점을 받았었습니다.

이 스도쿠를 기준으로 칸을 몇칸 추가로 비워서 통과한 코드가 위의 코드입니다.

무턱대고 칸을 지우게 되면 정답이 여러개가 나오는 스도쿠가 될 수 있어 유의해야합니다.

결과적으로 수동 브루트 포싱…. 을 통해 통과했습니다

댓글남기기

참고