Skip to main content

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
Last updated on by Kalkicode




Comment

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