The aim is to verify whether the provided Sudoku board setup is valid or not considering their configuration. Every row, column, and 3x 3 sub-matrix in a valid configuration must have the digits 1 through 9 without repeating.
Input
Output: true
Explanation: It is possible to have a proper sudoku.Proposed Approaches
- Naive Approach
- Using Hashing
- Using Array of Fixed Length
- Using Bitmasking
Naive Approach
Every integer between 1 and 9 shows just once in each row, column, 3X3 sub-matrix of the sudoku. Search every cell in the row, column, and 3X3 sub-matrix when its value is only showing once.
C++
// C++ Program to check whether given sudoku is valid
#include <iostream>
#include <vector>
using namespace std;
// Checks for duplicates in the current row
bool validRow(vector<vector<int>>& mat, int row) {
// Visited array to track occurrences
vector<int> vis(10, 0);
for (int i = 0; i < 9; i++) {
// If the cell is not empty
if (mat[row][i] != 0) {
int val = mat[row][i];
// If duplicate is found
if (vis[val] != 0)
return false;
// Mark the number as visited
vis[val]++;
}
}
return true;
}
// Checks for duplicates in the current column
bool colValid(vector<vector<int>>& mat, int col) {
// Visited array to track occurrences
vector<int> vis(10, 0);
for (int i = 0; i < 9; i++) {
// If the cell is not empty
if (mat[i][col] != 0) {
int val = mat[i][col];
// If duplicate is found
if (vis[val] != 0)
return false;
// Mark the number as visited
vis[val]++;
}
}
return true;
}
// Checks for duplicates in the current 3x3 submatrix
bool subMatValid(vector<vector<int>>& mat,
int startRow, int startCol) {
// Visited array to track occurrences
vector<int> vis(10, 0);
for (int row = 0; row < 3; row++) {
for (int col = 0; col < 3; col++) {
// Current element in the submatrix
int curr = mat[row + startRow][col + startCol];
// If the cell is not empty
if (curr != 0) {
// If duplicate is found
if (vis[curr] != 0)
return false;
// Mark the number as visited
vis[curr]++;
}
}
}
return true;
}
// Validates the Sudoku board
bool isValid(vector<vector<int>>& mat) {
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
// Check if the row, column,
// or submatrix is invalid
if (!validRow(mat, i) || !colValid(mat, j)
|| !subMatValid(mat, i - i % 3, j - j % 3))
return false;
}
}
return true;
}
int main() {
vector<vector<int>> mat = {
{9, 3, 0, 0, 7, 0, 0, 0, 0},
{6, 0, 0, 1, 9, 5, 0, 0, 0},
{0, 5, 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") << endl;
return 0;
}C
// C Program to check whether given sudoku is valid
#include <stdbool.h>
#include <stdio.h>
#include <string.h>
// Checks for duplicates in current row
bool validRow(int mat[9][9], int row){
// Integer array for marking visited
int vis[10] = {0};
for (int i = 0; i < 9; i++)
{
// If the cell is not empty
if (mat[row][i] != 0)
{
// If duplicate is found
if (vis[mat[row][i]] != 0)
return false;
// Mark occurrence in the visited array
vis[mat[row][i]]++;
}
}
return true;
}
// Checks for duplicates in current column
bool colValid(int mat[9][9], int col)
{
// Integer array for hashing
int vis[10] = {0};
// Loop through the column
for (int i = 0; i < 9; i++)
{
// If the cell is not empty
if (mat[i][col] != 0)
{
// If duplicate is found
if (vis[mat[i][col]] != 0)
return false;
// Mark occurrence in the hash array
vis[mat[i][col]]++;
}
}
return true;
}
// Checks for duplicates in the current 3x3 submatrix
bool subMatValid(int mat[9][9], int startRow,
int startCol){
// Integer array for hashing
int vis[10] = {0};
for (int row = 0; row < 3; row++){
for (int col = 0; col < 3; col++){
// Current element in the submatrix
int curr = mat[row + startRow][col + startCol];
// If the cell is not empty
if (curr != 0){
// If duplicate is found
if (vis[curr] != 0)
return false;
// Mark occurrence in the hash array
vis[curr]++;
}
}
}
return true;
}
// Validates the Sudoku board
bool isValid(int mat[9][9]){
for (int i = 0; i < 9; i++){
for (int j = 0; j < 9; j++){
// Check if row, column, or submatrix is invalid
if (!validRow(mat, i) || !colValid(mat, j)
|| !subMatValid(mat, i - i % 3, j - j % 3))
return false;
}
}
return true;
}
int main(){
int mat[9][9] = {{9, 3, 0, 0, 7, 0, 0, 0, 0},
{6, 0, 0, 1, 9, 5, 0, 0, 0},
{0, 5, 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(isValid(mat) ? "true\n" : "false\n");
return 0;
}Java
// Java Program to check whether given sudoku board is valid
class GfG {
// Checks for duplicates in the current row
static boolean validRow(int[][] mat, int row) {
// Visited array to track occurrences
int[] vis = new int[10];
for (int i = 0; i < 9; i++) {
// If the cell is not empty
if (mat[row][i] != 0) {
int val = mat[row][i];
// If duplicate is found
if (vis[val] != 0)
return false;
// Mark the number as visited
vis[val]++;
}
}
return true;
}
// Checks for duplicates in the current column
static boolean colValid(int[][] mat, int col) {
// Visited array to track occurrences
int[] vis = new int[10];
for (int i = 0; i < 9; i++) {
// If the cell is not empty
if (mat[i][col] != 0) {
int val = mat[i][col];
// If duplicate is found
if (vis[val] != 0)
return false;
// Mark the number as visited
vis[val]++;
}
}
return true;
}
// Checks for duplicates in the current 3x3 submatrix
static boolean subMatValid(int[][] mat, int startRow,
int startCol) {
// Visited array to track occurrences
int[] vis = new int[10];
for (int row = 0; row < 3; row++) {
for (int col = 0; col < 3; col++) {
// Current element in the submatrix
int curr = mat[row + startRow][col + startCol];
// If the cell is not empty
if (curr != 0) {
// If duplicate is found
if (vis[curr] != 0)
return false;
// Mark the number as visited
vis[curr]++;
}
}
}
return true;
}
// Validates the Sudoku board
static boolean isValid(int[][] mat) {
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
// Check if the row, column,
// or submatrix is invalid
if (!validRow(mat, i) || !colValid(mat, j)
|| !subMatValid(mat, i - i % 3, j - j % 3))
return false;
}
}
return true;
}
public static void main(String[] args) {
int[][] mat = {
{9, 3, 0, 0, 7, 0, 0, 0, 0},
{6, 0, 0, 1, 9, 5, 0, 0, 0},
{0, 5, 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
# Python Program to check whether given sudoku board is valid
# Checks for duplicates in the current row
def validRow(mat, row):
# Visited array to track occurrences
vis = [0] * 10
for i in range(9):
# If the cell is not empty
if mat[row][i] != 0:
val = mat[row][i]
# If duplicate is found
if vis[val] != 0:
return False
# Mark the number as visited
vis[val] += 1
return True
# Checks for duplicates in the current column
def colValid(mat, col):
# Visited array to track occurrences
vis = [0] * 10
for i in range(9):
# If the cell is not empty
if mat[i][col] != 0:
val = mat[i][col]
# If duplicate is found
if vis[val] != 0:
return False
# Mark the number as visited
vis[val] += 1
return True
# Checks for duplicates in the current 3x3 submatrix
def subMatValid(mat, startRow, startCol):
# Visited array to track occurrences
vis = [0] * 10
for row in range(3):
for col in range(3):
# Current element in the submatrix
curr = mat[row + startRow][col + startCol]
# If the cell is not empty
if curr != 0:
# If duplicate is found
if vis[curr] != 0:
return False
# Mark the number as visited
vis[curr] += 1
return True
# Validates the Sudoku board
def isValid(mat):
for i in range(9):
for j in range(9):
# Check if the row, column, or submatrix is invalid
if not validRow(mat, i) or not colValid(mat, j) or \
not subMatValid(mat, i - i % 3, j - j % 3):
return False
return True
# Driver code
mat = [
[9, 3, 0, 0, 7, 0, 0, 0, 0],
[6, 0, 0, 1, 9, 5, 0, 0, 0],
[0, 5, 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#
// C# Program to check whether given sudoku is valid
using System;
class GfG {
// Checks for duplicates in the current row
static bool ValidRow(int[, ] mat, int row)
{
// Visited array to track occurrences
int[] vis = new int[10];
for (int i = 0; i < 9; i++) {
// If the cell is not empty
if (mat[row, i] != 0) {
int val = mat[row, i];
// If duplicate is found
if (vis[val] != 0)
return false;
// Mark the number as visited
vis[val]++;
}
}
return true;
}
// Checks for duplicates in the current column
static bool ColValid(int[, ] mat, int col)
{
// Visited array to track occurrences
int[] vis = new int[10];
for (int i = 0; i < 9; i++) {
// If the cell is not empty
if (mat[i, col] != 0) {
int val = mat[i, col];
// If duplicate is found
if (vis[val] != 0)
return false;
// Mark the number as visited
vis[val]++;
}
}
return true;
}
// Checks for duplicates in current 3x3 submatrix
static bool SubMatValid(int[, ] mat, int startRow,
int startCol)
{
// Visited array to track occurrences
int[] vis = new int[10];
for (int row = 0; row < 3; row++) {
for (int col = 0; col < 3; col++) {
// Current element in the submatrix
int curr
= mat[row + startRow, col + startCol];
// If the cell is not empty
if (curr != 0) {
// If duplicate is found
if (vis[curr] != 0)
return false;
// Mark the number as visited
vis[curr]++;
}
}
}
return true;
}
// Validates the Sudoku board
static bool IsValid(int[, ] mat)
{
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
// Check if the row, column, or submatrix is
// invalid
if (!ValidRow(mat, i) || !ColValid(mat, j)
|| !SubMatValid(mat, i - i % 3,
j - j % 3))
return false;
}
}
return true;
}
static void Main(){
int[, ] mat = { { 9, 3, 0, 0, 7, 0, 0, 0, 0 },
{ 6, 0, 0, 1, 9, 5, 0, 0, 0 },
{ 0, 5, 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");
}
}JavaScript
// JavaScript Program to check whether given sudoku board is
// valid
// Checks for duplicates in the current row
function validRow(mat, row)
{
// Visited array to track occurrences
let vis = Array(10).fill(0);
for (let i = 0; i < 9; i++) {
// If the cell is not empty
if (mat[row][i] !== 0) {
let val = mat[row][i];
// If duplicate is found
if (vis[val] !== 0)
return false;
// Mark the number as visited
vis[val]++;
}
}
return true;
}
// Checks for duplicates in the current column
function colValid(mat, col)
{
// Visited array to track occurrences
let vis = Array(10).fill(0);
for (let i = 0; i < 9; i++) {
// If the cell is not empty
if (mat[i][col] !== 0) {
let val = mat[i][col];
// If duplicate is found
if (vis[val] !== 0)
return false;
// Mark the number as visited
vis[val]++;
}
}
return true;
}
// Checks for duplicates in the current 3x3 submatrix
function subMatValid(mat, startRow, startCol)
{
// Visited array to track occurrences
let vis = Array(10).fill(0);
for (let row = 0; row < 3; row++) {
for (let col = 0; col < 3; col++) {
// Current element in the submatrix
let curr = mat[row + startRow][col + startCol];
// If the cell is not empty
if (curr !== 0) {
// If duplicate is found
if (vis[curr] !== 0)
return false;
// Mark the number as visited
vis[curr]++;
}
}
}
return true;
}
// Validates the Sudoku board
function isValid(mat)
{
for (let i = 0; i < 9; i++) {
for (let j = 0; j < 9; j++) {
// Check if the row, column, or submatrix is
// invalid
if (!validRow(mat, i) || !colValid(mat, j)
|| !subMatValid(mat, i - i % 3, j - j % 3))
return false;
}
}
return true;
}
// Driver code
let mat = [
[ 9, 3, 0, 0, 7, 0, 0, 0, 0 ],
[ 6, 0, 0, 1, 9, 5, 0, 0, 0 ],
[ 0, 5, 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.log(isValid(mat) ? "true" : "false");Output : True
Time Complexity: O(n3) for every cell we must verify duplicacy with row, column, and sub-matrix. There are thus n^2 cells, and for every cell validation n processes are involved.
O(n) auxiliary space for storing row, column, and sub-matrix value.