数独求解器在无效位置重复数字 1

Question

你好我在大学里做一个项目，它包括以某种方式解决数独问题。首先我们寻找一个位置可能的数字，然后我们比较相同 ror，colum 和 3x3 中位置的可能数字。如果有一个强制值，我们将其放入数独中，如果没有，我们跳转到下一个位置。我的代码主要运行良好，但有时我不知道为什么它会在无效的位置分配数字 1，因为数字 1 已经在 row/column/3x3.

#include <iostream>
#include <vector>

using namespace std;

typedef vector<vector<int>> Matrix;

int charaint(char colum){
    return colum-'A'+1;
}

char intachar(int colum){
    return char(colum-1+'A');
}
//looking in the row for possible values in a position.
bool en_fila(const Matrix sudoku, int fil, int i){
    bool trobat = false;
    for (int col = 0; col < 9 and not trobat; col++){
        if ((int)sudoku[fil][col] == i)
            trobat = true;  
    }
    return trobat;
}

//looking in the column for possible values in a position.
bool en_columna(const Matrix sudoku, int col, int i){
    bool trobat = false;
    for (int fil = 0; fil < 9 and not trobat; fil++){
        if ((int)sudoku[fil][col] == i)
            trobat = true;
    }
    return trobat;
}

//looking in the 3x3 for possible values in a position.
bool en_quadrat(const Matrix sudoku, int inifil, int inicol, int i){
    bool trobat = false;
    for (int fil = 0; fil < 3 and not trobat; fil++){
        for (int col = 0; col < 3 and not trobat; col++){
            if (sudoku[fil+inifil][col+inicol] == i)
                trobat = true;
        }
    }
    return trobat;
}

//looking if a value is possible in a position
bool es_possible(const Matrix sudoku, int fil, int col, int i)
{
    return !en_fila(sudoku, fil, i) and !en_columna(sudoku, col, i) and !en_quadrat(sudoku, fil-fil%3, col-col%3, i);
}

//creating a vector with the possible values in a position
vector<int> possibles_en_casella(const Matrix sudoku, int fil, int col){
    vector<int> p;
    for (int i = 1; i <= 9; i++){
        if (es_possible(sudoku, fil, col, i))
                p.push_back(i);
    }
    return p;
}

//comparing vectors of the diferent positions of a row with a the vector of possibilities in a single position
bool possible_en_fila(const Matrix sudoku, int fil, int col, vector<int> p, int i){
    bool trobat = false;
    vector<int> paux;
    for (int c = 0; c < 9 and not trobat; c++){
        if ((col != c) and (sudoku[fil][c] == 0)){
            paux = possibles_en_casella(sudoku, fil, c);
            for (int j = 0; j < int(paux.size()); j++){
                if (paux[j] == p[i]){
                    trobat = true;
                }
            }
        }
    }
    return trobat;
}
//comparing vectors of the diferent positions of a column with a the vector of possibilities in a single position
bool possible_en_columna(const Matrix sudoku, int fil, int col, vector<int> p, int i){
    bool trobat = false;
    vector<int> paux;
    for (int f = 0; f < 9 and not trobat; f++){
        if ((fil != f) and (sudoku[f][col] == 0)){
            paux = possibles_en_casella(sudoku, f, col);
            for (int j = 0; j < int(paux.size()); j++){
                if (paux[j] == p[i]){
                    trobat = true;
                }
            }
        }
    }
    return trobat;
}

//comparing vectors of the diferent positions of a 3x3 with a the vector of possibilities in a single position
bool possible_en_quadrat(const Matrix sudoku, int fil, int col,  vector<int> p, int i){
    bool trobat = false;
    int inicol = (col-col%3);
    int inifil = (fil-fil%3);   
    vector<int> paux;
    for (int f = 0; f < 3 and not trobat; f++){
        for (int c = 0; c < 3 and not trobat; c++){
            if ((f+inifil != fil) and (c+inicol != col) and (sudoku[f+inifil][c+inicol] == 0)){
                paux = possibles_en_casella(sudoku, f+inifil, col+inicol);
                for (int j = 0; j < int(paux.size()); j++){
                    if (paux[j] == p[i]){
                        trobat = true;
                    }
                }
            }
        }
    }
    return trobat;
}
//comparing vectors of the diferent positions with a the vector of possibilities in a single position
vector<int> vector_possibles_en_casella(const Matrix sudoku, int fil, int col){
    vector<int> p = possibles_en_casella(sudoku, fil, col);
    vector<int> paux;
    if ((int(p.size())) == 1 and (p[0] != 0)) return p;
    else{ 
        for (int i = 0; i < int(p.size()); i++){
            if (!possible_en_fila(sudoku, fil, col, p, i) and !possible_en_columna(sudoku, fil, col, p, i) and !possible_en_quadrat(sudoku, fil, col, p, i)){
                paux.push_back(i);
            }
        }
    return paux;
    }
}
//print the sudoku
void imprimir_sudoku(Matrix sudoku){
    cout << "   A B C   D E F   G H I" << endl;
    for (int fil = 0; fil < 9; fil++){
        if (fil == 3 or fil == 6){
            cout << "  -------+-------+-------" << endl;
        }
        cout << fil+1 << " ";
        for (int col = 0; col < 9; col++){
            if (col == 2 or col == 5){
                if (sudoku[fil][col] == 0) cout << " . |"; 
                else cout << " " << sudoku[fil][col] << " |"; 
            }
            else{
                if (sudoku[fil][col] == 0) cout << " .";
                else cout << " " << sudoku[fil][col];
            }       
        }
        cout << endl;
    }
    cout << endl;
}
int main(){
    int fil, val;
    char op, columna;
    Matrix sudoku(9, vector<int> (9));
    for (int f = 0; f < 9; f++){
        for (int c = 0; c < 9; c++){
            cin >> sudoku[f][c];
        }
    }
    Matrix sudokuinicial = sudoku;
    while (cin >> op and op != 'Z'){
        //prints the vector of possible values in a given position
        if (op == 'A'){
            cin >> fil >> columna;
            int col = charaint(columna);
            if (sudoku[fil-1][col-1] != 0) cout << fil << columna << ": []"; 
            else{
                vector<int> p = possibles_en_casella(sudoku, fil-1, col-1);
                cout << fil << columna << ": [" << p[0];
                if (p.size() > 1){
                    for (unsigned int j = 1; j < p.size(); j++){
                        cout << ", " << p[j];
                    }
                }
                cout << "]";
            }
            cout << endl;
        }
        //looks if the given number is vaild in the given position
        if (op == 'B'){
            cin >> fil >> columna >> val;
            int col = charaint(columna);
            if (sudokuinicial[fil-1][col-1] != 0) cout << fil << columna << ": Casella no modificable" << endl; 
            else {
                Matrix sudokuaux = sudoku;
                sudokuaux[fil-1][col-1] = 0;
                if (not hi_es(val,possibles_en_casella(sudokuaux, fil-1, col-1))){
                    cout << fil << columna << ": " << val << " es un valor no possible" << endl;
                }
                else{
                    sudoku[fil-1][col-1]=val;
                }
            }
        }
        //prints actual sudoku
        if (op == 'C'){
            imprimir_sudoku(sudoku);
        }
        if (op == 'R'){
            Matrix sudokurini;          
            while (sudokurini != sudoku){
                sudokurini = sudoku;
                for (int i = 0; i < 9; i++){
                    for (int j = 0; j < 9; j++){
                        if (sudoku[i][j] == 0){
                            vector<int> paux = vector_possibles_en_casella(sudoku, i, j);
                            if ((int(paux.size()) == 1) /*and (paux[0] != 0)*/){
                                sudoku[i][j] = paux[0];
                                char columna = intachar(j+1);
                                cout << "A la casella (" << i+1 << "," << columna << ") hi ha d'anar un " << paux[0] << endl;
                            }
                        }
                    }
                }
                imprimir_sudoku(sudoku);
            }   
        }
    }
}

我只是复制了完整的代码，但我的问题是当 'R' 是输入（解决数独的指令）时，选项 A、B 和 C 都可以。我认为问题出在这个函数中：

//comparing vectors of the diferent positions with a the vector of possibilities in a single position
vector<int> vector_possibles_en_casella(const Matrix sudoku, int fil, int col){
    vector<int> p = possibles_en_casella(sudoku, fil, col);
    vector<int> paux;
    if ((int(p.size())) == 1 and (p[0] != 0)) return p;
    else{ 
        for (int i = 0; i < int(p.size()); i++){
            if (!possible_en_fila(sudoku, fil, col, p, i) and !possible_en_columna(sudoku, fil, col, p, i) and !possible_en_quadrat(sudoku, fil, col, p, i)){
                paux.push_back(i);
            }
        }
    return paux;
    }
}

抱歉，这些功能使用的是我的语言（加泰罗尼亚语）。

Answer 1

这个循环中有一个小而重要的错误：

    for (int i = 0; i < int(p.size()); i++){
        if (!possible_en_fila(sudoku, fil, col, p, i) and !possible_en_columna(sudoku, fil, col, p, i) and !possible_en_quadrat(sudoku, fil, col, p, i)){
            paux.push_back(i);
        }
    }

您正在遍历向量 p，但不是将 p 中的项目添加到 paux，而是为向量分配索引。正确的版本是：

            paux.push_back(p[i]);

数独求解器在无效位置重复数字 1

sudoku solver repeting number 1 in invalid places

c++

arrays

vector

sudoku

c++11