Check Sudoku board configuration is valid or not(Using Bitmasking)

Using arrays in the prior method allowed us to monitor which numbers have emerged in every row, column, and sub-matrix. Now, by employing bit manipulation, we can make this more efficient; we represent the existence of numbers with bits in an integer, therefore lowering memory use and enhancing time complexity as well. Apart from verifying and marking visited values in row, column, and sub-matrix, the implementation processes remain the same as above technique.

Methodical, step-by-step approach:

• For each row, column, and sub-matrix use a single integer. Every bit of the integer relates to a number.
• Bitwise AND (&) lets us find whether the bit of any integer is already set for every cell. Should this be the case, the Sudoku is invalid as the number has appeared previously.
• Should the present cell value (i,e, mat[i][j]) not be set in the row, column, or sub-matrix, we must mark visited by bitwise OR operation (|=).

C++

#include <bits/stdc++.h>
using namespace std;

bool isValid(vector<vector<int>> &mat) {

    // Arrays to track seen numbers in rows,
    // columns, and sub-matrix
    vector<int> rows(9);
    vector<int> cols(9);
    vector<int> subMat(9);

    for (int i = 0; i < 9; i++) {
        for (int j = 0; j < 9; j++) {

            // Skip empty cells
            if (mat[i][j] == 0)
                continue;

            int val = mat[i][j];

            // Bit position for the current value
            int pos = 1 << (val - 1); 

            // Check for duplicates in the current row
            if ((rows[i] & pos) > 0)
                return false;

            // Mark the value as seen in the row
            rows[i] |= pos; 

            // Check for duplicates in the current column
            if ((cols[j] & pos) > 0)
                return false; 

            // Mark the value as seen in the column
            cols[j] |= pos; 

            // Calculate the index for the 3x3 sub-matrix
            int idx = (i / 3) * 3 + j / 3;

            // Check for duplicates in the current sub-matrix
            if ((subMat[idx] & pos) > 0)
                return false;

            // Mark the value as seen in the sub-matrix
            subMat[idx] |= pos; 
        }
    }
    return true; 
}

int main(){
    vector<vector<int>> mat = {
        {5, 3, 0, 0, 7, 0, 0, 0, 0},
        {6, 0, 0, 1, 9, 5, 0, 0, 0},
        {0, 9, 8, 0, 0, 0, 0, 6, 0},
        {8, 0, 0, 0, 6, 0, 0, 0, 3},
        {4, 0, 0, 8, 0, 3, 0, 0, 1},
        {7, 0, 0, 0, 2, 0, 0, 0, 6},
        {0, 6, 0, 0, 0, 0, 2, 8, 0},
        {0, 0, 0, 4, 1, 9, 0, 0, 5},
        {0, 0, 0, 0, 8, 0, 0, 7, 9}};

    cout << (isValid(mat) ? "true" : "false") << "\n";

    return 0;
}

C

#include <stdio.h>
#include <stdbool.h>

bool isValid(int mat[][9]) {
  
    // Arrays to track seen numbers in rows,
    // columns, and sub-matrix
    int rows[9] = {0}, cols[9] = {0}, subMat[9] = {0};

    for (int i = 0; i < 9; i++) {
        for (int j = 0; j < 9; j++) {
          
            // Skip empty cells
            if (mat[i][j] == 0)
                continue;

            int val = mat[i][j];
            int pos = 1 << (val - 1);

            // Check for duplicates in the current row
            if ((rows[i] & pos) > 0)
                return false;
            rows[i] |= pos;

            // Check for duplicates in the current column
            if ((cols[j] & pos) > 0)
                return false;
            cols[j] |= pos;

            // Calculate the index for the 3x3 sub-matrix
            int idx = (i / 3) * 3 + j / 3;

            // Check for duplicates in the current sub-matrix
            if ((subMat[idx] & pos) > 0)
                return false;
            subMat[idx] |= pos;
        }
    }
    return true;
}

int main() {
    int mat[][9] = {
        {5, 3, 0, 0, 7, 0, 0, 0, 0},
        {6, 0, 0, 1, 9, 5, 0, 0, 0},
        {0, 9, 8, 0, 0, 0, 0, 6, 0},
        {8, 0, 0, 0, 6, 0, 0, 0, 3},
        {4, 0, 0, 8, 0, 3, 0, 0, 1},
        {7, 0, 0, 0, 2, 0, 0, 0, 6},
        {0, 6, 0, 0, 0, 0, 2, 8, 0},
        {0, 0, 0, 4, 1, 9, 0, 0, 5},
        {0, 0, 0, 0, 8, 0, 0, 7, 9}
    };

    printf("%s\n", isValid(mat) ? "true" : "false");
    return 0;
}

Java

import java.util.Arrays;

class GfG {
    static boolean isValid(int[][] mat){

        // Arrays to track seen numbers in rows,
        // columns, and sub-matrix
        int[] rows = new int[9];
        int[] cols = new int[9];
        int[] subMat = new int[9];

        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {

                // Skip empty cells
                if (mat[i][j] == 0)
                    continue;

                int val = mat[i][j];
                int pos = 1 << (val - 1);

                // Check for duplicates in the current row
                if ((rows[i] & pos) > 0)
                    return false;
                rows[i] |= pos;

                // Check for duplicates
                // in the current column
                if ((cols[j] & pos) > 0)
                    return false;
                cols[j] |= pos;

                // Calculate the index for the 3x3
                // sub-matrix
                int idx = (i / 3) * 3 + j / 3;

                // Check for duplicates in the current
                // sub-matrix
                if ((subMat[idx] & pos) > 0)
                    return false;
                subMat[idx] |= pos;
            }
        }
        return true;
    }

    public static void main(String[] args)
    {
        int[][] mat = { { 5, 3, 0, 0, 7, 0, 0, 0, 0 },
                        { 6, 0, 0, 1, 9, 5, 0, 0, 0 },
                        { 0, 9, 8, 0, 0, 0, 0, 6, 0 },
                        { 8, 0, 0, 0, 6, 0, 0, 0, 3 },
                        { 4, 0, 0, 8, 0, 3, 0, 0, 1 },
                        { 7, 0, 0, 0, 2, 0, 0, 0, 6 },
                        { 0, 6, 0, 0, 0, 0, 2, 8, 0 },
                        { 0, 0, 0, 4, 1, 9, 0, 0, 5 },
                        { 0, 0, 0, 0, 8, 0, 0, 7, 9 } };

        System.out.println(isValid(mat) ? "true" : "false");
    }
}

Python

def isValid(mat):
  
    # Arrays to track seen numbers in rows,
    # columns, and sub-matrix
    rows = [0] * 9
    cols = [0] * 9
    subMat = [0] * 9

    for i in range(9):
        for j in range(9):
            # Skip empty cells
            if mat[i][j] == 0:
                continue

            val = mat[i][j]
            pos = 1 << (val - 1)

            # Check for duplicates in the current row
            if (rows[i] & pos) > 0:
                return False
            rows[i] |= pos

            # Check for duplicates in the current column
            if (cols[j] & pos) > 0:
                return False
            cols[j] |= pos

            # Calculate the index for the 3x3 sub-matrix
            idx = (i // 3) * 3 + j // 3

            # Check for duplicates in the current sub-matrix
            if (subMat[idx] & pos) > 0:
                return False
            subMat[idx] |= pos

    return True

if __name__ == "__main__":
    mat = [
        [5, 3, 0, 0, 7, 0, 0, 0, 0],
        [6, 0, 0, 1, 9, 5, 0, 0, 0],
        [0, 9, 8, 0, 0, 0, 0, 6, 0],
        [8, 0, 0, 0, 6, 0, 0, 0, 3],
        [4, 0, 0, 8, 0, 3, 0, 0, 1],
        [7, 0, 0, 0, 2, 0, 0, 0, 6],
        [0, 6, 0, 0, 0, 0, 2, 8, 0],
        [0, 0, 0, 4, 1, 9, 0, 0, 5],
        [0, 0, 0, 0, 8, 0, 0, 7, 9]
    ]

    print("true" if isValid(mat) else "false")

C#

using System;

class GfG {
    static bool IsValid(int[, ] mat)
    {

        // Arrays to track seen numbers in rows,
        // columns, and sub-matrix
        int[] rows = new int[9];
        int[] cols = new int[9];
        int[] subMat = new int[9];

        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                // Skip empty cells
                if (mat[i, j] == 0)
                    continue;

                int val = mat[i, j];

                // Bit position for the current value
                int pos = 1 << (val - 1);

                // Check for duplicates in the current row
                if ((rows[i] & pos) > 0)
                    return false;

                // Mark the value as seen in the row
                rows[i] |= pos;

                // Check for duplicates in the current
                // column
                if ((cols[j] & pos) > 0)
                    return false;

                // Mark the value as seen in the column
                cols[j] |= pos;

                // Calculate the index for the 3x3
                // sub-matrix
                int idx = (i / 3) * 3 + j / 3;

                // Check for duplicates in the current
                // sub-matrix
                if ((subMat[idx] & pos) > 0)
                    return false;

                // Mark the value as seen in the sub-matrix
                subMat[idx] |= pos;
            }
        }
        return true;
    }

    static void Main(){
        int[, ] mat = { { 5, 3, 0, 0, 7, 0, 0, 0, 0 },
                        { 6, 0, 0, 1, 9, 5, 0, 0, 0 },
                        { 0, 9, 8, 0, 0, 0, 0, 6, 0 },
                        { 8, 0, 0, 0, 6, 0, 0, 0, 3 },
                        { 4, 0, 0, 8, 0, 3, 0, 0, 1 },
                        { 7, 0, 0, 0, 2, 0, 0, 0, 6 },
                        { 0, 6, 0, 0, 0, 0, 2, 8, 0 },
                        { 0, 0, 0, 4, 1, 9, 0, 0, 5 },
                        { 0, 0, 0, 0, 8, 0, 0, 7, 9 } };

        Console.WriteLine(IsValid(mat) ? "true" : "false");
    }
}

Time complexity O(n^2), where n = Sudoku matrix size—that is, 9. This is so as we go across all n*n matrix cells iteratively.
O(n) auxiliary space since we track the seen numbers for rows, columns, and sub-matrix using three arrays (rows, cols, subMat), each of size n. Bitwise operations use the integer each array element carries.