Sudoku Solver 数独自动计算工具

Sudoku Solver

Sudoku Solver 是由C++编写的数独计算工具，使用了基于MRV策略的Forward Checking算法，是典型的CSP问题的实例。
读者可以复制代码编译使用。

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;

const int SIZE = 9;

struct Do {
    int val; // value
    int row, col; // position
    bool curdom[SIZE]; // 1~SIZE's availablity
    bool assigned;
};

struct sudoku {
    Do board[SIZE][SIZE];
    bool RowCheck(sudoku* board, Do* m);
    bool ColCheck(sudoku* board, Do* m);
    bool BoxCheck(sudoku* board, Do* m);
    int CDcount(Do* m);
    bool Goal(sudoku* board);
    bool FCCheck(sudoku* board, int c, Do* m);
    void Copyboard(sudoku* dest, const sudoku* src);
    Do* heuristicpick(sudoku* board);
    void propagete(sudoku* board, Do* m);
};

bool FC(sudoku* board, int level);
void propagate(sudoku* board, Do* m);
void display(sudoku* board);


int main() {
    sudoku SUDK;
    sudoku* ptr = &SUDK;
    for (int i = 0;i<SIZE;i++) {
        for (int j = 0;j<SIZE;j++) {
            SUDK.board[i][j].val = 0;
            SUDK.board[i][j].row = i;
            SUDK.board[i][j].col = j;
            SUDK.board[i][j].assigned = 0;
            memset(SUDK.board[i][j].curdom, 0, sizeof(SUDK.board[i][j].curdom));
        }
    }
    cout << "Input Presets: " << endl;
    cout << "In the form as (row, col, value):" << endl;
    cout << "E.g.: 1 2 5" << endl;
    cout << "End with (0, 0, 0)" << endl;
    while(1) {
        int a, b, v;
        cin >> a >> b >> v;
        if (a+b+v == 0) break;
        SUDK.board[a-1][b-1].val = v;
        SUDK.board[a-1][b-1].assigned = 1;
        propagate(ptr, &SUDK.board[a-1][b-1]);
    }
    display(ptr);
    FC(ptr, 0);
    return 0;
}

/* ###################################################################### */

bool RowCheck(sudoku* board, Do* m) {
    // return false: constraint falsified;
    //         true: NO falsification.
    int Row[SIZE];
    for(int i = 0;i<SIZE;i++) {
        Row[i] = board->board[m->row][i].val;
    }
    // Check Constraints
    sort(Row, Row + SIZE);
    for(int i = 0;i<SIZE-1;i++) {
        if (!Row[i]) continue;
        if (Row[i] == Row[i+1]) return false;
    }
    return true;
}

bool ColCheck(sudoku* board, Do* m) {
    // return false: constraint falsified;
    //         true: NO falsification.
    int Col[SIZE];
    for(int i = 0;i<SIZE;i++) {
        Col[i] = board->board[i][m->col].val;
    }
    // Check Constraints
    sort(Col, Col + SIZE);
    for(int i = 0;i<SIZE-1;i++) {
        if (!Col[i]) continue;
        if (Col[i] == Col[i+1]) return false;
    }
    return true;
}

bool BoxCheck(sudoku* board, Do* m) {
    int v = m->val;
    int r1, r2, c1, c2;
    if (m->row % 3 == 1) {
        r1 = 1; r2 = 1;
    }
    else if (m->row % 3 == 0) {
        r1 = 1; r2 = -2;
    }
    else {
        r1 = -1; r2 = 2;
    }
    if (m->col % 3 == 1) {
        c1 = 1; c2 = 1;
    }
    else if (m->col % 3 == 0) {
        c1 = 1; c2 = -2;
    }
    else {
        c1 = -1; c2 = 2;
    }
    // Check Constraints
    if (board->board[m->row][m->col+c1].assigned && v == board->board[m->row][m->col+c1].val) return false;
    if (board->board[m->row][m->col-c2].assigned && v == board->board[m->row][m->col-c2].val) return false;
    if (board->board[m->row+r1][m->col].assigned && v == board->board[m->row+r1][m->col].val) return false;
    if (board->board[m->row+r1][m->col+c1].assigned && v == board->board[m->row+r1][m->col+c1].val) return false;
    if (board->board[m->row+r1][m->col-c2].assigned && v == board->board[m->row+r1][m->col-c2].val) return false;
    if (board->board[m->row-r2][m->col].assigned && v == board->board[m->row-r2][m->col].val) return false;
    if (board->board[m->row-r2][m->col+c1].assigned && v == board->board[m->row-r2][m->col+c1].val) return false;
    if (board->board[m->row-r2][m->col-c2].assigned && v == board->board[m->row-r2][m->col-c2].val) return false;
}

int CDcount(Do* m) {
    int res = 0;
    for (int i = 0;i<SIZE;i++) {
        res += m->curdom[i];
    }
    return res;
}

bool CheckCons(sudoku* board, int c, Do* m) {
    int R = m->row, C = m->col, tot = 0;
    // c == 0 >>> row
    if (c == 0) {
        for (int i = 0;i<SIZE;i++) {
            tot += board->board[R][i].assigned;
        }
        return (tot == SIZE-1);
    }
    // c == 1 >>> col
    else if (c == 1) {
        for (int i = 0;i<SIZE;i++) {
            tot += board->board[i][C].assigned;
        }
        return (tot == SIZE-1);
    }
    // c == 2 >>> Box
    else if (c == 2) {
        int r1, r2, c1, c2;
        if (m->row % 3 == 1) {
            r1 = 1; r2 = 1;
        }
        else if (m->row % 3 == 0) {
            r1 = 1; r2 = -2;
        }
        else {
            r1 = -1; r2 = 2;
        }
        if (m->col % 3 == 1) {
            c1 = 1; c2 = 1;
        }
        else if (m->col % 3 == 0) {
            c1 = 1; c2 = -2;
        }
        else {
            c1 = -1; c2 = 2;
        }
        if (board->board[m->row][m->col+c1].assigned) tot += 1;
        if (board->board[m->row][m->col-c2].assigned) tot += 1;
        if (board->board[m->row+r1][m->col].assigned) tot += 1;
        if (board->board[m->row+r1][m->col+c1].assigned) tot += 1;
        if (board->board[m->row+r1][m->col-c2].assigned) tot += 1;
        if (board->board[m->row-r2][m->col].assigned) tot += 1;
        if (board->board[m->row-r2][m->col+c1].assigned) tot += 1;
        if (board->board[m->row-r2][m->col-c2].assigned) tot += 1;
        return (tot == SIZE-2);
    }
    return false;
}

bool FCCheck(sudoku* board, int c, Do* m) {
    // c == 0 >>> row
    if (c == 0) for (int i = 0;i<SIZE;i++) {
        if (!m->curdom[i]) {
            m->curdom[i] = 1;
            if(RowCheck(board, m)) m->curdom[i] = 0; // No falsification
        }
    }
    // c == 1 >>> col
    else if (c == 1) for (int i = 0;i<SIZE;i++) {
        if (!m->curdom[i]) {
            m->curdom[i] = 1;
            if(ColCheck(board, m)) m->curdom[i] = 0; // No falsification
        }
    }
    // c == 2 >>> Box
    else if (c == 2) for (int i = 0;i<SIZE;i++) {
        if (!m->curdom[i]) {
            m->curdom[i] = 1;
            if(BoxCheck(board, m)) m->curdom[i] = 0; // No falsification
        }
    }
    if (CDcount(m) == SIZE) return false;
    else return true;
}

bool Goal(sudoku* board) {
    for (int i = 0;i<SIZE;i++) {
        for (int j = 0;j<SIZE;j++) {
            if (!board->board[i][j].assigned) return false;
        }
    }
    return true;
}

Do* heuristicpick(sudoku* board) {
    // MRV
    Do* maxi = &board->board[0][0];
    for (int i = 0;i<SIZE;i++) {
        for (int j = 0;j<SIZE;j++) {
            if(board->board[i][j].assigned) continue;
            if(CDcount(maxi) < CDcount(&board->board[i][j]) || maxi->assigned) {
                maxi = &board->board[i][j];
                if (CDcount(maxi) == SIZE-1) return maxi;
            }
        }
    }
    return maxi;
}

void propagate(sudoku* board, Do* m) {
    // Propagate to cols and rows
    for (int i = 0;i<SIZE;i++) {
        board->board[m->row][i].curdom[m->val-1] = 1;
        board->board[i][m->col].curdom[m->val-1] = 1;
    }
    // Propagate to Box
    int r1, r2, c1, c2;
    if (m->row % 3 == 1) {
        r1 = 1; r2 = 1;
    }
    else if (m->row % 3 == 0) {
        r1 = 1; r2 = -2;
    }
    else {
        r1 = -1; r2 = 2;
    }
    if (m->col % 3 == 1) {
        c1 = 1; c2 = 1;
    }
    else if (m->col % 3 == 0) {
        c1 = 1; c2 = -2;
    }
    else {
        c1 = -1; c2 = 2;
    }
    board->board[m->row][m->col+c1].curdom[m->val-1] = 1;
    board->board[m->row][m->col-c2].curdom[m->val-1] = 1;
    board->board[m->row+r1][m->col].curdom[m->val-1] = 1;
    board->board[m->row+r1][m->col+c1].curdom[m->val-1] = 1;
    board->board[m->row+r1][m->col-c2].curdom[m->val-1] = 1;
    board->board[m->row-r2][m->col].curdom[m->val-1] = 1;
    board->board[m->row-r2][m->col+c1].curdom[m->val-1] = 1;
    board->board[m->row-r2][m->col-c2].curdom[m->val-1] = 1;
}

void Copyboard(sudoku* dest, const sudoku* src) {
	memcpy(dest, src, sizeof(sudoku));
}

bool FC(sudoku* board, int level) {
    if (Goal(board)) {
        // Return when all cells are assigned.
        cout << "Goal!" << endl;
        display(board);
        return true;
    }
    Do* v = heuristicpick(board); // Pick with MRV
    v->assigned = true;
    bool dwo = false;
    int pos = 0;
    for (int i = 0;i<SIZE;i++) if (!v->curdom[i]) {
        sudoku boardcopy;
        Copyboard(&boardcopy, board);
        v->val = i+1;
        propagate(board, v);
        dwo = false;
        // row constraint
        if (!dwo && CheckCons(board, 0, v)) {
            for (int i = 0;i<SIZE;i++) if (!board->board[v->row][i].assigned) {
                dwo = !FCCheck(board, 0, &board->board[v->row][i]);
            }
        }
        // col constraint
        if (!dwo && CheckCons(board, 1, v)) {
            for (int i = 0;i<SIZE;i++) if (!board->board[i][v->col].assigned) {
                dwo = !FCCheck(board, 1, &board->board[i][v->col]);
            }
        }
        // Box constraint
        if (!dwo && CheckCons(board, 2, v)) {
            int r1, r2, c1, c2;
            if (v->row % 3 == 1) {
                r1 = 1; r2 = 1;
            }
            else if (v->row % 3 == 0) {
                r1 = 1; r2 = -2;
            }
            else {
                r1 = -1; r2 = 2;
            }
            if (v->col % 3 == 1) {
                c1 = 1; c2 = 1;
            }
            else if (v->col % 3 == 0) {
                c1 = 1; c2 = -2;
            }
            else {
                c1 = -1; c2 = 2;
            }
            int tmp_r, tmp_c;
            if (!board->board[v->row][v->col+c1].assigned) {tmp_r = v->row; tmp_c = v->col+c1;}
            else if (!board->board[v->row][v->col-c2].assigned) {tmp_r = v->row; tmp_c = v->col-c2;}
            else if (!board->board[v->row+r1][v->col].assigned) {tmp_r = v->row+r1; tmp_c = v->col;}
            else if (!board->board[v->row+r1][v->col+c1].assigned) {tmp_r = v->row+r1; tmp_c = v->col+c1;}
            else if (!board->board[v->row+r1][v->col-c2].assigned) {tmp_r = v->row+r1; tmp_c = v->col-c2;}
            else if (!board->board[v->row-r2][v->col].assigned) {tmp_r = v->row-r2; tmp_c = v->col;}
            else if (!board->board[v->row-r2][v->col+c1].assigned) {tmp_r = v->row-r2; tmp_c = v->col+c1;}
            else if (!board->board[v->row-r2][v->col-c2].assigned) {tmp_r = v->row-r2; tmp_c = v->col-c2;}
            dwo = !FCCheck(board, 2, &board->board[tmp_r][tmp_c]);
        }
        if(!dwo && FC(board, level + 1)) return true;
        Copyboard(board, &boardcopy);
    }
    v->assigned = false;
    return false;
}

void display(sudoku* board) {
	cout << "\t----------------------------------------" << endl;
    for (int i = 0;i<SIZE;i++) {
        cout << "\t|";
        for (int j = 0;j<SIZE;j++) {
            cout << " " << board->board[i][j].val << "  ";
            if (j%3 == 2) cout << "|";
        }
        cout << endl;
        if (i%3 == 2) cout << "\t----------------------------------------" << endl;
    }
}

---

2019/10 Karl