C++

Validate a given Sudoku



Program to validate a given Sudoku

#include<iostream>
#include<vector>
#include<map>

using namespace std;

class Sudoku {

    public:
    bool IsValid (vector<vector<char>>& board) {

        // Create a map for validating the elements inside the square
        map<int,int> row_start, col_start;

        for(int i=0; i<=2; i++) {
            row_start[i] = 0;
            col_start[i] = 0;
        }

        for(int i=3; i<=5; i++) {
            row_start[i] = 3;
            col_start[i] = 3;
        }

        for(int i=6; i<=8; i++) {
            row_start[i] = 6;
            col_start[i] = 6;
        }

        // Look at each element of the sudoku
        for (int r=0; r<=8; r++) {
            for (int c=0; c<=8; c++) {

                if (board[r][c] == '.') {
                    continue;
                } else {

                    // Check in all the rows for a matching number
                    for (int dr=0; dr<=8; dr++) {
                        if (dr == r) // skip the current row
                            continue;
                        else {
                            if (board[dr][c] == board[r][c])
                                return false;
                        }
                    }

                    // Check in all the columns for a matching number
                    for (int dc=0; dc<=8; dc++) {
                        if (dc == c) // skip the current row
                            continue;
                        else {
                            if (board[r][dc] == board[r][c])
                                return false;
                        }
                    }

                    // Check in the square for any matching number
                    for (int dr=row_start[r]; dr<=row_start[r]+2; dr++) {
                        for (int dc=col_start[c]; dc<=col_start[c]+2; dc++) {
                            if (dr == r and dc == c) // Skip the same element
                                continue;
                            else if (board[dr][dc] == board[r][c])
                                return false;
                        }
                    }
                }
            }
        }
        return true;
    }
};

int main() {

    Sudoku S;
    vector<vector<char>> grid_1 = {{ '5', '3', '.', '.', '7', '.', '.', '.', '.'},
                                   { '6', '.', '.', '1', '9', '5', '.', '.', '.'},
                                   { '.', '9', '8', '.', '.', '.', '.', '6', '.'},
                                   { '8', '.', '.', '.', '6', '.', '.', '.', '3'},
                                   { '4', '.', '.', '8', '.', '3', '.', '.', '1'},
                                   { '7', '.', '.', '.', '2', '.', '.', '.', '6'},
                                   { '.', '6', '.', '.', '.', '.', '2', '8', '.'},
                                   { '.', '.', '.', '4', '1', '9', '.', '.', '5'},
                                   { '.', '.', '.', '.', '8', '.', '.', '7', '9'}};

    if (S.IsValid(grid_1)) {
        cout << "Sudoku grid_1 is valid" << endl;
    } else {
        cout << "Sudoku grid_1 is invalid" << endl;
    }

    vector<vector<char>> grid_2 = {{ '8', '3', '.', '.', '7', '.', '.', '.', '.'},
                                   { '6', '.', '.', '1', '9', '5', '.', '.', '.'},
                                   { '.', '9', '8', '.', '.', '.', '.', '6', '.'},
                                   { '8', '.', '.', '.', '6', '.', '.', '.', '3'},
                                   { '4', '.', '.', '8', '.', '3', '.', '.', '1'},
                                   { '7', '.', '.', '.', '2', '.', '.', '.', '6'},
                                   { '.', '6', '.', '.', '.', '.', '2', '8', '.'},
                                   { '.', '.', '.', '4', '1', '9', '.', '.', '5'},
                                   { '.', '.', '.', '.', '8', '.', '.', '7', '9'}};
    if (S.IsValid(grid_2)) {
        cout << "Sudoku grid_2 is valid" << endl;
    } else {
        cout << "Sudoku grid_2 is invalid" << endl;
    }

    return 0;
}

Output

Sudoku grid_1 is valid
Sudoku grid_2 is invalid



Copyright (c) 2019-2022, Algotree.org.
All rights reserved.