Introduction to Sudoku

Sudoku is a logic based, number placement puzzle. The objective is to fill the 9X9 puzzle with numbers from 1 to 9 such that each row, each column and each of the 3X3 sub-grids(or boxes) contain all the digits from 1 to 9. The given puzzle is a partially completed grid and each sudoku has only one solution.

a sample sudoku
here is a sample sudoku, which we will be working with in this post

Methods of Solving Sudoku

Backtracking

This is a brute-force search method of solving the sudoku in which each possible number is put into the empty boxes until an error occurs, then it returns(backtracks) to the last number and changes its value. e.g – in the given sudoku, the first cell is filled with the number 1. Then the second cell is filled with the number 1, where an error occurs. The program changes its value to 2, where again an error occurs. When it is filled with 3 there is no error, so it moves to next empty cell, and so on.

Stochastic Search

In this method, random numbers are placed in the empty cells and the number of errors is calculated. Then, the inserted numbers are shuffled to minimise the number of errors, until it reaches zero. Then the puzzle is solved.

Constraint Programming

In this method, the sudoku is broken down into rules which need to be satisfied. These constraints can be programmed to be satisfied and using this the possible numbers of each place can be reduced until one remains. This is the method used in this post.

Explaining the Sudoku Solver

Index of Spaces in the Sudoku and Possible Numbers

The sudoku is indexed from the top left to the bottom right starting with 0,0 to 8,8. The x- value increases from left to right and the y- value increase from top to bottom

Possible numbers refers to the numbers that can be placed in the current sudoku without any errors occuring. In this program, each function uses a specific sudoku rule to eliminate as many possible numbers. If there is only one possible number, it is the number that fits that space in the sudoku

Storing the Given Sudoku

To store the sudoku, I’ve chosen a 3 dimensional array (9X9X10). The first layer of the array, i.e., x,y,0 stores the given value of the sudoku. The remaining layers, i.e, x,y,z store the value 0 or 1. These layers represent the possible values of that space in the sudoku. For example, if the value of the array at 5,6,7 is equal to 1, it means 7 is a possible number in the space 5,6 in the sudoku. The value of empty spaces in the sudoku is 0.

Inputting the Sudoku

The input function is an overloaded function that either takes a manual input or reads a file that is passed as an argument. If no arguments are passed, the sudoku is inputted from top left to bottom right. If an argument is passed in the form of a string containing the name of the file, the file is opened and the sudoku is copied from its contents.

This is how you should run the program, when the puzzle is stored in a file called sudoku.txt containing:

000400200
002000018
506900030
069000300
050000021
800157609
000030960
900602050
000000702

java Sudoku "sudoku.txt"

Once the sudoku is stored in the array, the setPossibleNumber() function is called to set each possible number to 1, or true for all empty space. For spaces with a number, the possible numbers are set to 0(false) except for the value of that space. For example, if a space has the value 5, all possible numbers are set to 0, except for 5, which is set to 1.

Adding the Basic Constraints

Now it’s time to add functions which use the rules of sudoku to reduce possible numbers of each space

Checking the Rows and the Columns

This is a very simple part of the code. It runs a loop which checks each value in the row/column, by changing the x- or y- value in the array. If the space has a value, that value is removed from the possible numbers. Here is the code for this:

public static void checkRow(int x, int y){
		for(int i = 0; i < 9; i++){
			if(i != x && board[i][y][0] != 0)board[x][y][(board[i][y][0])] = 0;
		}
	}

public static void checkColumn(int x, int y){
		for(int i = 0; i < 9; i++){
			if(i != y && board[x][i][0] != 0)board[x][y][(board[x][i][0])] = 0; 
		}
	}

Checking in the Box

Checking the values of the box in which the x,y position belongs poses a challenge. You need to determine which space in the box the x,y belongs as it decides how many spaces in front, behind, above or below need to be checked. To solve this, the boxCoordinates() function returns an array containing the x- positions of the box, or the y- positions of the box, depending on the value passed

public static void checkBox(int x, int y){
		int[] a = boxCoordinates(y);
		int[] b = boxCoordinates(x);


		for(int z = 0; z < 3; z++){
			for(int k = 0; k < 3; k++){
				if(!(x == b[k] && y == a[z]) && board[(b[k])][(a[z])][0] != 0)board[x][y][(board[(b[k])][(a[z])][0])] = 0;
			}
		}
	}
boxCoordinates()

To find the coordinates of each space in the box, the divisibility by three is used. If the x- coordinate passed is 3, it is the corner piece of the box. So, the output should be {3,4,5}. As 3 is a multiple of the three, the value of ‘k'( the coordinate of the left/top corner of the box) is three. If 4 was passed, the value of ‘k’ would be (4 – 1) = 3 and the output would be {3,4,5}.

public static int[] boxCoordinates(int x){
		int[] coordinates = new int[3];
		int k = x - (x%3);
		for(int y = 0; y < 3; y++){
			coordinates[y] = k + y;
		}
		return coordinates;
	}

Here is how this function would be used to find the coordinates of position x,y

a[] = boxCoordinates(y);
b[] = boxCoordinates(x);

These arrays can be used in a nested for loop such as “board[(b[k])][(a[z])][0] “

Adding Values to the Solution

Values are only added to the solution when an empty space has only one possible number. The add() function checks if a space has only one possible number and if it does, it adds it to the solution

public static void add(){
		int k = 0;
		for(int x = 0; x < 9; x++){
			for(int y = 0; y < 9; y++){
				if(board[x][y][0] == 0){
					k = count(x,y);//count() counts the number of possible numbers
					if(k == 1){
						board[x][y][0] = possibleNumber(x,y);//possibleNumber() finds the possible number of that space
						added = true;
					}	
					k = 0;
				}
			}
		}		
	}

This function also changes the value of a boolean ‘added’ to true if a number has been added. This is used in the code to ensure that if it is unable to find a solution it stops the program instead of running an infinite loop

Printing the Board

The sudoku board is printed after each iteration, when a value is added. The printing is a simple nested for loop which prints the value of each space and ‘-‘ for each empty space

public static void printBoard(){
		for(int y = 0; y < 9; y++){
			for(int x = 0; x < 9; x++){
				if(board[x][y][0] == 0)System.out.print("- ");
				else System.out.print(board[x][y][0] + " ");
			}
			System.out.println();
		}
		System.out.println("\n \n \n");
	}

Advanced Constraints

Now it’s time to add advanced methods to find values of the sudoku, which are not directly taken from the rules

Unique Candidate

If in a row,column or box; a number is only possible in one space, the number must be placed there. For example if the number 1 can only be placed in 5,7 in the entire row x,7 then the value of 5,7 must be 1. To implement this rule, I have the uniqueCandidateRow(), UniqueCandidateColumn() and uniqueCandidateBox() functions. Each of them function similarly. They use a boolean called unique which is originally set to true. The function then checks the possible numbers of the row/column/box and sets unique to false if two spaces have that possible number. If unique remains true at the end of the check, it removes all possible numbers for that space except for the unique candidate.

public static void uniqueCandidateRow(int x, int y){
		
		boolean unique;
		for(int z = 1; z < 10; z++){
			unique = true;
			if(board[x][y][z] == 1){	
				for(int k = 0; k < 9; k++){
					if(x != k && board[x][y][z] == board[k][y][z]){
						unique = false;
						break;
					}				
				}
				if(unique){
					for(int k = 1; k < 10; k++)board[x][y][k] = 0;
					board[x][y][z] = 1;	
					break;
				}
			}
		}

Output

Here I will share some pictures showing the functioning of the solver

the initial stage of the solver
running the solver
the solved sudoku
the final steps of the solver along with the solved sudoku.

Here is the github link to access my code: https://github.com/ishaan420/Sudoku_Solver

Visits: 97

Leave a Reply

Your email address will not be published. Required fields are marked *