스도쿠

백트레킹으로 구현한 스도쿠

// 3*3 박스를 탐색하기위한 기준점으로 부터 변위차 const int dx[] = {0, 1, 2, 0, 1, 2, 0, 1, 2}; const int dy[] = {0, 0, 0, 1, 1, 1, 2, 2, 2}; // 문제가 풀렸나요? bool solved = false; // 문제를 푼다 // board - 확정된 숫자 판 // candi - 후보 숫자들 void solve(vector<vector<int> > board, vector<vector<int> > candi) { int i, j, k, m; bool loop = true; // 이미 풀렸으면 리턴 if (solved) return; // 일단은 논리적으로 할 수 있는데까지 푼다 while (loop) { loop = false; // 후보 숫자를 좁힌다. for (i = 0; i < 9; i++) { for (j = 0; j < 9; j++) { // (i, j)좌표 // (i, j)좌표에 이미 숫자가 확정되었음 if (board[i][j]) continue; // (i, j)좌표에 아직 숫자가 확정되지 않았음 -> 후보를 좁힌다. // 가로세로 방향에 확정된 숫자가 있으면 이 숫자는 (i, j)의 후보가 아니다. for (k = 0; k < 9; k++) { if (board[i][k]) { candi[i][j] &= ~(1<<board[i][k]); } if (board[k][j]) { candi[i][j] &= ~(1<<board[k][j]); } } // 3*3 사각형안에 확정된 숫자가 있으면 이 숫자는 (i, j)의 후보가 아니다. int y = (i/3)*3; int x = (j/3)*3; for (k = 0; k < 9; k++) { int ny = y + dy[k]; int nx = x + dx[k]; if (board[ny][nx]) { candi[i][j] &= ~(1<<board[ny][nx]); } } // 남은 후보 숫자가 몇개인지 조사한다. int number = 0; int numcandi = 0; for (k = 1; k <= 9; k++) { if (candi[i][j] & (1<<k)) { number = k; numcandi++; } } // 후보가 하나만 남았으면 숫자를 확정한다. if (numcandi == 1) { board[i][j] = number; loop = true; } } } // 유일한 후보를 찾는다. for (i = 0; i < 9; i++) { for (j = 0; j < 9; j++) { // (i, j) 좌표 // 이미 확정되었으면 패스 if (board[i][j]) continue; // 확정되지 않은 경우 for (m = 1; m <= 9; m++) { // 숫자 m이 (i, j)의 후보인가? if (candi[i][j] & (1<<m)) { bool ok1 = true, ok2 = true, ok3 = true; // 가로, 세로 방향에 숫자 m을 후보로 가지는 다른 칸이 있는지 검사 for (k = 0; k < 9; k++) if (k != j && (board[i][k] == m || (candi[i][k] & (1<<m)))) ok1 = false; for (k = 0; k < 9; k++) if (k != i && (board[k][j] == m || (candi[k][j] & (1<<m)))) ok2 = false; // 3*3 사각형 내에 숫자 m을 후보로 가지는 다른 칸이 있는지 검사 int y = (i/3)*3; int x = (j/3)*3; for (k = 0; k < 9; k++) { int ny = y + dy[k]; int nx = x + dx[k]; if (ny == i && nx == j) continue; if (board[ny][nx] == m || (candi[ny][nx] & (1<<m))) ok3 = false; } // 관련된 칸들 중 (i, j)가 숫자 m을 유일하게 후보로 가지는 경우 -> 숫자를 확정한다. if (ok1 || ok2 || ok3) { board[i][j] = m; candi[i][j] = 0; break; loop = true; } } } } } } // 모순이 있는지 검사 // 숫자가 확정되지도 않았고 후보도 없는 칸이 있으면 모순 for (i = 0; i < 9; i++) for (j = 0; j < 9; j++) if (board[i][j] == 0 && candi[i][j] == 0) return; // 관련된 9개의 칸에 동일한 숫자가 2회 이상 나타나면 모순 // 가로, 세로 방향 for (i = 0; i < 9; i++) { int cnt1[10] = {0}; int cnt2[10] = {0}; for (j = 0; j < 9; j++) { cnt1[board[i][j]]++; cnt2[board[j][i]]++; if (board[i][j] && cnt1[board[i][j]] > 1) return; if (board[j][i] && cnt2[board[j][i]] > 1) return; } } // 3*3 사각형 for (int y = 0; y < 9; y += 3) { for (int x = 0; x < 9; x += 3) { int cnt[10] = {0}; for (k = 0; k < 9; k++) { int ny = y + dy[k]; int nx = x + dx[k]; cnt[board[ny][nx]]++; if (board[ny][nx] && cnt[board[ny][nx]] > 1) return; } } } // 모든 칸을 다 찾았는지 검사 bool finish = true; for (i = 0; i < 9; i++) for (j = 0; j < 9; j++) if (board[i][j] == 0) finish = false; // 모든 칸은 다 채웠으면 게임 끝!!! if (finish) { printf("Solve\n"); for (i = 0; i < 9; i++) { for (j = 0; j < 9; j++) { if (j) printf(" "); printf("%d", board[i][j]); } printf("\n"); } solved = true; return; } // 아직 게임이 안 끝났고 논리적으로 더 찾을 수 있는 칸이 없다 // 벡트레킹한다. for (i = 0; i < 9; i++) { for (j = 0; j < 9; j++) { if (board[i][j]) continue; // (i, j)는 아직 숫자가 확정되지 않은 칸 for (k = 1; k <= 9; k++) { if (candi[i][j] & (1<<k)) { // (i, j)가 숫자 m을 후보로 가진다. // 새로운 상태를 저장 vector<vector<int> > nb = board; vector<vector<int> > nc = candi; nb[i][j] = k; nc[i][j] = 0; // 백트렉 solve(nb, nc); } } } } return; } int main() { int i, j, k, m; vector<vector<int> > board(9, vector<int>(9, 0)); vector<vector<int> > candi(9, vector<int>(9, 0)); // 초기상태 for (i = 0; i < 9; i++) { for (j = 0; j < 9; j++) { int num; scanf("%d", &num); if (num == 0) candi[i][j] = (1<<10)-1; else candi[i][j] = 0; board[i][j] = num; } } // 문제를 푼다 solved = false; solve(board, candi); return 0; } <SPAN id=tx_marker_caret></SPAN>