C++

Validate a given Sudoku


Rules of Sudoku Grid

  • Each row, each column, and each of the nine 3x3 sub-grids should contain all the digits from 1 to 9 without repetition.

Thus we have the below 3 algorithmic checks

  1. Check Rows: Make sure that each row contains all digits from 1 to 9 without repetition.
  2. Check Columns: Make sure that each column contains all digits from 1 to 9 without repetition.
  3. Check Sub-grids: Make sure that each 3x3 sub-grid contains all the digits from 1 to 9 without repetition.


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 number inside the 9 smaller grids of dimension (3 X 3).
        // This additional check would be used after the row and columns check pass
        // These smaller grids start from
        // 1'st row : [0,0], [0,3], [0,6]
        // 2'nd row : [3,0], [3,3], [3,6]
        // 3'rd row : [6,0], [6,3], [6,6]
        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, column would remain the same only row would increment.
                    for (int dr=0; dr<=8; dr++) {
                        if (dr == r) // skip the current row, as we don't want to compare the number with itself
                            continue;
                        else {
                            if (board[dr][c] == board[r][c])
                                return false;
                        }
                    }

                    // Check in all the columns for a matching number, row will remain the same only column would increment.
                    for (int dc=0; dc<=8; dc++) {
                        if (dc == c) // skip the current column, as we don't want to compare the number with itself
                            continue;
                        else {
                            if (board[r][dc] == board[r][c])
                                return false;
                        }
                    }

                    // Check in the square of dimension (3 X 3) for any matching number.
                    // Ex: To check if a number at position [4,4] is valild, check all the numbers in the grid starting from [3,3] till [6,6] for any match
                    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-2024, Algotree.org.
All rights reserved.