Given a partially filled 9×9 2D array ‘grid[9][9]’, the goal is to assign digits (from 1 to 9) to the empty cells so that every row, column, and subgrid of size 3×3 contains exactly one instance of the digits from 1 to 9.
Examples:
Input: grid
{ {3, 0, 6, 5, 0, 8, 4, 0, 0},
{5, 2, 0, 0, 0, 0, 0, 0, 0},
{0, 8, 7, 0, 0, 0, 0, 3, 1},
{0, 0, 3, 0, 1, 0, 0, 8, 0},
{9, 0, 0, 8, 6, 3, 0, 0, 5},
{0, 5, 0, 0, 9, 0, 6, 0, 0},
{1, 3, 0, 0, 0, 0, 2, 5, 0},
{0, 0, 0, 0, 0, 0, 0, 7, 4},
{0, 0, 5, 2, 0, 6, 3, 0, 0} }
Output:
3 1 6 5 7 8 4 9 2
5 2 9 1 3 4 7 6 8
4 8 7 6 2 9 5 3 1
2 6 3 4 1 5 9 8 7
9 7 4 8 6 3 1 2 5
8 5 1 7 9 2 6 4 3
1 3 8 9 4 7 2 5 6
6 9 2 3 5 1 8 7 4
7 4 5 2 8 6 3 1 9
Each row, column and 3*3 box of the output matrix contains unique numbers.
Input: grid
{ { 3, 1, 6, 5, 7, 8, 4, 9, 2 },
{ 5, 2, 9, 1, 3, 4, 7, 6, 8 },
{ 4, 8, 7, 6, 2, 9, 5, 3, 1 },
{ 2, 6, 3, 0, 1, 5, 9, 8, 7 },
{ 9, 7, 4, 8, 6, 0, 1, 2, 5 },
{ 8, 5, 1, 7, 9, 2, 6, 4, 3 },
{ 1, 3, 8, 0, 4, 7, 2, 0, 6 },
{ 6, 9, 2, 3, 5, 1, 8, 7, 4 },
{ 7, 4, 5, 0, 8, 6, 3, 1, 0 } };
Output:
3 1 6 5 7 8 4 9 2
5 2 9 1 3 4 7 6 8
4 8 7 6 2 9 5 3 1
2 6 3 4 1 5 9 8 7
9 7 4 8 6 3 1 2 5
8 5 1 7 9 2 6 4 3
1 3 8 9 4 7 2 5 6
6 9 2 3 5 1 8 7 4
7 4 5 2 8 6 3 1 9
Each row, column and 3*3 box of the output matrix contains unique numbers.
Follow the steps below to solve the problem:
- Create a function that checks after assigning the current index the grid becomes unsafe or not. Keep Hashmap for a row, column and boxes. If any number has a frequency greater than 1 in the hashMap return false else return true; hashMap can be avoided by using loops.
- Create a recursive function that takes a grid.
- Check for any unassigned location.
- If present then assigns a number from 1 to 9.
- Check if assigning the number to current index makes the grid unsafe or not.
- If safe then recursively call the function for all safe cases from 0 to 9.
- If any recursive call returns true, end the loop and return true. If no recursive call returns true then return false.
- If there is no unassigned location then return true.
#include <iostream>
using namespace std;
/* A utility function to print grid */
void print(int arr[N][N])
{
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
cout << arr[i][j] << " ";
cout << endl;
}
}
bool isSafe(int grid[N][N], int row,
int col, int num)
{
// Check if we find the same num
// in the similar row , we
// return false
for (int x = 0; x <= 8; x++)
if (grid[row][x] == num)
return false;
// Check if we find the same num in
// the similar column , we
// return false
for (int x = 0; x <= 8; x++)
if (grid[x][col] == num)
return false;
// Check if we find the same num in
// the particular 3*3 matrix,
// we return false
int startRow = row - row % 3,
startCol = col - col % 3;
for (int i = 0; i < 3; i++)
for (int j = 0; j < 3; j++)
if (grid[i + startRow][j +
startCol] == num)
return false;
return true;
}
bool solveSudoku(int grid[N][N], int row, int col)
{
if (row == N - 1 && col == N)
return true;
// Check if column value becomes 9 ,
// we move to next row and
// column start from 0
if (col == N) {
row++;
col = 0;
}
// Check if the current position of
// the grid already contains
// value >0, we iterate for next column
if (grid[row][col] > 0)
return solveSudoku(grid, row, col + 1);
for (int num = 1; num <= N; num++)
{
// Check if it is safe to place
// the num (1-9) in the
// given row ,col ->we
// move to next column
if (isSafe(grid, row, col, num))
{
grid[row][col] = num;
// Checking for next possibility with next
// column
if (solveSudoku(grid, row, col + 1))
return true;
}
grid[row][col] = 0;
}
return false;
}
int main()
{
int grid[N][N] = { { 3, 0, 6, 5, 0, 8, 4, 0, 0 },
{ 5, 2, 0, 0, 0, 0, 0, 0, 0 },
{ 0, 8, 7, 0, 0, 0, 0, 3, 1 },
{ 0, 0, 3, 0, 1, 0, 0, 8, 0 },
{ 9, 0, 0, 8, 6, 3, 0, 0, 5 },
{ 0, 5, 0, 0, 9, 0, 6, 0, 0 },
{ 1, 3, 0, 0, 0, 0, 2, 5, 0 },
{ 0, 0, 0, 0, 0, 0, 0, 7, 4 },
{ 0, 0, 5, 2, 0, 6, 3, 0, 0 } };
if (solveSudoku(grid, 0, 0))
print(grid);
else
cout << "no solution exists " << endl;
return 0;
}
Output:
3 1 6 5 7 8 4 9 2
5 2 9 1 3 4 7 6 8
4 8 7 6 2 9 5 3 1
2 6 3 4 1 5 9 8 7
9 7 4 8 6 3 1 2 5
8 5 1 7 9 2 6 4 3
1 3 8 9 4 7 2 5 6
6 9 2 3 5 1 8 7 4
7 4 5 2 8 6 3 1 9
// Java program for above approach
public class Sudoku {
// N is the size of the 2D matrix N*N
static int N = 9;
/* Takes a partially filled-in grid and attempts
to assign values to all unassigned locations in
such a way to meet the requirements for
Sudoku solution (non-duplication across rows,
columns, and boxes) */
static boolean solveSudoku(int grid[][], int row,
int col)
{
/*if we have reached the 8th
row and 9th column (0
indexed matrix) ,
we are returning true to avoid further
backtracking */
if (row == N - 1 && col == N)
return true;
// Check if column value becomes 9 ,
// we move to next row
// and column start from 0
if (col == N) {
row++;
col = 0;
}
// Check if the current position
// of the grid already
// contains value >0, we iterate
// for next column
if (grid[row][col] != 0)
return solveSudoku(grid, row, col + 1);
for (int num = 1; num < 10; num++) {
// Check if it is safe to place
// the num (1-9) in the
// given row ,col ->we move to next column
if (isSafe(grid, row, col, num)) {
/* assigning the num in the current
(row,col) position of the grid and
assuming our assigned num in the position
is correct */
grid[row][col] = num;
// Checking for next
// possibility with next column
if (solveSudoku(grid, row, col + 1))
return true;
}
/* removing the assigned num , since our
assumption was wrong , and we go for next
assumption with diff num value */
grid[row][col] = 0;
}
return false;
}
/* A utility function to print grid */
static void print(int[][] grid)
{
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++)
System.out.print(grid[i][j] + " ");
System.out.println();
}
}
// Check whether it will be legal
// to assign num to the
// given row, col
static boolean isSafe(int[][] grid, int row, int col,
int num)
{
// Check if we find the same num
// in the similar row , we
// return false
for (int x = 0; x <= 8; x++)
if (grid[row][x] == num)
return false;
// Check if we find the same num
// in the similar column ,
// we return false
for (int x = 0; x <= 8; x++)
if (grid[x][col] == num)
return false;
// Check if we find the same num
// in the particular 3*3
// matrix, we return false
int startRow = row - row % 3, startCol
= col - col % 3;
for (int i = 0; i < 3; i++)
for (int j = 0; j < 3; j++)
if (grid[i + startRow][j + startCol] == num)
return false;
return true;
}
// Driver Code
public static void main(String[] args)
{
int grid[][] = { { 3, 0, 6, 5, 0, 8, 4, 0, 0 },
{ 5, 2, 0, 0, 0, 0, 0, 0, 0 },
{ 0, 8, 7, 0, 0, 0, 0, 3, 1 },
{ 0, 0, 3, 0, 1, 0, 0, 8, 0 },
{ 9, 0, 0, 8, 6, 3, 0, 0, 5 },
{ 0, 5, 0, 0, 9, 0, 6, 0, 0 },
{ 1, 3, 0, 0, 0, 0, 2, 5, 0 },
{ 0, 0, 0, 0, 0, 0, 0, 7, 4 },
{ 0, 0, 5, 2, 0, 6, 3, 0, 0 } };
if (solveSudoku(grid, 0, 0))
print(grid);
else
System.out.println("No Solution exists");
}
} # N is the size of the 2D matrix N*N
N = 9
# A utility function to print grid
def printing(arr):
for i in range(N):
for j in range(N):
print(arr[i][j], end=" ")
print()
# Checks whether it will be
# legal to assign num to the
# given row, col
def isSafe(grid, row, col, num):
# Check if we find the same num
# in the similar row , we
# return false
for x in range(9):
if grid[row][x] == num:
return False
# Check if we find the same num in
# the similar column , we
# return false
for x in range(9):
if grid[x][col] == num:
return False
# Check if we find the same num in
# the particular 3*3 matrix,
# we return false
startRow = row - row % 3
startCol = col - col % 3
for i in range(3):
for j in range(3):
if grid[i + startRow][j + startCol] == num:
return False
return True
# Takes a partially filled-in grid and attempts
# to assign values to all unassigned locations in
# such a way to meet the requirements for
# Sudoku solution (non-duplication across rows,
# columns, and boxes) */
def solveSudoku(grid, row, col):
# Check if we have reached the 8th
# row and 9th column (0
# indexed matrix) , we are
# returning true to avoid
# further backtracking
if (row == N - 1 and col == N):
return True
# Check if column value becomes 9 ,
# we move to next row and
# column start from 0
if col == N:
row += 1
col = 0
# Check if the current position of
# the grid already contains
# value >0, we iterate for next column
if grid[row][col] > 0:
return solveSudoku(grid, row, col + 1)
for num in range(1, N + 1, 1):
# Check if it is safe to place
# the num (1-9) in the
# given row ,col ->we
# move to next column
if isSafe(grid, row, col, num):
# Assigning the num in
# the current (row,col)
# position of the grid
# and assuming our assigned
# num in the position
# is correct
grid[row][col] = num
# Checking for next possibility with next
# column
if solveSudoku(grid, row, col + 1):
return True
# Removing the assigned num ,
# since our assumption
# was wrong , and we go for
# next assumption with
# diff num value
grid[row][col] = 0
return False
# Driver Code
# 0 means unassigned cells
grid = [[3, 0, 6, 5, 0, 8, 4, 0, 0],
[5, 2, 0, 0, 0, 0, 0, 0, 0],
[0, 8, 7, 0, 0, 0, 0, 3, 1],
[0, 0, 3, 0, 1, 0, 0, 8, 0],
[9, 0, 0, 8, 6, 3, 0, 0, 5],
[0, 5, 0, 0, 9, 0, 6, 0, 0],
[1, 3, 0, 0, 0, 0, 2, 5, 0],
[0, 0, 0, 0, 0, 0, 0, 7, 4],
[0, 0, 5, 2, 0, 6, 3, 0, 0]]
if (solveSudoku(grid, 0, 0)):
printing(grid)
else:
print("no solution exists ")
Output
3 1 6 5 7 8 4 9 2
5 2 9 1 3 4 7 6 8
4 8 7 6 2 9 5 3 1
2 6 3 4 1 5 9 8 7
9 7 4 8 6 3 1 2 5
8 5 1 7 9 2 6 4 3
1 3 8 9 4 7 2 5 6
6 9 2 3 5 1 8 7 4
7 4 5 2 8 6 3 1 9
#include <stdio.h>
#include <stdlib.h>
// N is the size of the 2D matrix N*N
#define N 9
/* A utility function to print grid */
void print(int arr[N][N])
{
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
printf("%d ",arr[i][j]);
printf("\n");
}
}
// Checks whether it will be legal
// to assign num to the
// given row, col
int isSafe(int grid[N][N], int row,
int col, int num)
{
// Check if we find the same num
// in the similar row , we return 0
for (int x = 0; x <= 8; x++)
if (grid[row][x] == num)
return 0;
// Check if we find the same num in the
// similar column , we return 0
for (int x = 0; x <= 8; x++)
if (grid[x][col] == num)
return 0;
// Check if we find the same num in the
// particular 3*3 matrix, we return 0
int startRow = row - row % 3,
startCol = col - col % 3;
for (int i = 0; i < 3; i++)
for (int j = 0; j < 3; j++)
if (grid[i + startRow][j +
startCol] == num)
return 0;
return 1;
}
/* Takes a partially filled-in grid and attempts
to assign values to all unassigned locations in
such a way to meet the requirements for
Sudoku solution (non-duplication across rows,
columns, and boxes) */
int solveSudoku(int grid[N][N], int row, int col)
{
// Check if we have reached the 8th row
// and 9th column (0
// indexed matrix) , we are
// returning true to avoid
// further backtracking
if (row == N - 1 && col == N)
return 1;
// Check if column value becomes 9 ,
// we move to next row and
// column start from 0
if (col == N)
{
row++;
col = 0;
}
// Check if the current position
// of the grid already contains
// value >0, we iterate for next column
if (grid[row][col] > 0)
return solveSudoku(grid, row, col + 1);
for (int num = 1; num <= N; num++)
{
// Check if it is safe to place
// the num (1-9) in the
// given row ,col ->we move to next column
if (isSafe(grid, row, col, num)==1)
{
/* assigning the num in the
current (row,col)
position of the grid
and assuming our assigned num
in the position
is correct */
grid[row][col] = num;
// Checking for next possibility with next
// column
if (solveSudoku(grid, row, col + 1)==1)
return 1;
}
// Removing the assigned num ,
// since our assumption
// was wrong , and we go for next
// assumption with
// diff num value
grid[row][col] = 0;
}
return 0;
}
int main()
{
// 0 means unassigned cells
int grid[N][N] = { { 3, 0, 6, 5, 0, 8, 4, 0, 0 },
{ 5, 2, 0, 0, 0, 0, 0, 0, 0 },
{ 0, 8, 7, 0, 0, 0, 0, 3, 1 },
{ 0, 0, 3, 0, 1, 0, 0, 8, 0 },
{ 9, 0, 0, 8, 6, 3, 0, 0, 5 },
{ 0, 5, 0, 0, 9, 0, 6, 0, 0 },
{ 1, 3, 0, 0, 0, 0, 2, 5, 0 },
{ 0, 0, 0, 0, 0, 0, 0, 7, 4 },
{ 0, 0, 5, 2, 0, 6, 3, 0, 0 } };
if (solveSudoku(grid, 0, 0)==1)
print(grid);
else
printf("No solution exists");
return 0;
// This is code is contributed by Pradeep Mondal P
}Output
3 1 6 5 7 8 4 9 2
5 2 9 1 3 4 7 6 8
4 8 7 6 2 9 5 3 1
2 6 3 4 1 5 9 8 7
9 7 4 8 6 3 1 2 5
8 5 1 7 9 2 6 4 3
1 3 8 9 4 7 2 5 6
6 9 2 3 5 1 8 7 4
7 4 5 2 8 6 3 1 9
// Javascript program for above approach
// N is the size of the 2D matrix N*N
let N = 9;
/* Takes a partially filled-in grid and attempts
to assign values to all unassigned locations in
such a way to meet the requirements for
Sudoku solution (non-duplication across rows,
columns, and boxes) */
function solveSudoku(grid, row, col)
{
/* If we have reached the 8th
row and 9th column (0
indexed matrix) ,
we are returning true to avoid further
backtracking */
if (row == N - 1 && col == N)
return true;
// Check if column value becomes 9 ,
// we move to next row
// and column start from 0
if (col == N)
{
row++;
col = 0;
}
// Check if the current position
// of the grid already
// contains value >0, we iterate
// for next column
if (grid[row][col] != 0)
return solveSudoku(grid, row, col + 1);
for(let num = 1; num < 10; num++)
{
// Check if it is safe to place
// the num (1-9) in the given
// row ,col ->we move to next column
if (isSafe(grid, row, col, num))
{
/* assigning the num in the current
(row,col) position of the grid and
assuming our assigned num in the position
is correct */
grid[row][col] = num;
// Checking for next
// possibility with next column
if (solveSudoku(grid, row, col + 1))
return true;
}
/* removing the assigned num , since our
assumption was wrong , and we go for next
assumption with diff num value */
grid[row][col] = 0;
}
return false;
}
/* A utility function to print grid */
function print(grid)
{
for(let i = 0; i < N; i++)
{
for(let j = 0; j < N; j++)
document.write(grid[i][j] + " ");
document.write("<br>");
}
}
// Check whether it will be legal
// to assign num to the
// given row, col
function isSafe(grid, row, col, num)
{
// Check if we find the same num
// in the similar row , we
// return false
for(let x = 0; x <= 8; x++)
if (grid[row][x] == num)
return false;
// Check if we find the same num
// in the similar column ,
// we return false
for(let x = 0; x <= 8; x++)
if (grid[x][col] == num)
return false;
// Check if we find the same num
// in the particular 3*3
// matrix, we return false
let startRow = row - row % 3,
startCol = col - col % 3;
for(let i = 0; i < 3; i++)
for(let j = 0; j < 3; j++)
if (grid[i + startRow][j + startCol] == num)
return false;
return true;
}
// Driver Code
let grid = [ [ 3, 0, 6, 5, 0, 8, 4, 0, 0 ],
[ 5, 2, 0, 0, 0, 0, 0, 0, 0 ],
[ 0, 8, 7, 0, 0, 0, 0, 3, 1 ],
[ 0, 0, 3, 0, 1, 0, 0, 8, 0 ],
[ 9, 0, 0, 8, 6, 3, 0, 0, 5 ],
[ 0, 5, 0, 0, 9, 0, 6, 0, 0 ],
[ 1, 3, 0, 0, 0, 0, 2, 5, 0 ],
[ 0, 0, 0, 0, 0, 0, 0, 7, 4 ],
[ 0, 0, 5, 2, 0, 6, 3, 0, 0 ] ]
if (solveSudoku(grid, 0, 0))
print(grid)
else
document.write("no solution exists ") // C# program for above approach
using System;
class tikitaka {
// N is the size of the 2D matrix N*N
static int N = 9;
/* Takes a partially filled-in grid and attempts
to assign values to all unassigned locations in
such a way to meet the requirements for
Sudoku solution (non-duplication across rows,
columns, and boxes) */
static bool solveSudoku(int[,] grid, int row,
int col)
{
/*if we have reached the 8th
row and 9th column (0
indexed matrix) ,
we are returning true to avoid further
backtracking */
if (row == N - 1 && col == N)
return true;
// Check if column value becomes 9 ,
// we move to next row
// and column start from 0
if (col == N) {
row++;
col = 0;
}
// Check if the current position
// of the grid already
// contains value >0, we iterate
// for next column
if (grid[row,col] != 0)
return solveSudoku(grid, row, col + 1);
for (int num = 1; num < 10; num++) {
// Check if it is safe to place
// the num (1-9) in the
// given row ,col ->we move to next column
if (isSafe(grid, row, col, num)) {
/* assigning the num in the current
(row,col) position of the grid and
assuming our assigned num in the position
is correct */
grid[row,col] = num;
// Checking for next
// possibility with next column
if (solveSudoku(grid, row, col + 1))
return true;
}
/* removing the assigned num , since our
assumption was wrong , and we go for next
assumption with diff num value */
grid[row,col] = 0;
}
return false;
}
/* A utility function to print grid */
static void print(int[,] grid)
{
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++)
Console.Write(grid[i,j] + " ");
Console.WriteLine();
}
}
// Check whether it will be legal
// to assign num to the
// given row, col
static bool isSafe(int[,] grid, int row, int col,
int num)
{
// Check if we find the same num
// in the similar row , we
// return false
for (int x = 0; x <= 8; x++)
if (grid[row,x] == num)
return false;
// Check if we find the same num
// in the similar column ,
// we return false
for (int x = 0; x <= 8; x++)
if (grid[x,col] == num)
return false;
// Check if we find the same num
// in the particular 3*3
// matrix, we return false
int startRow = row - row % 3, startCol
= col - col % 3;
for (int i = 0; i < 3; i++)
for (int j = 0; j < 3; j++)
if (grid[i + startRow,j + startCol] == num)
return false;
return true;
}
// Driver code
static void Main() {
int[,] grid = { { 3, 0, 6, 5, 0, 8, 4, 0, 0 },
{ 5, 2, 0, 0, 0, 0, 0, 0, 0 },
{ 0, 8, 7, 0, 0, 0, 0, 3, 1 },
{ 0, 0, 3, 0, 1, 0, 0, 8, 0 },
{ 9, 0, 0, 8, 6, 3, 0, 0, 5 },
{ 0, 5, 0, 0, 9, 0, 6, 0, 0 },
{ 1, 3, 0, 0, 0, 0, 2, 5, 0 },
{ 0, 0, 0, 0, 0, 0, 0, 7, 4 },
{ 0, 0, 5, 2, 0, 6, 3, 0, 0 } };
if (solveSudoku(grid, 0, 0))
print(grid);
else
Console.WriteLine("No Solution exists");
}
}