Developing a Sudoku solver

I've never been great at solving Sudoku because I find it boring to sit down for an hour staring at boxes some filled and others to be filled with numbers. But I think it's an interesting game. I've always thought of developing an algorithm to solve any given Sudoku puzzle. I've had this in my mind from the very first year of my under graduation but I never gave it a serious thought. If you have seen my previous post, it's about backtracking which is a general algorithm used to solve many problems such as the classical N-Queens problem(I've solved it in that post). Yesterday I tried solving a question on the Hackerrank site which required me to use the backtracking algorithm and I was successful in devising an algorithm to solve it. I felt the question was very similar to solving a Sudoku puzzle so I thought of creating a sudoku solver and I've done it! It was simpler than what I thought it would be. All you need to know is how to use backtracking. If you don't know what backtracking is, just have a look at my previous post and I hope it'd help you.

Here's a video of me solving a Sudoku puzzle at 'Evil' mode using the Sudoku solver  I developed. Hope you enjoy it.

Now coming back to Sudoku solver, I've not taken the time to see any other algorithm so this is my own approach to the problem and I think it's pretty straight forward and easy to understand. To solve the Sudoku I'll be using these methods:

1. canPlace(): This function is used to check whether we can place a particular value at a particular position in the Sudoku.
2. solveSudoku(): This function uses backtracking and canPlace() method to solve the Sudoku. If the given Sudoku does not have a solution, it returns false.
3. displayBoard(): A simple function to display the numbers of a Sudoku puzzle(a box) which is simply a 2-Dimensional  array.
4. insertNumbers(): A function to insert numbers into the Sudoku before it gets solved. You are required to mention row number, column number and value for each entry.
5. insertFileNumbers(): This function is used to read the Sudoku entries from a mentioned file. To fill a sudoku having N*N boxes, the text must have N*N lines. The first line denotes the number at the first row and first column. The second line represents value at the first row and second column (and) so on. For not mentioning any value, you can leave the line empty or insert any non-number string.

The main logic only depends on the first two functions mentioned which are canPlace() and solveSudoku(). Both of these functions are Boolean returning functions. here are the algorithms for these functions:

1. canPlace() function algorithm:
   

   	//x,y are the row number and column number
   	//of the newly inserted value into the
   	//Sudoku box[][] of size n*n.
   	//This function evaluates whether the newly
   	//inserted value is whether valid or not
   	boolean canPlace(x, y, box[][], n)
   	{
   	if any cell of the xth row has the same value
   	return false
   	if any cell of the yth column has the same value
   	return false
   	if any cell of the inner box has the same value
   	return flase
   	return true
   	}

   view raw algorithm for canPlace() hosted with ❤ by GitHub
2. solveSudoku() function algorithm:
   

   	//x,y are the row number and column number
   	//where the new value must be inserted into
   	//the Sudoku box[][] of size n*n.
   	//This function evaluates whether solving the
   	//given Sudoku box[][] is possible or not
   	boolean solveSudoku(x, y, box[][], n)
   	{
   	//base case or the terminating condition
   	if x = n
   	//all the rows(0 to n-1) have been filled successfully
   	return true
   	if box[x][y] != 0
   	{
   	//A fixed number is mentioned which can't be changed
   	//so check for the next cell
   	if y = n-1
   	//end of the column approached
   	x = x+1 //moving to next row
   	y = -1 //moving to initial column-1
   	//recursive call within if condition
   	if !(solveSudoku(x,y+1,box[][],n))
   	//if placing values at next cells wasn't successful
   	return false
   	else
   	return true
   	}
   	else
   	{
   	//A fixed number isn't mentioned
   	//So each cell can take n values
   	for i = 1 to n
   	{
   	//inserting value i at cell (x,y)
   	box[x][y] = i
   	if !(canPlace(x,y,box[][],n))
   	//if placing values at present cell wasn't successful
   	box[x][y] = 0 //erase inserted value
   	continue //try inserting next value
   	//placing at the presnt cell i.e, (x,y) was successful
   	//so now we try placing at next cell
   	if y = n-1
   	//end of the column approached
   	next_x = x+1 //moving to next row
   	next_y = -1 //moving to initial column-1
   	//we use new varialbles next_x and next_y because
   	//in case of failure of placing values at next cells,
   	//the value at (x,y) must be again changed
   	//recursive call within if condition
   	if !(solveSudoku(next_x,next_y+1,box[][],n))
   	//if placing values at next cells wasn't successful
   	box[x][y] = 0 //erase inserted value at (x,y)
   	continue //try inserting next value
   	//placing values at next cells was also successful
   	return true
   	}
   	}
   	//unable to place anyone of the n values at the cell (x,y)
   	//so the Sudoku can't be solved
   	return false
   	}

   view raw algorithm for solveSudoku() hosted with ❤ by GitHub

I hope the above algorithms are clear enough to help you understand the logic behind Sudoku solver. Here's the code for java implementation of Sudoku solver with all of the five methods mentioned above along with the main() function.

	import java.util.*;
	import java.io.*;
	class SudokuSolver {
	public static boolean canPlace (int x, int y, int[][] box, int n) {
	//checking rows and columns
	for (int i = 0; i < n; i++) {
	//row check
	if ((box[x][i] == box[x][y]) && (i != y)) {
	return false;
	}
	//column check
	if ((box[i][y] == box[x][y]) && (i != x)) {
	return false;
	}
	}
	int sqrt_n = (int)Math.sqrt(n);
	int row_start = (x / sqrt_n) * sqrt_n;
	int col_start = (y / sqrt_n) * sqrt_n;
	//checking the smaller-box
	for (int i = row_start; i < row_start + sqrt_n; i++) {
	for (int j = col_start; j < col_start + sqrt_n; j++) {
	if(((i != x) || (j != y)) && (box[i][j] == box[x][y])) {
	return false;
	}
	}
	}
	return true;
	}
	public static boolean solveSudoku (int x, int y, int[][] box, int n) {
	if (x == n) {
	return true; //all have been placed
	}
	if (box[x][y] != 0) { //already placed
	//else solve next block recursively
	if (y == n-1) {
	y = -1;
	x += 1;
	}
	if (!solveSudoku(x, y+1, box, n)) {
	return false;
	}
	return true;
	}
	else {
	for (int i = 1; i <= n; i++) {
	box[x][y] = i;
	if(!canPlace(x,y,box,n)) {
	box[x][y] = 0;
	continue; //if cannot place, try next number
	}
	//else solve next block recursively
	int next_x = x;
	int next_y = y;
	if (y == n-1) {
	next_y = -1;
	next_x += 1;
	}
	if (!solveSudoku(next_x, next_y+1, box, n)) {
	box[x][y] = 0;
	continue; //if cannot place, any further block
	}
	return true;
	}
	}
	return false;
	}
	public static void displayBoard (int[][] box, int n) {
	System.out.println("\n");
	for (int i = 0; i < n; i++) {
	for (int j = 0; j < n; j++) {
	System.out.printf("| %2d |", box[i][j]);
	}
	System.out.println("\n");
	}
	System.out.println("\n");
	}
	public static void insertNumbers (int[][] box, int n) {
	int cont = 1;
	while (cont != 0) {
	Scanner s = new Scanner(System.in);
	System.out.print("\n\nenter row no: ");
	int x = s.nextInt();
	System.out.print("enter col no: ");
	int y = s.nextInt();
	System.out.print("enter the value: ");
	int v = s.nextInt();
	if ((x > n) || (y > n) || (v > n) || (x < 1) || (y < 1) || (v < 1)) {
	System.out.println("ERROR: Wrong entry. row no, col no & value must be < n and > 1.");
	}
	else {
	box[x-1][y-1] = v;
	if (!canPlace(x-1,y-1,box,n)) {
	box[x-1][y-1] = 0;
	System.out.println("ERROR: Wrong entry. Cannot place entered value.");
	}
	else {
	displayBoard(box, n);
	}
	}
	System.out.print("(press 0 to exit or any other key to enter again): ");
	cont = s.nextInt();
	}
	}
	public static void insertFileNumbers (int[][] box, int n) throws IOException {
	Scanner s = new Scanner(System.in);
	System.out.print("enter file name: ");
	String file_name = s.nextLine();
	RandomAccessFile raf = null;
	try {
	raf = new RandomAccessFile(file_name + ".txt", "r");
	}
	catch (Exception e) {
	System.out.println("ERROR: correct <File names> not provided.\n");
	System.exit(1);
	}
	for (int i = 0; i < n; i++) {
	for (int j = 0; j < n; j++) {
	String line = raf.readLine();
	int number;
	try {
	number = Integer.parseInt(line);
	}
	catch (Exception e) {
	continue;
	}
	System.out.println("value insertead at [" + (i+1) + "][" + (j+1) + "]: " + number);
	box[i][j] = number;
	if (!canPlace(i,j,box,n) || number > n || number < 1) {
	box[i][j] = 0;
	System.out.println("ERROR: Invalid entries present in file.");
	System.exit(1);
	}
	raf.readLine();
	}
	}
	raf.close();
	}
	public static void main (String args[]) throws Exception {
	Scanner s = new Scanner(System.in);
	System.out.print("enter value of sqrt(n): ");
	int n = s.nextInt();
	n *= n;
	int box[][] = new int [n][n];
	displayBoard(box, n);
	insertFileNumbers(box, n);
	displayBoard(box, n);
	if (solveSudoku(0,0,box,n)) {
	System.out.println("Solved!");
	displayBoard(box, n);
	}
	else {
	System.out.println("No solution found.");
	displayBoard(box, n);
	}
	}
	}

view raw SudokuSolver.java hosted with ❤ by GitHub

I know this can be further developed into a good application but my intention of developing the program wasn't that. I just wanted to devise an algorithm to solve any given valid Sudoku puzzle.