|
| Source Code to Solve SuDoKu - Java |
| Friday, June 16, 2006 |
Sudoku (Japanese: 数独, sūdoku), also known as Number Place, is a logic-based placement puzzle. The aim of the canonical puzzle is to enter a numerical digit from 1 through 9 in each cell of a 9×9 grid made up of 3×3 subgrids (called "regions"), starting with various digits given in some cells (the "givens"). Each row, column, and region must contain only one instance of each numeral. Completing the puzzle requires patience and logical ability. Although first published in a U. S. puzzle magazine in 1979, Sudoku initially caught on in Japan in 1986 and attained international popularity in 2005.
 Basic SudoKu Image...
To know more about SuDoKu, visit the following link..
http://en.wikipedia.org/wiki/Sudoku
Download API & Java Source code of SuDoKu here...
/******************************************************/
Program to Solve Given Basic SuDoKu
Krishnakanth. S
sonikrishnakanth@gmail.com
/******************************************************/
Output Screen
import java.io.*;
class SuDoku
{
private int numbs[][];
private int numCount[];
private boolean numFlags[];
private static int no_of_iterations=0;
private static BufferedReader br = new BufferedReader( new InputStreamReader( System.in ) );
public String readInput() throws Exception{
String input = new String();
input = br.readLine();
return input;
}
public int getUserInput() throws Exception{
int input;
try{
input = Integer.parseInt( readInput() );
}
catch( Exception e ){
input = -1;
}
return input;
}
public SuDoku(){
numbs = new int[9][9];
numCount = new int[9];
numFlags = new boolean[9];
for( int i=0; i < 9; i++ ){
for( int j=0; j < 9; j++ ){
numbs[i][j] = 0;
}
numCount[i]=0;
numFlags[i] = true;
}
}
private void getNumCount(){
for( int i=0; i < 9; i++ ){
for( int j=0; j < 9; j++ ){
if ( numbs[i][j] != 0 ){
numCount[ numbs[i][j] - 1 ]++;
}
}
}
}
private boolean isSuDokuFilled(){
for( int i=0; i < 9; i++ )
numFlags[i] = true;
for( int i=0; i < 9; i++ ){
for( int j=0; j < 9; j++ ){
if ( numbs[i][j] == 0 )
{
numFlags[i] = false;
}
}
}
for ( int i=0; i < 9; i++ ){
if ( numFlags[i] == false ){
return false;
}
}
return true;
}
private int getHighCountNumber(){
int maxIndex = 0;
int temp=-1;
for( int i=0; i < 9; i++ ){
if( numCount[i] > temp &&amp;amp; numCount[i] != 9 ){
temp = numCount[i];
maxIndex = i;
}
}
return maxIndex;
}
public void fillBox( int i, int j, int value ){
if( !( i>=1 && j>=1) ){
System.out.println( "Invalid Row And Column" );
return;
}
if( value <=0 || value>=10 ){
return;
}
if( numbs[i-1][j-1] != 0 ){
System.out.println( "Previous Value " + numbs[i][j] + " is Replaced By : " + value );
}
numbs[i-1][j-1] = value;
}
public void displaySudo(){
for( int i=0; i < 9; i++ ){
if( i%3 == 0 )
System.out.println();
for( int j=0; j < 9; j++ ){
if( (j%3) == 0 )
System.out.print( "\t" );
System.out.print( numbs[i][j] + " " );
}
System.out.println();
}
}
public int getNoOfIterations(){
return no_of_iterations;
}
public void fillValues( int number ){
no_of_iterations++;
boolean flag = false;
int row=0;
int col=0;
int newRow = 0;
int newCol = 0;
int rowCnt = 0;
int colCnt = 0;
int numsInBoxes[][][] = new int[9][3][3];
int numRows[][] = new int[9][9];
int numColumns[][] = new int[9][9];
boolean numInBox[] = new boolean[9];
boolean numInRow[] = new boolean[9];
boolean numInCol[] = new boolean[9];
for ( int i=0; i < 9; i++ ){
if( i%3 == 0 &&amp;amp; i != 0 ){
row += 3;
col=0;
}
newRow = 0;
newCol = 0;
for( int j=col*3; j < ((col*3)+3); j++ ){
for( int k=row; k < row+3; k++ ){
numsInBoxes[i][newRow++][newCol] = numbs[k][j];
}
newRow = 0;
newCol++;
}
col++;
numInBox[i] = false;
numInRow[i] = false;
numInCol[i] = false;
}
for( int i=0; i < 9; i++ ){
for( int j=0; j < 9; j++ ){
numRows[i][j] = numbs[i][j];
numColumns[j][i] = numbs[j][i];
}
}
for ( int i=0; i < 9; i++ ){
for( int j=0; j < 3; j++ ){
for( int k=0; k < 3; k++ ){
if( numsInBoxes[i][j][k] == number ){
numInBox[i] = true;
}
}
}
}
for( int i=0; i < 9; i++ ){
for( int j=0; j < 9; j++ ){
if( numRows[i][j] == number )
numInRow[i] = true;
}
}
for( int i=0; i < 9; i++ ){
for( int j=0; j < 9; j++ ){
if( numColumns[j][i] == number )
numInCol[i] = true;
}
}
for( int i=0; i < 9; i++ ){
int rowsEmpty[] = new int[9];
int rowIndex = 0;
int colsEmpty[] = new int[9];
int colIndex = 0;
for( int aa=0; aa < 9; aa++ ){
rowsEmpty[aa] = -1;
colsEmpty[aa] = -1;
}
if( numInBox[i] ){
}
else{
for( int ro=0; ro < 3; ro++ ){
for( int co=0; co < 3; co++ ){
if( numsInBoxes[i][ro][co] == 0 ){
int oriRow = ro;
int oriCol = co;
if( i == 3 || i == 4 || i == 5 ){
oriRow += 3;
}
else{
if( i == 6 || i == 7 || i == 8 ){
oriRow += 6;
}
}
if( i == 1 || i == 4 || i == 7 ){
oriCol += 3;
}
if( i == 2 || i == 5 || i == 8 ){
oriCol += 6;
}
rowsEmpty[rowIndex++] = oriRow;
colsEmpty[colIndex++] = oriCol;
}
}
}
for ( int kk=0; kk < rowsEmpty.length; kk++ )
{
if( rowsEmpty[kk] != -1 ){
if( numInRow[ rowsEmpty[kk] ] ){
rowsEmpty[kk] = -1;
colsEmpty[kk] = -1;
}
}
if( colsEmpty[kk] != -1 ){
if( numInCol[ colsEmpty[kk] ] ){
rowsEmpty[kk] = -1;
colsEmpty[kk] = -1;
}
}
}
int count = 0;
int preRow = -1;
int preCol = -1;
for ( int kk=0; kk < rowsEmpty.length; kk++ )
{
if( rowsEmpty[kk] != -1 && colsEmpty[kk] != -1 ){
preRow = rowsEmpty[kk];
preCol = colsEmpty[kk];
count++;
}
}
if( count == 1 )
numbs[preRow][preCol] = number;
}
}
}
public void completeSudoku(){
getNumCount();
while( !isSuDokuFilled() ){
for( int ad=1; ad <=9; ad++ )
fillValues( ad );
if( no_of_iterations >= 1500 ){
System.out.println( "\nIts Very Complicated SuDoKu " );
break;
}
}
}
public static void main(String[] args)
{
SuDoku s = new SuDoku();
int row, col, value;
boolean inputEntry = true;
System.out.println( "Enter the values in Sudoku ,, Format : Row < Enter> Column < Enter> Value < Enter>" );
while( inputEntry ){
try{
System.out.print( "Row : " );
row = s.getUserInput();
System.out.print( "Column : " );
col = s.getUserInput();
System.out.print( "Value : " );
value = s.getUserInput();
if( row >= 1 && row <= 9 &&amp;amp; col >= 1 && col <= 9 &&amp;amp; value >= 1 && value <= 9 )
s.fillBox( row, col, value );
else
System.out.println( "Invalid Entry" );
System.out.print( "Do You Want To Enter More Elements (Y/N) : " );
String choice = s.readInput();
if( choice.startsWith( "n" ) || choice.startsWith( "N" ) )
inputEntry = false;
}catch( Exception e ){}
}
String clear = "\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n";
System.out.println( clear );
System.out.println( "\n\n\tQuestion ??? " );
s.displaySudo();
s.completeSudoku();
if( !(s.getNoOfIterations() >= 1500) ){
System.out.println( "\nRequired " + s.getNoOfIterations() + " Iterations to Solve \n\n" );
System.out.println( "\tSolution " );
s.displaySudo();
}
}
}
|
posted by Zaara @ 11:43 AM 
|
|
|
|
|
|
