# Java Program to solve Sudoku

J

This program is based on Depth First Search or Back track Algorithm.

``````package com.csetutorials;

import java.util.Arrays;
import java.util.Scanner;
import java.util.Set;
import java.util.TreeSet;

public class Sudoku {

public static void main(String[] args) {
Sudoku sudoku = new Sudoku();

// Creating a sudoku board
int[][] board = new int[][] {
{ 0, 0, 0, 0, 0, 6, 0, 0, 0 },
{ 0, 2, 7, 5, 1, 0, 9, 0, 8 },
{ 3, 9, 0, 7, 0, 0, 0, 0, 5 },
{ 0, 1, 0, 0, 0, 0, 0, 0, 0 },
{ 9, 0, 4, 0, 0, 0, 3, 0, 6 },
{ 0, 0, 0, 0, 0, 0, 0, 4, 0 },
{ 5, 0, 0, 0, 0, 7, 0, 9, 4 },
{ 8, 0, 1, 0, 6, 5, 2, 3, 0 },
{ 0, 0, 0, 4, 0, 0, 0, 0, 0 } };
int[][] result = sudoku.getResult(board);

// Printing the final result
sudoku.printSudoku(result);
}

public int[][] getResult(int[][] board) {
int row, column;
Set<Integer> possibleValuesList;
for (row = 0; row < 9; row++) {
for (column = 0; column < 9; column++) {
if (board[row][column] != 0) {
continue;
}
// Getting possible values that can be
// filled at position [row, column]
possibleValuesList = getPossibleValues(row,
column, board);

// If there are no such values that can be
// pass another possible value to child (recursion)
if (possibleValuesList.size() == 0) {
return null;
} else {
for(int possibleValue:possibleValuesList){

// Identical sudoku but its filled with
// a possible value
int[][] copy = getCopy(row, column,
possibleValue, board);

// Recursion
int[][] result = getResult(copy);
if (result != null) {
return result;
}
}
// If non of the posible values could give
return null;
}
}
}

// Returning final result
return board;
}

// Create a clone of existing sudoku and fill the
// num at [row, column]
public int[][] getCopy(int row, int column, int num,
int[][] board) {
int[][] board_copy = new int[board.length][];
for (int i = 0; i < board.length; i++) {
board_copy[i] = board[i].clone();
}
board_copy[row][column] = num;
return board_copy;
}

// Returns the list of values that can be filled
// at [row, column]
public Set<Integer> getPossibleValues(int row,
int column, int[][] board) {
int i, j;

// Get already filled horizontal elements
for (i = 0; i < 9; i++) {
}

// Get already filled vertical elements
for (i = 0; i < 9; i++) {
}

// Get all elements which are in the same box
// as the point/number [row, column]
int boxRowStart = row - row % 3,
boxColumnStart = column - column % 3;
for (i = boxRowStart; i < boxRowStart + 3; i++) {
for (j = boxColumnStart; j < boxColumnStart + 3; j++) {
}
}

for (i = 1; i <= 9; i++) {
}
}

// Printing sudoku
private void printSudoku(int[][] board) {
System.out.println("Printing Result");
int row, column;
for (row = 0; row < 9; row++) {
for (column = 0; column < 9; column++) {
System.out.print(board[row][column] + " ");
}
System.out.println();
}
}

// Takes the input from user and returns the board
public int[][] getInputFromUser() {
int[][] board = new int[9][9];
Scanner kb = new Scanner(System.in);
int row, column;
for (row = 0; row < 9; row++) {
for (column = 0; column < 9; column++) {
board[row][column] = kb.nextInt();
}
}
kb.close();
return board;
}
}
``````

Using this algorithm I have created sudoku solver on github.

Published in:
Originally Published On : Oct 18, 2016