[백준 #2580] 스토쿠

개요

---

무조건 +1, -1이 능사는 아니라는 것을 배웠다.

+1, -1했다가 틀림 ㅂㄷㅂㄷ

중복으로 사용하는게 아니면 +,-하지말자

www.acmicpc.net/problem/2580

2580번: 스도쿠

 

코드 (정답, 1984KB, 236ms)

---

/**
 * @name: 스토쿠
 * @link: https://www.acmicpc.net/problem/2580
 * @date 2020-05-07
 * @author sunmon
 * TIP: 
**/
#include <iostream>
#include <vector>
#include <cstring>

using namespace std;
int board[9][9];
const int GARO=0, SERO=1, PAN=2; 
int used[3][9][9+1];    //used[타입][i번째][j]: i번째 가로/세로/네모에 숫자 j가 쓰였는지 여부
const int MAX = 9;

bool toggle(int i, int j, int n){
    int pn = i/3*3 + j/3;
    int& g = used[GARO][i][n], &s=used[SERO][j][n],&p=used[PAN][pn][n];
    g = !g;
    s = !s;
    p = !p;
    return g && s && p;  
}
bool solve(){
    int i = -1, j = -1, pn = -1;
    for(int ii = 0; ii<MAX; ++ii){
        for(int jj= 0; jj<MAX; ++jj){
            if(board[ii][jj]==0){
                i = ii;
                j = jj;
                break;
            }
        }
        if(i != -1) break;
    }
    if(i==-1) return true;  //다 채움

    //하나씩 채우고 다음 빈칸으로 넘어가기
    bool ret = false;
    for(int n = 1; n <= 9; ++n){
        if(toggle(i,j,n)){
            board[i][j] = n;
            if(ret |= solve()) break;
        }
        board[i][j] = 0;
        toggle(i,j,n);
    }
    return ret;
}
int main(){
    memset(board, 0, sizeof(board));
    memset(used, 0, sizeof(used));
    for(int i = 0; i<9; i++){
        for(int j = 0; j<9; j++){
            int k;
            cin >> k;
            board[i][j] = k;
            used[GARO][i][k] = 1;
            used[SERO][j][k] = 1;
            int pn = (i/3)*3 + j/3;
            used[PAN][pn][k] = 1;
        }
    }

    solve();
    for(int i = 0; i<9; i++){
        for(int j = 0; j<9; j++){
            cout << board[i][j] << " ";
        }
        cout << "\n";
    }
}