스도쿠 문제

[Jinsun-Lee]

추가 풀이한 문제 (리드미에 없음)

• 2239. 스도쿠: ⭐재귀로 칸 전부 채우기, 백트래킹
• → 2580. 스도쿠: 입력만 수정해서 통과 가능

• → 19998. 스도쿠 (Hard): ⭐⭐⭐지옥(knuth's Algorithm X, Dancing Link) &ref 1 2 3 4
• 3763. 스도쿠: 16*16에 알파벳 출력(지옥 개념 검증용으로 좋아)
• 7681. Sudoku: 걍 똑같

[Jinsun-Lee]

재귀로 칸 전부 채우기

bool isPossible(int y, int x, int v) { // v라는 숫자가 가능한지 확인
    for (int i = 1; i <= 9; ++i) {

        if (board[y][i] == v && i != x) return false; // 행열 체크하고, 나랑 같은 좌표는 패스하려고 i!=x
        if (board[i][x] == v && i != y) return false;

        // 3x3
        int ny = (y - 1) / 3 * 3 + 1 + (i - 1) % 3; // 행!!! 
        int nx = (x - 1) / 3 * 3 + 1 + (i - 1) / 3; // 열
        if (board[ny][nx] == v && !(ny == y && nx == x)) return false;
    }
    return true;
}

void backTrack(int dep) {
    if (stop) return;

    if (dep == pos.size()) {
        stop = true;
        print();
        return;
    }

    int y = pos[dep].y;
    int x = pos[dep].x;

    for (int v = 1; v <= 9; ++v) {
        if (isPossible(y, x, v)) {
            board[y][x] = v;
            backTrack(dep + 1);

            if (stop) return; // 조기 종료
            board[y][x] = 0; // 다른 숫자도 쓸 수 있어
        }
    }
    return;
}

[Jinsun-Lee]

지옥(knuth's Algorithm X, Dancing Link)

#include <iostream>
#include <vector>
#include <tuple>
using namespace std;

const int INF = 1e9;

namespace DLX { // 행과 열을 연결한 링크 구조
    struct Node {
        int row; // 원래 어느 행인지
        int size; // 연결된 노드의 수 = 내 아래에 몇 개나 연결되어 있는지?

        Node* column; // 자신이 속한 col의 header = A~F 내 위에가 어디인지

        Node* up; // Dancing Links의 4방향 연결
        Node* down;
        Node* left;
        Node* right;
    };

    void cover(Node* c) { // 해당 열col을 선택하면, 해당 컬럼이랑 연관된 행 제거
        c->right->left = c->left; // left - 나 - right에서 left - right로 양 옆의 포인터를 제거
        c->left->right = c->right; // 이건 헤더 리스트에서 제거하는 거야

        // 컬럼 c를 선택한다 = 이 규칙을 만족하는 후보 숫자를 하나 선택한다라서
        // 선택한 후보 row가 다른 규칙(컬럼)에 영향을 끼치니 이 연결을 제거
        for (Node* it = c->down; it != c; it = it->down) { // 제거한 컬럼 아래로 연결된 것 순회

            for (Node* jt = it->right; jt != it; jt = jt->right) { // it 행에 연결된 다른 컬럼 노드를 순회
                jt->down->up = jt->up;
                jt->up->down = jt->down;

                jt->column->size--; // 남은 후보 수 줄이기
            }
        }
    }

    void uncover(Node* c) { // cover 반대
        // 재귀 탐색에서 c와 관련된 행row들을 다시 복원
        for (Node* it = c->up; it != c; it = it->up) { // 아래로 내려가면서 제거했으니, 올라가며 복구
            for (Node* jt = it->left; jt != it; jt = jt->left) {
                jt->down->up = jt;
                jt->up->down = jt;

                jt->column->size++;
            }
        }

        c->right->left = c; // 다시 추가
        c->left->right = c;
    }

    bool search(Node* head, vector<int>& result) { // 재귀 탐색
        if (head->right == head) return 1; // 모든 규칙을 충족해서 컬럼이 없다는 뜻

        Node* ptr = nullptr;
        int low = INF;

        for (Node* it = head->right; it != head; it = it->right) {
            if (it->size < low) { // 후보가 가장 적은 컬럼부터 선택
                if (it->size == 0) return 0; // 근데 후보가 0이면 실패

                low = it->size;
                ptr = it; // 선택한 컬럼
            }
        }

        cover(ptr); // 선택한 컬럼과 관련 행 제거 + 재귀

        // ptr 컬럼에서 각 후보 열row를 순회
        for (Node* it = ptr->down; it != ptr; it = it->down) {

            result.push_back(it->row);
            for (Node* jt = it->right; jt != it; jt = jt->right) cover(jt->column);

            if (search(head, result)) return 1; // 스도쿠 완성
            else {
                result.pop_back(); // 실패 시 백트래킹
                for (Node* jt = it->left; jt != it; jt = jt->left) uncover(jt->column);
            }
        }

        uncover(ptr); // ptr 컬럼 선택 종료 후 복원

        return 0;
    }

    vector<int> solve(vector<vector<int>> matrix) {
        int n = matrix[0].size(); // DLX 행렬의 열col의 개수 (스도쿠의 경우 324 = 9*9*4개의 제약조건)

        vector<Node> column(n); // 각 열col의 헤더 노드 생성 (A~F)

        Node head; // 헤더 = 마스터 헤드(더미임), 컬럼(각 조건들) 연결용
        head.left = &column[n - 1]; 
        head.right = &column[0]; 

        // 헤더와 컬럼들이 원형 이중 연결 리스트 형태로 연결됨
        for (int i = 0; i < n; ++i) {
            column[i].size = 0; // 컬럼에 연결된 노드 수 (후보 수=아래에 몇 개가 있는지?)

            if (i == 0) column[i].left = &head; // 좌우 컬럼 연결
            else column[i].left = &column[i - 1]; 

            if (i == n - 1) column[i].right = &head;
            else column[i].right = &column[i + 1];

            column[i].up = &column[i]; // 상하 원형 연결 (처음엔 자기 자신)
            column[i].down = &column[i];
        }

        // 후보 행row 노드 생성
        vector<Node*> nodes;
        for (int i = 0; i < matrix.size(); ++i) {
            Node* last = nullptr;

            for (int j = 0; j < n; ++j) if (matrix[i][j]) {
                Node* now = new Node;
                now->row = i;
                now->column = &column[j];
                now->up = column[j].up;
                now->down = &column[j];

                // 같은 후보row 내에서 좌우 노드 연결 + 이전 노드와 원형 연결
                if (last) {
                    now->left = last;
                    now->right = last->right;
                    last->right->left = now;
                    last->right = now;
                }
                else {
                    now->left = now;
                    now->right = now;
                }

                column[j].up->down = now;
                column[j].up = now;
                column[j].size++;
                last = now;

                nodes.push_back(now); // 나중에 메모리 해제용
            }
        }

        vector<int> result;
        search(&head, result);
        for (Node* ptr : nodes) delete ptr; // 메모리 해제

        return result; // 선택된 후보 행 번호 리스트 -> 나중에 dat와 매핑하여 실제 스도쿠 board 채움
    }
}

int main() {
    freopen_s(new FILE*, "input.txt", "r", stdin);
    ios::sync_with_stdio(0); cin.tie(0);

    int board[9][9]; // 스도쿠 판

    vector<vector<int>> mat; // 숫자를 넣을 수 있는 가능한 선택지들 전부
    vector<tuple<int, int, int>> dat; // 실제로 어디에 뭐가 들어가는지 표시 / (781) = (7,8)칸에 1이 들어간다는 뜻

    /* A = mat = Cover Matrix 
    - (row, col) = 729 * 324 = (9*9*9)*(9*9*4)
    - row는 각 제약 조건으로 dat의 값이고
    - col은 81+81+81+81 = 324 컬럼
        1. 각 칸마다 숫자를 채워야 함   -> 9행   × 9열   = 81 컬럼
        2. 행마다 숫자는 한 번만 등장   -> 9행   × 9숫자 = 81 컬럼
        3. 열마다 숫자는 한 번만 등장   -> 9열   × 9숫자 = 81 컬럼
        4. 블록마다 숫자는 한 번만 등장 -> 9블록 × 9숫자 = 81 컬럼
    */

    for (int i = 0; i < 9; ++i) for (int j = 0; j < 9; ++j) {
        cin >> board[i][j];

        auto make_row = [&](int k) {
            vector<int> row(324);

            int box = (i / 3) * 3 + (j / 3);
            row[81 * 0 + 9 * i + j] = 1; // 셀규칙
            row[81 * 1 + 9 * i + k] = 1; // 행규칙
            row[81 * 2 + 9 * j + k] = 1; // 열규칙
            row[81 * 3 + 9 * box + k] = 1; // 블록규칙

            mat.push_back(row);
            dat.push_back({ i, j, k });
        };

        if (board[i][j]) make_row(board[i][j] - 1); // 숫자가 있으면 그 숫자만 후보
        else for (int k = 0; k < 9; k++) make_row(k); // 비어 있으면 0~8에 대해 모든 후보 숫자 생성 -> 나중에 DLX가 정답 결정할 것
    }

    // DLX 알고리즘이 후보 숫자 행렬 mat을 풀어서, 선택한 후보 행 번호 리스트를 반환
    for (auto i : DLX::solve(mat)) { // i가 mat에서 선택된 row 번호 = 어느 칸에 어떤 숫자를 넣을 것인지
        int x, y, k; tie(x, y, k) = dat[i]; // dat[i] = {7, 8, 0}이면 (7, 8)칸에 후보 숫자 1 (0~8로 저장해서 +1 필요)
        board[x][y] = k; // 실제로 그 값 대입
    }

    // 출력
    for (int i = 0; i < 9; i++) {
        for (int j = 0; j < 9; j++) cout << board[i][j] + 1 << " "; // 0~8로 다뤄서 1을 더해서 출력
        cout << "\n";
    }

    return 0;
}

[Jinsun-Lee]

16*16에 알파벳 출력(지옥 개념 검증용으로 좋아)

전체 코드는 링크에 있어

int main() {
    int board[16][16]; // 스도쿠의 전체 사이즈로 수정

    vector<vector<int>> mat; 
    vector<tuple<int, int, int>> dat;

    for (int i = 0; i < 16; ++i) for (int j = 0; j < 16; ++j) { // 스도쿠의 전체 사이즈로 수정
        char c; cin >> c; // 입력 포맷을 수정 
        if (c == '-') board[i][j] = 0; // 비어있는 칸을 처리하게 수정
        else board[i][j] = c - 'A' + 1; // 1~16범위로 설정하게 수정

        auto make_row = [&](int k) {
            vector<int> row(16*16*4); // 조건=컬럼의 수로 수정

            int box = (i / 4) * 4 + (j / 4); // 사이즈에 맞게 수정
            row[256 * 0 + 16 * i + j] = 1; // 사이즈에 맞게 수정
            row[256 * 1 + 16 * i + k] = 1; // 사이즈에 맞게 수정
            row[256 * 2 + 16 * j + k] = 1; // 사이즈에 맞게 수정
            row[256 * 3 + 16 * box + k] = 1; // 사이즈에 맞게 수정

            mat.push_back(row);
            dat.push_back({ i, j, k });
        };

        if (board[i][j]) make_row(board[i][j]-1); 
        else for (int k = 0; k < 16; k++) make_row(k);
    }

    for (auto i : DLX::solve(mat)) { // DLX 부분은 수정한 것 하나도 없어
        int x, y, k; tie(x, y, k) = dat[i]; 
        board[x][y] = k+1; // 1~16범위로 설정하게 수정
    }

    for (int i = 0; i < 16; i++) {
        for (int j = 0; j < 16; j++) cout << (char)(board[i][j] -1 +'A'); // 알파벳으로 출력하게 수정
        cout << "\n";
    }

    return 0;
}

[Jinsun-Lee]

걍 똑같

int main() {
	ios::sync_with_stdio(0); cin.tie(0);

	string str; 
	while (1) {
		cin >> str;
		if (str == "end") break;

		int board[9][9]; // 스도쿠의 전체 사이즈로 수정

		vector<vector<int>> mat;
		vector<tuple<int, int, int>> dat;

		int s = -1;
		for (int i = 0; i < 9; ++i) for (int j = 0; j < 9; ++j) { // 스도쿠의 전체 사이즈로 수정
			char c; c= str[++s]; // 입력 포맷을 수정 
			if (c == '.') board[i][j] = 0; // 비어있는 칸을 처리하게 수정
			else board[i][j] = c - '0'; // 1~9범위로 설정하게 수정

			auto make_row = [&](int k) {
				vector<int> row(9 * 9 * 4); // 조건=컬럼의 수로 수정

				int box = (i / 3) * 3 + (j / 3); // 사이즈에 맞게 수정
				row[81 * 0 + 9 * i + j] = 1; // 사이즈에 맞게 수정
				row[81 * 1 + 9 * i + k] = 1; // 사이즈에 맞게 수정
				row[81 * 2 + 9 * j + k] = 1; // 사이즈에 맞게 수정
				row[81 * 3 + 9 * box + k] = 1; // 사이즈에 맞게 수정

				mat.push_back(row);
				dat.push_back({ i, j, k });
			};

			if (board[i][j]) make_row(board[i][j] - 1);
			else for (int k = 0; k < 9; k++) make_row(k);
		}

		for (auto i : DLX::solve(mat)) { // DLX 부분은 수정한 것 하나도 없어
			int x, y, k; tie(x, y, k) = dat[i];
			board[x][y] = k + 1; // 1~9범위로 설정하게 수정
		}

		for (int i = 0; i < 9; i++) {
			for (int j = 0; j < 9; j++) cout << board[i][j]; // 출력하게 수정
		}

		cout << "\n";
	}
	return 0;
}