Sudoku – Solver

After a long time I’m writing this post. Today, I would like to explain you one of my project which I have worked on. This my programming Languages project – A 16 X 16 Sudoku Solver with a Java Driven program.

User can select any one of the language among C, Java, Python, Javascript, Prolog to solve the given sudoku. Details of this project are presented below:

1. A Java driven application is developed which takes input from the user to invoke solver in the respective language.

2. This is designed to solve 16 X 16 Sudoku given enough default values to it.

3. The logic used for solving is same in all languages. The coding part of the logic differs according to languages.

Let us see how the logic works in a language and we can figure it out in other languages.

public static boolean solve(char[] grid, int cell) //This is a recursive function which checks cell by cell for solution.
	   {
		  char[] options = {'0','1','2','3','4','5','6','7','8','9','A','B','C','D','E','F'}; 
	      while (cell < 256 && grid[cell] != '.') //Checks if cell is empty or not.
	         cell++;
	      if(cell == 256)
	         return true;

	      for(int i = 0; i < 16; i++)
	      {
	    	  grid[cell] = options[i];	//Take an option from options array and place it in the cell.
	          if(isColumnValid(grid, cell % 16)) //Now check the column of the cell and if true move forward.
	             if(isRowValid(grid, cell / 16)) //Check the row of the cell and if true check Block
	                if(isBlockValid(grid, cell % 16, cell / 16)) //The corresponding block of the cell.
	                	if(isValid(grid) && solve(grid, cell +1)) //Check if entire grid is valid or not.
	                		return true;
	       }
	      grid[cell] = '.';
	      return false;

This is a recursive solution i.e if the solution for a particular cell satisfies all the required constraints, then we call the solve function recursively with goal of finding solution for the next cell in the sudoku if it is empty. An empty cell is defined by ‘.’.

The main logic is:
1. Check if a cell is empty i.e the value of cell is == ‘.’ . If it is empty, then goto step 2.

2. Change the value of the cell from ‘.’ to a value picked up from options array using the for loop.

3. Now, check if modified grid is valid or not. For grid to be valid, it need to satisfy 3 conditions. Every column, row should have all unique values. No repetition of values in the Block. There are 16 Columns, Rows and Blocks.

4. If changing of a grid value from ‘.’ to an option value violates any of the above three condition then we should return False, and run the for loop over the same cell with value from other option.

5. If a value for a given cell satisfies all condition, then we call solve() method recursively trying to solve next cell.

In order to solve a sudoku in python language, I used process builder to create new process and execute the python command. The solution from python is returned to java as a string.

String[] cmd = new String[3];
cmd[0] = "python";
cmd[1] = "sudoku_solver.py";
cmd[2] = ip;
Process pr = Runtime.getRuntime().exec(cmd);
BufferedReader in = new BufferedReader(new InputStreamReader(pr.getInputStream())); //Gathering the output of the python program into a string
String python_output = in.readLine();

For solving the sudoku in Javascript, there is built in Script class which allow us to call Javascript Engine. Solution is returned to Java from Javascript as a string.

ScriptEngineManager factory = new ScriptEngineManager();//Creating an engine to inovke JavaScriptEngine.						ScriptEngine engine = factory.getEngineByName("JavaScript");						
engine.eval(Files.newBufferedReader(Paths.get("/import/linux/home/adesu1/plprj/sudoku_solver.js"),StandardCharsets.UTF_8));
Invocable inv = (Invocable)engine;
String Js_ret = inv.invokeFunction("solve_JS",ip).toString();

All the source files are here.

Any doubts regarding working it out can be placed in comments section.

Advertisements

About Anuroop D

Very enthusiastic about technology and likes to share my knowledge through blogging. Has Bachelor's in Information Technology and currently pursuing my Master's in Computer Science.
This entry was posted in C, Java, Python and tagged , , , , , , , , , , , , , , . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

w

Connecting to %s