Home > Enterprise >  sudoku solver repeting number 1 in invalid places
sudoku solver repeting number 1 in invalid places

Time:12-26

Hi I'm doing a project in college and it consist in solving a sudoku in a certain way. First we look for the possible numbers in one position and then we compare with the possible numbers in the positions in the same ror, colum and 3x3. If there is one compulsory value we put it in the sudoku, if not we jump to the next position. My code works mainly well, but sometimes I don't know why it assigns the number 1 in a position where it's invalid because number 1 it's already in the 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);
            }   
        }
    }
}

I just copied the full code but my problem is when 'R' is the input(instruction to solve the sudoku), options A, B, and C are ok. I think the problem is in this function:

//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;
    }
}

Sorry the functions are in my language(catalan).

CodePudding user response:

There is a small but important bug in this loop:

    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);
        }
    }

You're looping through a vector p, but instead of adding an item from p to paux, you're assigning an index to the vector. The correct version is:

            paux.push_back(p[i]);
  • Related