Solve Sudoku Puzzle
Here given code implementation process.
// C program
// Solve Sudoku Puzzle
#include <stdio.h>
#define N 9
//Check that given number are suitable to particular row and column or not
int is_vaild(int grid[N][N], int row, int col, int num)
{
//Define loop controlling variable
int i = 0;
int j = 0;
// Test case 1
// Check that whether given number are exist in given row and column or not
for (i = 0; i < N; ++i)
{
if (grid[row][i] == num || grid[i][col] == num)
{
//When given number already exists in given row and column
return 0;
}
}
//Test case 2
//Check that given number are exist in 3x3 sub grid or not
for (i = 0; i < 3; ++i)
{
for (j = 0; j < 3; ++j)
{
if (grid[(row - row % 3) + i][(col - col % 3) + j] == num)
{
//When subgrid contains element
//Then it is not valid
return 0;
}
}
}
//When number is valid
return 1;
}
//Find the location of empty element in given grid
int new_empty_location(int grid[N][N])
{
//Loop controlling variable
int i = 0;
int j = 0;
for (i = 0; i < N; ++i)
{
for (j = 0; j < N; ++j)
{
if (grid[i][j] == 0)
{
//When empty location exist
return (N * i) + j;
}
}
}
return -1;
}
//Recursive find solution of given grid
int sudoku(int grid[N][N])
{
int location = new_empty_location(grid);
if (location == -1)
{
//When sudoku is complete
return 1;
}
// Define some auxiliary variables
int row = 0;
int col = 0;
int num = -1;
if (location != 0)
{
//Get current change element location
//Get element row
row = location / N;
//Get element column
col = location % N;
}
for (num = 1; num <= 9; ++num)
{
if (is_vaild(grid, row, col, num) == 1)
{
//Set this number of location [row][col]
grid[row][col] = num;
if (sudoku(grid) == 1)
{
// When sudoku is solved
return 1;
}
//reset value
grid[row][col] = 0;
}
}
return 0;
}
//Display grid elements
void display(int grid[N][N])
{
//Loop controlling variable
int i = 0;
int j = 0;
for (i = 0; i < N; ++i)
{
for (j = 0; j < N; ++j)
{
printf(" %d", grid[i][j]);
}
printf("\n");
}
}
int main()
{
// Given sudoku problem here
// N number of row and col
int grid[N][N] = {
{ 9, 0, 1, 2, 3, 0, 8, 0, 0},
{ 0, 0, 0, 0, 9, 0, 2, 0, 0},
{ 7, 0, 2, 0, 8, 0, 0, 3, 0},
{ 0, 2, 0, 0, 0, 0, 7, 6, 0},
{ 6, 1, 4, 0, 0, 0, 0, 0, 0},
{ 0, 0, 0, 0, 2, 0, 0, 0, 0},
{ 2, 7, 5, 9, 4, 0, 0, 1, 0},
{ 0, 4, 0, 7, 0, 2, 9, 5, 8},
{ 0, 0, 6, 3, 0, 0, 0, 0, 0}
};
display(grid);
int result = sudoku(grid);
if (result == 1)
{
printf("\n Output Result \n\n");
display(grid);
}
else
{
//In case given input are not have solution
printf("\n No result \n");
}
return 0;
}
Output
9 0 1 2 3 0 8 0 0
0 0 0 0 9 0 2 0 0
7 0 2 0 8 0 0 3 0
0 2 0 0 0 0 7 6 0
6 1 4 0 0 0 0 0 0
0 0 0 0 2 0 0 0 0
2 7 5 9 4 0 0 1 0
0 4 0 7 0 2 9 5 8
0 0 6 3 0 0 0 0 0
Output Result
9 5 1 2 3 7 8 4 6
4 3 8 1 9 6 2 7 5
7 6 2 4 8 5 1 3 9
5 2 9 8 1 3 7 6 4
6 1 4 5 7 9 3 8 2
3 8 7 6 2 4 5 9 1
2 7 5 9 4 8 6 1 3
1 4 3 7 6 2 9 5 8
8 9 6 3 5 1 4 2 7
/*
Java Program
Solve sudoku puzzle
*/
class SolveSudoku
{
//Sudoku {N} grid size
public int size;
public SolveSudoku(int size)
{
//Assuming that given size are suitable to sudoku
this.size = size;
}
//Check that given number are suitable to particular row and column or not
public boolean is_vaild(int[][] grid, int row, int col, int num)
{
//Define loop controlling variable
int i = 0;
int j = 0;
// Test case 1
// Check that whether given number are exist in given row and column or not
for (i = 0; i < this.size; ++i)
{
if (grid[row][i] == num || grid[i][col] == num)
{
//When given number already exists in given row and column
return false;
}
}
//Test case 2
//Check that given number are exist in 3x3 sub grid or not
for (i = 0; i < 3; ++i)
{
for (j = 0; j < 3; ++j)
{
if (grid[(row - row % 3) + i][(col - col % 3) + j] == num)
{
//When subgrid contains element
//Then it is not valid
return false;
}
}
}
//When number is valid
return true;
}
//Find the location of empty element in given grid
public int new_empty_location(int[][] grid)
{
//Loop controlling variable
int i = 0;
int j = 0;
for (i = 0; i < this.size; ++i)
{
for (j = 0; j < this.size; ++j)
{
if (grid[i][j] == 0)
{
//When empty element exist
//return it's location
return (i *this.size) + j;
}
}
}
return -1;
}
//Recursive find solution of given grid
public boolean sudoku(int[][] grid)
{
int location = new_empty_location(grid);
if (location == -1)
{
//When sudoku is complete
return true;
}
// Define some auxiliary variables
int row = 0;
int col = 0;
int num = -1;
if (location != 0)
{
//Get current change element location
//Get element row
row = location / this.size;
//Get element column
col = location % this.size;
}
for (num = 1; num <= 9; num++)
{
if (is_vaild(grid, row, col, num) == true)
{
//Set this number of location [row][col]
grid[row][col] = num;
if (sudoku(grid) == true)
{
// When sudoku is solved
return true;
}
//reset value
grid[row][col] = 0;
}
}
return false;
}
//Display grid elements
public void display(int[][] grid)
{
//Loop controlling variable
int i = 0;
int j = 0;
for (i = 0; i < this.size; ++i)
{
for (j = 0; j < this.size; ++j)
{
System.out.print(" " + grid[i][j]);
}
System.out.print("\n");
}
}
public static void main(String[] args)
{
int n = 9;
SolveSudoku obj = new SolveSudoku(n);
int[][] grid = {
{ 9, 0, 1, 2, 3, 0, 8, 0, 0},
{ 0, 0, 0, 0, 9, 0, 2, 0, 0},
{ 7, 0, 2, 0, 8, 0, 0, 3, 0},
{ 0, 2, 0, 0, 0, 0, 7, 6, 0},
{ 6, 1, 4, 0, 0, 0, 0, 0, 0},
{ 0, 0, 0, 0, 2, 0, 0, 0, 0},
{ 2, 7, 5, 9, 4, 0, 0, 1, 0},
{ 0, 4, 0, 7, 0, 2, 9, 5, 8},
{ 0, 0, 6, 3, 0, 0, 0, 0, 0}
};
obj.display(grid);
if (obj.sudoku(grid))
{
System.out.print("\n Output Result \n\n");
obj.display(grid);
}
else
{
//In case given input are not have solution
System.out.print("\n No result \n");
obj.display(grid);
}
}
}
Output
9 0 1 2 3 0 8 0 0
0 0 0 0 9 0 2 0 0
7 0 2 0 8 0 0 3 0
0 2 0 0 0 0 7 6 0
6 1 4 0 0 0 0 0 0
0 0 0 0 2 0 0 0 0
2 7 5 9 4 0 0 1 0
0 4 0 7 0 2 9 5 8
0 0 6 3 0 0 0 0 0
Output Result
9 5 1 2 3 7 8 4 6
4 3 8 1 9 6 2 7 5
7 6 2 4 8 5 1 3 9
5 2 9 8 1 3 7 6 4
6 1 4 5 7 9 3 8 2
3 8 7 6 2 4 5 9 1
2 7 5 9 4 8 6 1 3
1 4 3 7 6 2 9 5 8
8 9 6 3 5 1 4 2 7
//Include header file
#include <iostream>
#define N 9
using namespace std;
/*
C++ Program
Solve sudoku puzzle
*/
class SolveSudoku
{
public:
//Sudoku {N} grid size
int size;
SolveSudoku(int size)
{
//Assuming that given size are suitable to sudoku
this->size = size;
}
//Check that given number are suitable to particular row and column or not
bool is_vaild(int grid[N][N], int row, int col, int num)
{
//Define loop controlling variable
int i = 0;
int j = 0;
// Test case 1
// Check that whether given number are exist in given row and column or not
for (i = 0; i < this->size; ++i)
{
if (grid[row][i] == num || grid[i][col] == num)
{
//When given number already exists in given row and column
return false;
}
}
//Test case 2
//Check that given number are exist in 3x3 sub grid or not
for (i = 0; i < 3; ++i)
{
for (j = 0; j < 3; ++j)
{
if (grid[(row - row % 3) + i][(col - col % 3) + j] == num)
{
//When subgrid contains element
//Then it is not valid
return false;
}
}
}
//When number is valid
return true;
}
//Find the location of empty element in given grid
int new_empty_location(int grid[N][N])
{
//Loop controlling variable
int i = 0;
int j = 0;
for (i = 0; i < this->size; ++i)
{
for (j = 0; j < this->size; ++j)
{
if (grid[i][j] == 0)
{
//When empty element exist
//return it's location
return (i * this->size) + j;
}
}
}
return -1;
}
//Recursive find solution of given grid
bool sudoku(int grid[N][N])
{
int location = this->new_empty_location(grid);
if (location == -1)
{
//When sudoku is complete
return true;
}
// Define some auxiliary variables
int row = 0;
int col = 0;
int num = -1;
if (location != 0)
{
//Get current change element location
//Get element row
row = location / this->size;
//Get element column
col = location % this->size;
}
for (num = 1; num <= 9; num++)
{
if (this->is_vaild(grid, row, col, num) == true)
{
//Set this number of location [row][col]
grid[row][col] = num;
if (this->sudoku(grid) == true)
{
// When sudoku is solved
return true;
}
//reset value
grid[row][col] = 0;
}
}
return false;
}
//Display grid elements
void display(int grid[N][N])
{
//Loop controlling variable
int i = 0;
int j = 0;
for (i = 0; i < this->size; ++i)
{
for (j = 0; j < this->size; ++j)
{
cout << " " << grid[i][j];
}
cout << "\n";
}
}
};
int main()
{
SolveSudoku obj = SolveSudoku(N);
int grid[N][N] = {
{
9 , 0 , 1 , 2 , 3 , 0 , 8 , 0 , 0
} , {
0 , 0 , 0 , 0 , 9 , 0 , 2 , 0 , 0
} , {
7 , 0 , 2 , 0 , 8 , 0 , 0 , 3 , 0
} , {
0 , 2 , 0 , 0 , 0 , 0 , 7 , 6 , 0
} , {
6 , 1 , 4 , 0 , 0 , 0 , 0 , 0 , 0
} , {
0 , 0 , 0 , 0 , 2 , 0 , 0 , 0 , 0
} , {
2 , 7 , 5 , 9 , 4 , 0 , 0 , 1 , 0
} , {
0 , 4 , 0 , 7 , 0 , 2 , 9 , 5 , 8
} , {
0 , 0 , 6 , 3 , 0 , 0 , 0 , 0 , 0
}
};
obj.display(grid);
if (obj.sudoku(grid))
{
cout << "\n Output Result \n\n";
obj.display(grid);
}
else
{
//In case given input are not have solution
cout << "\n No result \n";
obj.display(grid);
}
return 0;
}
Output
9 0 1 2 3 0 8 0 0
0 0 0 0 9 0 2 0 0
7 0 2 0 8 0 0 3 0
0 2 0 0 0 0 7 6 0
6 1 4 0 0 0 0 0 0
0 0 0 0 2 0 0 0 0
2 7 5 9 4 0 0 1 0
0 4 0 7 0 2 9 5 8
0 0 6 3 0 0 0 0 0
Output Result
9 5 1 2 3 7 8 4 6
4 3 8 1 9 6 2 7 5
7 6 2 4 8 5 1 3 9
5 2 9 8 1 3 7 6 4
6 1 4 5 7 9 3 8 2
3 8 7 6 2 4 5 9 1
2 7 5 9 4 8 6 1 3
1 4 3 7 6 2 9 5 8
8 9 6 3 5 1 4 2 7
//Include namespace system
using System;
/*
C# Program
Solve sudoku puzzle
*/
class SolveSudoku
{
//Sudoku {N} grid size
public int size;
public SolveSudoku(int size)
{
//Assuming that given size are suitable to sudoku
this.size = size;
}
//Check that given number are suitable to particular row and column or not
public Boolean is_vaild(int[,] grid, int row, int col, int num)
{
//Define loop controlling variable
int i = 0;
int j = 0;
// Test case 1
// Check that whether given number are exist in given row and column or not
for (i = 0; i < this.size; ++i)
{
if (grid[row,i] == num || grid[i,col] == num)
{
//When given number already exists in given row and column
return false;
}
}
//Test case 2
//Check that given number are exist in 3x3 sub grid or not
for (i = 0; i < 3; ++i)
{
for (j = 0; j < 3; ++j)
{
if (grid[(row - row % 3) + i,(col - col % 3) + j] == num)
{
//When subgrid contains element
//Then it is not valid
return false;
}
}
}
//When number is valid
return true;
}
//Find the location of empty element in given grid
public int new_empty_location(int[,] grid)
{
//Loop controlling variable
int i = 0;
int j = 0;
for (i = 0; i < this.size; ++i)
{
for (j = 0; j < this.size; ++j)
{
if (grid[i,j] == 0)
{
//When empty element exist
//return it's location
return (i * this.size) + j;
}
}
}
return -1;
}
//Recursive find solution of given grid
public Boolean sudoku(int[,] grid)
{
int location = new_empty_location(grid);
if (location == -1)
{
//When sudoku is complete
return true;
}
// Define some auxiliary variables
int row = 0;
int col = 0;
int num = -1;
if (location != 0)
{
//Get current change element location
//Get element row
row = location / this.size;
//Get element column
col = location % this.size;
}
for (num = 1; num <= 9; num++)
{
if (is_vaild(grid, row, col, num) == true)
{
//Set this number of location [row,col]
grid[row,col] = num;
if (sudoku(grid) == true)
{
// When sudoku is solved
return true;
}
//reset value
grid[row,col] = 0;
}
}
return false;
}
//Display grid elements
public void display(int[,] grid)
{
//Loop controlling variable
int i = 0;
int j = 0;
for (i = 0; i < this.size; ++i)
{
for (j = 0; j < this.size; ++j)
{
Console.Write(" " + grid[i,j]);
}
Console.Write("\n");
}
}
public static void Main(String[] args)
{
int n = 9;
SolveSudoku obj = new SolveSudoku(n);
int[,] grid = {
{
9 , 0 , 1 , 2 , 3 , 0 , 8 , 0 , 0
} , {
0 , 0 , 0 , 0 , 9 , 0 , 2 , 0 , 0
} , {
7 , 0 , 2 , 0 , 8 , 0 , 0 , 3 , 0
} , {
0 , 2 , 0 , 0 , 0 , 0 , 7 , 6 , 0
} , {
6 , 1 , 4 , 0 , 0 , 0 , 0 , 0 , 0
} , {
0 , 0 , 0 , 0 , 2 , 0 , 0 , 0 , 0
} , {
2 , 7 , 5 , 9 , 4 , 0 , 0 , 1 , 0
} , {
0 , 4 , 0 , 7 , 0 , 2 , 9 , 5 , 8
} , {
0 , 0 , 6 , 3 , 0 , 0 , 0 , 0 , 0
}
};
obj.display(grid);
if (obj.sudoku(grid))
{
Console.Write("\n Output Result \n\n");
obj.display(grid);
}
else
{
//In case given input are not have solution
Console.Write("\n No result \n");
obj.display(grid);
}
}
}
Output
9 0 1 2 3 0 8 0 0
0 0 0 0 9 0 2 0 0
7 0 2 0 8 0 0 3 0
0 2 0 0 0 0 7 6 0
6 1 4 0 0 0 0 0 0
0 0 0 0 2 0 0 0 0
2 7 5 9 4 0 0 1 0
0 4 0 7 0 2 9 5 8
0 0 6 3 0 0 0 0 0
Output Result
9 5 1 2 3 7 8 4 6
4 3 8 1 9 6 2 7 5
7 6 2 4 8 5 1 3 9
5 2 9 8 1 3 7 6 4
6 1 4 5 7 9 3 8 2
3 8 7 6 2 4 5 9 1
2 7 5 9 4 8 6 1 3
1 4 3 7 6 2 9 5 8
8 9 6 3 5 1 4 2 7
<?php
/*
Php Program
Solve sudoku puzzle
*/
class SolveSudoku
{
//Sudoku {N} grid size
public $size;
function __construct($size)
{
//Assuming that given size are suitable to sudoku
$this->size = $size;
}
//Check that given number are suitable to particular row and column or not
public function is_vaild( & $grid, $row, $col, $num)
{
//Define loop controlling variable
$i = 0;
$j = 0;
// Test case 1
// Check that whether given number are exist in given row and column or not
for ($i = 0; $i < $this->size; ++$i)
{
if ($grid[$row][$i] == $num || $grid[$i][$col] == $num)
{
//When given number already exists in given row and column
return false;
}
}
//Test case 2
//Check that given number are exist in 3x3 sub grid or not
for ($i = 0; $i < 3; ++$i)
{
for ($j = 0; $j < 3; ++$j)
{
if ($grid[($row - $row % 3) + $i][($col - $col % 3) + $j] == $num)
{
//When subgrid contains element
//Then it is not valid
return false;
}
}
}
//When number is valid
return true;
}
//Find the location of empty element in given grid
public function new_empty_location( & $grid)
{
//Loop controlling variable
$i = 0;
$j = 0;
for ($i = 0; $i < $this->size; ++$i)
{
for ($j = 0; $j < $this->size; ++$j)
{
if ($grid[$i][$j] == 0)
{
//When empty element exist
//return it's location
return ($i * $this->size) + $j;
}
}
}
return -1;
}
//Recursive find solution of given grid
public function sudoku( & $grid)
{
$location = $this->new_empty_location($grid);
if ($location == -1)
{
//When sudoku is complete
return true;
}
// Define some auxiliary variables
$row = 0;
$col = 0;
$num = -1;
if ($location != 0)
{
//Get current change element location
//Get element row
$row = intval($location / $this->size);
//Get element column
$col = $location % $this->size;
}
for ($num = 1; $num <= 9; $num++)
{
if ($this->is_vaild($grid, $row, $col, $num) == true)
{
//Set this number of location [row][col]
$grid[$row][$col] = $num;
if ($this->sudoku($grid) == true)
{
// When sudoku is solved
return true;
}
//reset value
$grid[$row][$col] = 0;
}
}
return false;
}
//Display grid elements
public function display( & $grid)
{
//Loop controlling variable
$i = 0;
$j = 0;
for ($i = 0; $i < $this->size; ++$i)
{
for ($j = 0; $j < $this->size; ++$j)
{
echo " ". $grid[$i][$j];
}
echo "\n";
}
}
}
function main()
{
$n = 9;
$obj = new SolveSudoku($n);
$grid = array(array(9, 0, 1, 2, 3, 0, 8, 0, 0), array(0, 0, 0, 0, 9, 0, 2, 0, 0), array(7, 0, 2, 0, 8, 0, 0, 3, 0), array(0, 2, 0, 0, 0, 0, 7, 6, 0), array(6, 1, 4, 0, 0, 0, 0, 0, 0), array(0, 0, 0, 0, 2, 0, 0, 0, 0), array(2, 7, 5, 9, 4, 0, 0, 1, 0), array(0, 4, 0, 7, 0, 2, 9, 5, 8), array(0, 0, 6, 3, 0, 0, 0, 0, 0));
$obj->display($grid);
if ($obj->sudoku($grid))
{
echo "\n Output Result \n\n";
$obj->display($grid);
}
else
{
//In case given input are not have solution
echo "\n No result \n";
$obj->display($grid);
}
}
main();
Output
9 0 1 2 3 0 8 0 0
0 0 0 0 9 0 2 0 0
7 0 2 0 8 0 0 3 0
0 2 0 0 0 0 7 6 0
6 1 4 0 0 0 0 0 0
0 0 0 0 2 0 0 0 0
2 7 5 9 4 0 0 1 0
0 4 0 7 0 2 9 5 8
0 0 6 3 0 0 0 0 0
Output Result
9 5 1 2 3 7 8 4 6
4 3 8 1 9 6 2 7 5
7 6 2 4 8 5 1 3 9
5 2 9 8 1 3 7 6 4
6 1 4 5 7 9 3 8 2
3 8 7 6 2 4 5 9 1
2 7 5 9 4 8 6 1 3
1 4 3 7 6 2 9 5 8
8 9 6 3 5 1 4 2 7
/*
Node Js Program
Solve sudoku puzzle
*/
class SolveSudoku
{
//Sudoku {N} grid size
constructor(size)
{
//Assuming that given size are suitable to sudoku
this.size = size;
}
//Check that given number are suitable to particular row and column or not
is_vaild(grid, row, col, num)
{
//Define loop controlling variable
var i = 0;
var j = 0;
// Test case 1
// Check that whether given number are exist in given row and column or not
for (i = 0; i < this.size; ++i)
{
if (grid[row][i] == num || grid[i][col] == num)
{
//When given number already exists in given row and column
return false;
}
}
//Test case 2
//Check that given number are exist in 3x3 sub grid or not
for (i = 0; i < 3; ++i)
{
for (j = 0; j < 3; ++j)
{
if (grid[(row - row % 3) + i][(col - col % 3) + j] == num)
{
//When subgrid contains element
//Then it is not valid
return false;
}
}
}
//When number is valid
return true;
}
//Find the location of empty element in given grid
new_empty_location(grid)
{
//Loop controlling variable
var i = 0;
var j = 0;
for (i = 0; i < this.size; ++i)
{
for (j = 0; j < this.size; ++j)
{
if (grid[i][j] == 0)
{
//When empty element exist
//return it's location
return (i * this.size) + j;
}
}
}
return -1;
}
//Recursive find solution of given grid
sudoku(grid)
{
var location = this.new_empty_location(grid);
if (location == -1)
{
//When sudoku is complete
return true;
}
// Define some auxiliary variables
var row = 0;
var col = 0;
var num = -1;
if (location != 0)
{
//Get current change element location
//Get element row
row = parseInt(location / this.size);
//Get element column
col = location % this.size;
}
for (num = 1; num <= 9; num++)
{
if (this.is_vaild(grid, row, col, num) == true)
{
//Set this number of location [row][col]
grid[row][col] = num;
if (this.sudoku(grid) == true)
{
// When sudoku is solved
return true;
}
//reset value
grid[row][col] = 0;
}
}
return false;
}
//Display grid elements
display(grid)
{
//Loop controlling variable
var i = 0;
var j = 0;
for (i = 0; i < this.size; ++i)
{
for (j = 0; j < this.size; ++j)
{
process.stdout.write(" " + grid[i][j]);
}
process.stdout.write("\n");
}
}
}
function main()
{
var n = 9;
var obj = new SolveSudoku(n);
var grid = [
[9, 0, 1, 2, 3, 0, 8, 0, 0],
[0, 0, 0, 0, 9, 0, 2, 0, 0],
[7, 0, 2, 0, 8, 0, 0, 3, 0],
[0, 2, 0, 0, 0, 0, 7, 6, 0],
[6, 1, 4, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 2, 0, 0, 0, 0],
[2, 7, 5, 9, 4, 0, 0, 1, 0],
[0, 4, 0, 7, 0, 2, 9, 5, 8],
[0, 0, 6, 3, 0, 0, 0, 0, 0]
];
obj.display(grid);
if (obj.sudoku(grid))
{
process.stdout.write("\n Output Result \n\n");
obj.display(grid);
}
else
{
//In case given input are not have solution
process.stdout.write("\n No result \n");
obj.display(grid);
}
}
main();
Output
9 0 1 2 3 0 8 0 0
0 0 0 0 9 0 2 0 0
7 0 2 0 8 0 0 3 0
0 2 0 0 0 0 7 6 0
6 1 4 0 0 0 0 0 0
0 0 0 0 2 0 0 0 0
2 7 5 9 4 0 0 1 0
0 4 0 7 0 2 9 5 8
0 0 6 3 0 0 0 0 0
Output Result
9 5 1 2 3 7 8 4 6
4 3 8 1 9 6 2 7 5
7 6 2 4 8 5 1 3 9
5 2 9 8 1 3 7 6 4
6 1 4 5 7 9 3 8 2
3 8 7 6 2 4 5 9 1
2 7 5 9 4 8 6 1 3
1 4 3 7 6 2 9 5 8
8 9 6 3 5 1 4 2 7
# Python 3 Program
# Solve sudoku puzzle
class SolveSudoku :
def __init__(self, size) :
# Assuming that given size are suitable to sudoku
# Sudoku N grid size
self.size = size
# Check that given number are suitable to particular row and column or not
def is_vaild(self, grid, row, col, num) :
# Define loop controlling variable
i = 0
j = 0
# Test case 1
# Check that whether given number are exist in given row and column or not
while (i < self.size) :
if (grid[row][i] == num or grid[i][col] == num) :
# When given number already exists in given row and column
return False
i += 1
# Test case 2
# Check that given number are exist in 3x3 sub grid or not
i = 0
while (i < 3) :
j = 0
while (j < 3) :
if (grid[(row - row % 3) + i][(col - col % 3) + j] == num) :
# When subgrid contains element
# Then it is not valid
return False
j += 1
i += 1
# When number is valid
return True
# Find the location of empty element in given grid
def new_empty_location(self, grid) :
# Loop controlling variable
i = 0
j = 0
while (i < self.size) :
j = 0
while (j < self.size) :
if (grid[i][j] == 0) :
# When empty element exist
# return it's location
return (i * self.size) + j
j += 1
i += 1
return -1
# Recursive find solution of given grid
def sudoku(self, grid) :
location = self.new_empty_location(grid)
if (location == -1) :
# When sudoku is complete
return True
# Define some auxiliary variables
row = 0
col = 0
num = 1
if (location != 0) :
# Get current change element location
# Get element row
row = int(location / self.size)
# Get element column
col = location % self.size
while (num <= 9) :
if (self.is_vaild(grid, row, col, num) == True) :
# Set this number of location [row][col]
grid[row][col] = num
if (self.sudoku(grid) == True) :
# When sudoku is solved
return True
# reset value
grid[row][col] = 0
num += 1
return False
# Display grid elements
def display(self, grid) :
# Loop controlling variable
i = 0
j = 0
while (i < self.size) :
j = 0
while (j < self.size) :
print(" ", grid[i][j], end = "")
j += 1
print("\n", end = "")
i += 1
def main() :
n = 9
obj = SolveSudoku(n)
grid = [
[9, 0, 1, 2, 3, 0, 8, 0, 0],
[0, 0, 0, 0, 9, 0, 2, 0, 0],
[7, 0, 2, 0, 8, 0, 0, 3, 0],
[0, 2, 0, 0, 0, 0, 7, 6, 0],
[6, 1, 4, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 2, 0, 0, 0, 0],
[2, 7, 5, 9, 4, 0, 0, 1, 0],
[0, 4, 0, 7, 0, 2, 9, 5, 8],
[0, 0, 6, 3, 0, 0, 0, 0, 0]
]
obj.display(grid)
if (obj.sudoku(grid)) :
print("\n Output Result \n\n", end = "")
obj.display(grid)
else :
# In case given input are not have solution
print("\n No result \n", end = "")
obj.display(grid)
if __name__ == "__main__": main()
Output
9 0 1 2 3 0 8 0 0
0 0 0 0 9 0 2 0 0
7 0 2 0 8 0 0 3 0
0 2 0 0 0 0 7 6 0
6 1 4 0 0 0 0 0 0
0 0 0 0 2 0 0 0 0
2 7 5 9 4 0 0 1 0
0 4 0 7 0 2 9 5 8
0 0 6 3 0 0 0 0 0
Output Result
9 5 1 2 3 7 8 4 6
4 3 8 1 9 6 2 7 5
7 6 2 4 8 5 1 3 9
5 2 9 8 1 3 7 6 4
6 1 4 5 7 9 3 8 2
3 8 7 6 2 4 5 9 1
2 7 5 9 4 8 6 1 3
1 4 3 7 6 2 9 5 8
8 9 6 3 5 1 4 2 7
# Ruby Program
# Solve sudoku puzzle
class SolveSudoku
# Define the accessor and reader of class SolveSudoku
attr_reader :size
attr_accessor :size
# Sudoku Nend grid size
def initialize(size)
# Assuming that given size are suitable to sudoku
self.size = size
end
# Check that given number are suitable to particular row and column or not
def is_vaild(grid, row, col, num)
# Define loop controlling variable
i = 0
j = 0
# Test case 1
# Check that whether given number are exist in given row and column or not
while (i < self.size)
if (grid[row][i] == num || grid[i][col] == num)
# When given number already exists in given row and column
return false
end
i += 1
end
# Test case 2
# Check that given number are exist in 3x3 sub grid or not
i = 0
while (i < 3)
j = 0
while (j < 3)
if (grid[(row - row % 3) + i][(col - col % 3) + j] == num)
# When subgrid contains element
# Then it is not valid
return false
end
j += 1
end
i += 1
end
# When number is valid
return true
end
# Find the location of empty element in given grid
def new_empty_location(grid)
# Loop controlling variable
i = 0
j = 0
while (i < self.size)
j = 0
while (j < self.size)
if (grid[i][j] == 0)
# When empty element exist
# return it's location
return (i * self.size) + j
end
j += 1
end
i += 1
end
return -1
end
# Recursive find solution of given grid
def sudoku(grid)
location = self.new_empty_location(grid)
if (location == -1)
# When sudoku is complete
return true
end
# Define some auxiliary variables
row = 0
col = 0
num = 1
if (location != 0)
# Get current change element location
# Get element row
row = location / self.size
# Get element column
col = location % self.size
end
while (num <= 9)
if (self.is_vaild(grid, row, col, num) == true)
# Set this number of location [row][col]
grid[row][col] = num
if (self.sudoku(grid) == true)
# When sudoku is solved
return true
end
# reset value
grid[row][col] = 0
end
num += 1
end
return false
end
# Display grid elements
def display(grid)
# Loop controlling variable
i = 0
j = 0
while (i < self.size)
j = 0
while (j < self.size)
print(" ", grid[i][j])
j += 1
end
print("\n")
i += 1
end
end
end
def main()
n = 9
obj = SolveSudoku.new(n)
grid = [
[9, 0, 1, 2, 3, 0, 8, 0, 0],
[0, 0, 0, 0, 9, 0, 2, 0, 0],
[7, 0, 2, 0, 8, 0, 0, 3, 0],
[0, 2, 0, 0, 0, 0, 7, 6, 0],
[6, 1, 4, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 2, 0, 0, 0, 0],
[2, 7, 5, 9, 4, 0, 0, 1, 0],
[0, 4, 0, 7, 0, 2, 9, 5, 8],
[0, 0, 6, 3, 0, 0, 0, 0, 0]
]
obj.display(grid)
if (obj.sudoku(grid))
print("\n Output Result \n\n")
obj.display(grid)
else
# In case given input are not have solution
print("\n No result \n")
obj.display(grid)
end
end
main()
Output
9 0 1 2 3 0 8 0 0
0 0 0 0 9 0 2 0 0
7 0 2 0 8 0 0 3 0
0 2 0 0 0 0 7 6 0
6 1 4 0 0 0 0 0 0
0 0 0 0 2 0 0 0 0
2 7 5 9 4 0 0 1 0
0 4 0 7 0 2 9 5 8
0 0 6 3 0 0 0 0 0
Output Result
9 5 1 2 3 7 8 4 6
4 3 8 1 9 6 2 7 5
7 6 2 4 8 5 1 3 9
5 2 9 8 1 3 7 6 4
6 1 4 5 7 9 3 8 2
3 8 7 6 2 4 5 9 1
2 7 5 9 4 8 6 1 3
1 4 3 7 6 2 9 5 8
8 9 6 3 5 1 4 2 7
/*
Scala Program
Solve sudoku puzzle
*/
class SolveSudoku(var size: Int)
{
//Check that given number are suitable to particular row and column or not
def is_vaild(grid: Array[Array[Int]], row: Int, col: Int, num: Int): Boolean = {
//Define loop controlling variable
var i: Int = 0;
var j: Int = 0;
// Test case 1
// Check that whether given number are exist in given row and column or not
while (i < this.size)
{
if (grid(row)(i) == num || grid(i)(col) == num)
{
//When given number already exists in given row and column
return false;
}
i += 1;
}
//Test case 2
//Check that given number are exist in 3x3 sub grid or not
i = 0;
while (i < 3)
{
j = 0;
while (j < 3)
{
if (grid((row - row % 3) + i)((col - col % 3) + j) == num)
{
//When subgrid contains element
//Then it is not valid
return false;
}
j += 1;
}
i += 1;
}
//When number is valid
return true;
}
//Find the location of empty element in given grid
def new_empty_location(grid: Array[Array[Int]]): Int = {
//Loop controlling variable
var i: Int = 0;
var j: Int = 0;
while (i < this.size)
{
j = 0;
while (j < this.size)
{
if (grid(i)(j) == 0)
{
//When empty element exist
//return it's location
return (i * this.size) + j;
}
j += 1;
}
i += 1;
}
return -1;
}
//Recursive find solution of given grid
def sudoku(grid: Array[Array[Int]]): Boolean = {
var location: Int = new_empty_location(grid);
if (location == -1)
{
//When sudoku is complete
return true;
}
// Define some auxiliary variables
var row: Int = 0;
var col: Int = 0;
var num: Int = 1;
if (location != 0)
{
//Get current change element location
//Get element row
row = (location / this.size).toInt;
//Get element column
col = location % this.size;
}
while (num <= 9)
{
if (is_vaild(grid, row, col, num) == true)
{
//Set this number of location [row][col]
grid(row)(col) = num;
if (sudoku(grid) == true)
{
// When sudoku is solved
return true;
}
//reset value
grid(row)(col) = 0;
}
num += 1;
}
return false;
}
//Display grid elements
def display(grid: Array[Array[Int]]): Unit = {
//Loop controlling variable
var i: Int = 0;
var j: Int = 0;
while (i < this.size)
{
j = 0;
while (j < this.size)
{
print(" " + grid(i)(j));
j += 1;
}
print("\n");
i += 1;
}
}
}
object Main
{
def main(args: Array[String]): Unit = {
var n: Int = 9;
var obj: SolveSudoku = new SolveSudoku(n);
var grid: Array[Array[Int]] = Array(Array(9, 0, 1, 2, 3, 0, 8, 0, 0), Array(0, 0, 0, 0, 9, 0, 2, 0, 0), Array(7, 0, 2, 0, 8, 0, 0, 3, 0), Array(0, 2, 0, 0, 0, 0, 7, 6, 0), Array(6, 1, 4, 0, 0, 0, 0, 0, 0), Array(0, 0, 0, 0, 2, 0, 0, 0, 0), Array(2, 7, 5, 9, 4, 0, 0, 1, 0), Array(0, 4, 0, 7, 0, 2, 9, 5, 8), Array(0, 0, 6, 3, 0, 0, 0, 0, 0));
obj.display(grid);
if (obj.sudoku(grid))
{
print("\n Output Result \n\n");
obj.display(grid);
}
else
{
//In case given input are not have solution
print("\n No result \n");
obj.display(grid);
}
}
}
Output
9 0 1 2 3 0 8 0 0
0 0 0 0 9 0 2 0 0
7 0 2 0 8 0 0 3 0
0 2 0 0 0 0 7 6 0
6 1 4 0 0 0 0 0 0
0 0 0 0 2 0 0 0 0
2 7 5 9 4 0 0 1 0
0 4 0 7 0 2 9 5 8
0 0 6 3 0 0 0 0 0
Output Result
9 5 1 2 3 7 8 4 6
4 3 8 1 9 6 2 7 5
7 6 2 4 8 5 1 3 9
5 2 9 8 1 3 7 6 4
6 1 4 5 7 9 3 8 2
3 8 7 6 2 4 5 9 1
2 7 5 9 4 8 6 1 3
1 4 3 7 6 2 9 5 8
8 9 6 3 5 1 4 2 7
/*
Swift Program
Solve sudoku puzzle
*/
class SolveSudoku
{
//Sudoku {N} grid size
var size: Int;
init(_ size: Int)
{
//Assuming that given size are suitable to sudoku
self.size = size;
}
//Check that given number are suitable to particular row and column or not
func is_vaild(_ grid: [
[Int]
], _ row: Int, _ col: Int, _ num: Int) -> Bool
{
//Define loop controlling variable
var i: Int = 0;
var j: Int = 0;
// Test case 1
// Check that whether given number are exist in given row and column or not
while (i < self.size)
{
if (grid[row][i] == num || grid[i][col] == num)
{
//When given number already exists in given row and column
return false;
}
i += 1;
}
//Test case 2
//Check that given number are exist in 3x3 sub grid or not
i = 0;
while (i < 3)
{
j = 0;
while (j < 3)
{
if (grid[(row - row % 3) + i][(col - col % 3) + j] == num)
{
//When subgrid contains element
//Then it is not valid
return false;
}
j += 1;
}
i += 1;
}
//When number is valid
return true;
}
//Find the location of empty element in given grid
func new_empty_location(_ grid: [
[Int]
]) -> Int
{
//Loop controlling variable
var i: Int = 0;
var j: Int = 0;
while (i < self.size)
{
j = 0;
while (j < self.size)
{
if (grid[i][j] == 0)
{
//When empty element exist
//return it"s location
return (i * self.size) + j;
}
j += 1;
}
i += 1;
}
return -1;
}
//Recursive find solution of given grid
func sudoku(_ grid: inout[[Int]]) -> Bool
{
let location: Int = self.new_empty_location(grid);
if (location == -1)
{
//When sudoku is complete
return true;
}
// Define some auxiliary variables
var row: Int = 0;
var col: Int = 0;
var num: Int = 1;
if (location != 0)
{
//Get current change element location
//Get element row
row = location / self.size;
//Get element column
col = location % self.size;
}
while (num <= 9)
{
if (self.is_vaild(grid, row, col, num) == true)
{
//Set this number of location [row][col]
grid[row][col] = num;
if (self.sudoku(&grid) == true)
{
// When sudoku is solved
return true;
}
//reset value
grid[row][col] = 0;
}
num += 1;
}
return false;
}
//Display grid elements
func display(_ grid: [
[Int]
])
{
//Loop controlling variable
var i: Int = 0;
var j: Int = 0;
while (i < self.size)
{
j = 0;
while (j < self.size)
{
print(" ", grid[i][j], terminator: "");
j += 1;
}
print("\n", terminator: "");
i += 1;
}
}
}
func main()
{
let n: Int = 9;
let obj: SolveSudoku = SolveSudoku(n);
var grid: [
[Int]
] = [
[9, 0, 1, 2, 3, 0, 8, 0, 0],
[0, 0, 0, 0, 9, 0, 2, 0, 0],
[7, 0, 2, 0, 8, 0, 0, 3, 0],
[0, 2, 0, 0, 0, 0, 7, 6, 0],
[6, 1, 4, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 2, 0, 0, 0, 0],
[2, 7, 5, 9, 4, 0, 0, 1, 0],
[0, 4, 0, 7, 0, 2, 9, 5, 8],
[0, 0, 6, 3, 0, 0, 0, 0, 0]
];
obj.display(grid);
if (obj.sudoku(&grid))
{
print("\n Output Result \n\n", terminator: "");
obj.display(grid);
}
else
{
//In case given input are not have solution
print("\n No result \n", terminator: "");
obj.display(grid);
}
}
main();
Output
9 0 1 2 3 0 8 0 0
0 0 0 0 9 0 2 0 0
7 0 2 0 8 0 0 3 0
0 2 0 0 0 0 7 6 0
6 1 4 0 0 0 0 0 0
0 0 0 0 2 0 0 0 0
2 7 5 9 4 0 0 1 0
0 4 0 7 0 2 9 5 8
0 0 6 3 0 0 0 0 0
Output Result
9 5 1 2 3 7 8 4 6
4 3 8 1 9 6 2 7 5
7 6 2 4 8 5 1 3 9
5 2 9 8 1 3 7 6 4
6 1 4 5 7 9 3 8 2
3 8 7 6 2 4 5 9 1
2 7 5 9 4 8 6 1 3
1 4 3 7 6 2 9 5 8
8 9 6 3 5 1 4 2 7
Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.
New Comment