ISourceCode

Make the frequent cases fast and the rare case correct

Special case of Latin square – Sudoku

Sudoku is the most well known puzzle.

Previously i wrote the article about LATIN SQUARE . A Latin square is an n × n array filled with n different Latin letters, each occurring exactly once in each row and exactly once in each column. Sudoku is a special case of a latin square where we try to satisfy an additional condition where each 3×3 sub squares must contain all the 9 numbers.

The input for the below code is solved here ( flash simulation).

import java.io.*;
public class sudoku
{
	public static void main(String[] args) throws IOException
 	{
		int[][] matrix=new int[9][9];		
		System.out.println("Enter the 9x9 sudoku puzzle with a blank represented by 0");  		
		InputStreamReader input=new InputStreamReader(System.in);
  		BufferedReader in=new BufferedReader(input);
    		
   		for(int i=0;i< 9;i++)
   		{
			for(int j=0;j< 9;j++)
          			matrix[i][j]=in.read()-'0';
        		in.readLine();
   		}
   		sudoku(0,0,matrix);
		System.out.println("The Soved puzzle is");
   		for(int i=0;i< 9;i++)
   		{
     			for(int j=0;j< 9;j++)
				System.out.print(matrix[i][j]+" ");
     			System.out.println();
    		}
   
  	}

  	public static boolean sudoku(int x,int y,int[][] matrix)
  	{
		int[] solution=new int[10];   		
		if(y>8)
    		{
			x++;
			y=0;
			if(x>8) return true;
    		}
    		if(matrix[x][y]!=0)return sudoku(x,y+1,matrix);
    		
    		for(int k=0;k< 9;k++)
    		{
			solution[matrix[x][k]]++;
			solution[matrix[k][y]]++;
    		}
    		int row=x/3,col=y/3;
    		for(int k=row*3;k<row*3+3;k++)
			for(int h=col*3;h<col*3+3;h++)
	   			solution[matrix[k][h]]++;
    		for(int k=1;k<10;k++)
    		{
			if(solution[k]!=0) continue;
			matrix[x][y]=k;
			if(sudoku(x,y+1,matrix)) return true;
    		}
    		matrix[x][y]=0;
    		return false;
   	}
}

OUTPUT:

labuser@ubuntu:~$ java sudoku
Enter the 9×9 sudoku puzzle with a blank represented by 0
002090060
040001008
070420003
500000300
001060500
003000006
100057040
600900020
020080100
The Soved puzzle is
3 1 2 5 9 8 7 6 4
9 4 6 7 3 1 2 5 8
8 7 5 4 2 6 9 1 3
5 6 7 8 4 2 3 9 1
4 8 1 3 6 9 5 7 2
2 9 3 1 7 5 4 8 6
1 3 8 2 5 7 6 4 9
6 5 4 9 1 3 8 2 7
7 2 9 6 8 4 1 3 5

It Would be interesting to solve the sudoku for different dimension matrix

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 )

Twitter picture

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

Facebook photo

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

Google+ photo

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

Connecting to %s

%d bloggers like this: