rendered paste body// ©Copyright 2007 Jonathan Bastnagel.
// Created between March 2, 2007 - March 7, 2007
import static java.lang.System.*;
import java.util.Scanner;
import java.util.List;
import java.io.*;
public class SudokuSolver
{
public static class Sudoku
{
private int m_iGrid[ ][ ];
private boolean m_bPossibles[ ][ ][ ];
private boolean m_bSolvable = true;
public Sudoku( String file )
{
m_iGrid = new int[ 9 ][ 9 ];
m_bPossibles = new boolean[ 9 ][ 9 ][ 9 ];
for( int x = 0; x < 9; x++ )
{
for( int y = 0; y < 9; y++ )
{
for( int z = 0; z < 9; z++ )
{
m_bPossibles[ x ][ y ][ z ] = true;
}
}
}
try
{
Scanner fl = new Scanner( new File( file ) );
for( int row = 0; row < 9; row++ )
{
if( fl.hasNext() )
{
for( int column = 0; column < 9; column++ )
{
if( fl.hasNextInt() )
{
m_iGrid[ row ][ column ] = fl.nextInt();
}
}
}
}
}
catch( Exception e )
{
System.out.println( "File not found!" );
}
}
public int Total( )
{
int total = 0;
for( int row = 0; row < 9; row++ )
{
for( int column = 0; column < 9; column++ )
{
total += m_iGrid[ row ][ column ];
}
}
return total;
}
public void CalculatePossibles( )
{
for( int row = 0; row < 9; row++ )
{
for( int column = 0; column < 9; column++ )
{
if( m_iGrid[ row ][ column ] == 0 )
{
for( int x = 0; x < 9; x++ )
{
int number = m_iGrid[ row ][ x ];
if( number != 0 )
{
m_bPossibles[ row ][ column ][ number - 1 ] = false;
}
}
for( int y = 0; y < 9; y++ )
{
int number = m_iGrid[ y ][ column ];
if( number != 0 )
{
m_bPossibles[ row ][ column ][ number - 1 ] = false;
}
}
}
}
}
for( int row = 0; row < 9; row++ )
{
for( int column = 0; column < 9; column++ )
{
int number = m_iGrid[ row ][ column ];
if( number != 0 )
{
for( int i = 0; i < 9; i++ )
{
m_bPossibles[ row ][ column ][ i ] = false;
}
m_bPossibles[ row ][ column ][ number - 1 ] = true;
}
}
}
CalculateBoxPossibles( 0, 3, 0, 3 );
CalculateBoxPossibles( 0, 3, 3, 6 );
CalculateBoxPossibles( 0, 3, 6, 9 );
CalculateBoxPossibles( 3, 6, 0, 3 );
CalculateBoxPossibles( 3, 6, 3, 6 );
CalculateBoxPossibles( 3, 6, 6, 9 );
CalculateBoxPossibles( 6, 9, 0, 3 );
CalculateBoxPossibles( 6, 9, 3, 6 );
CalculateBoxPossibles( 6, 9, 6, 9 );
}
public void CalculateBoxPossibles( int rowstart, int rowend, int columnstart, int columnend )
{
boolean BoxPossibles[ ] = new boolean[ 9 ];
for( int i = 0; i < 9; i++ )
{
BoxPossibles[ i ] = true;
}
for( int row = rowstart; row < rowend; row++ )
{
for( int column = columnstart; column < columnend; column++ )
{
int number = m_iGrid[ row ][ column ];
if ( number != 0 )
{
BoxPossibles [ number - 1 ] = false;
}
}
}
for( int row = rowstart; row < rowend; row++ )
{
for( int column = columnstart; column < columnend; column++ )
{
int number = m_iGrid[ row ][ column ];
if ( number == 0 )
{
for( int i = 0; i < 9; i++ )
{
if( BoxPossibles[ i ] == false )
{
m_bPossibles[ row ][ column ][ i ] = false;
}
}
}
}
}
for( int i = 0; i <9; i++ )
{
int numfalse = 0;
int numtrue = 0;
int therow = 0;
int thecolumn = 0;
for( int row = rowstart; row < rowend; row++ )
{
for( int column = columnstart; column < columnend; column++ )
{
if ( !m_bPossibles[ row ][ column ][ i ] )
{
numfalse++;
}
else
if ( m_bPossibles[ row ][ column ][ i ] )
{
numtrue++;
therow = row;
thecolumn = column;
}
}
}
if( numfalse == 8 && numtrue == 1 && m_iGrid[ therow ][ thecolumn ] == 0 )
{
for( int j = 0; j < 9; j++ )
{
m_bPossibles[ therow ][ thecolumn ][ j ] = false;
}
m_bPossibles[ therow ][ thecolumn ][ i ] = true;
}
}
}
public void PrintPossibles( )
{
for( int x = 0; x < 9; x++ )
{
for( int y = 0; y < 9; y++ )
{
for( int z = 0; z < 9; z++ )
{
System.out.print( m_bPossibles[ x ][ y ][ z ] + "," );
}
System.out.print( " " );
}
System.out.println( );
}
}
public boolean Solve( )
{
int numsolvable = 0;
for( int row = 0; row < 9; row++ )
{
for( int column = 0; column < 9; column++ )
{
if( m_iGrid[ row ][ column ] == 0 )
{
for( int i = 0; i < 9; i++ )
{
int number = GetOnlyTrue( m_bPossibles[ row ][ column ] );
if( number != 0 )
{
m_iGrid[ row ][ column ] = number;
numsolvable++;
}
}
}
}
}
if ( numsolvable == 0 )
{
m_bSolvable = false;
return false;
}
else
{
return true;
}
}
public int GetOnlyTrue( boolean Possibles[ ] )
{
int count = 0;
int num = 0;
for( int i = 0; i < 9; i++ )
{
if ( Possibles[ i ] == true )
{
count++;
num = i + 1;
}
}
if ( count == 1 )
{
return num;
}
else
{
return 0;
}
}
public void CompleteSolve( )
{
while( Total( ) != 405 )
{
CalculatePossibles( );
if( !Solve( ) )
{
break;
}
}
System.out.println( this );
}
public String PrintResults( )
{
String result = "";
for( int row = 0; row < 9; row++ )
{
if( row == 0 || row == 3 || row == 6 )
{
result += "+ - - - + - - - + - - - +\n";
}
for( int column = 0; column < 9; column++)
{
if( column == 0 )
{
result += "|";
}
else
if( column == 3 || column == 6 )
{
result += " |";
}
if( m_iGrid[ row ][ column ] == 0 )
{
result += " " + " ";
}
else
{
result += " " + m_iGrid[ row ][ column ];
}
if( column == 8 )
{
result += " |";
}
}
if( row == 8 )
{
result += "\n+ - - - + - - - + - - - +";
}
result += "\n";
}
return result;
}
public String toString( )
{
String result = "";
if( m_bSolvable )
{
result = "[ Sudoku Puzzle Solved! The following is the solution ]\n";
result += PrintResults( ) + "\n";
}
else
{
result = "[ Cannot solve this puzzle at the moment, as this algorithm is not completely capable. The following is the portion of it that has been solved. ]\n";
result += PrintResults( ) + "\n";
}
return result;
}
}
public static void main ( String args[] ) //throws Exception
{
Sudoku test;
// Beginner
test = new Sudoku( "puzzle.sdk" );
test.CompleteSolve( );
// Intermediate
test = new Sudoku ( "puzzle2.sdk" );
test.CompleteSolve( );
// Advanced
test = new Sudoku ( "puzzle3.sdk" );
test.CompleteSolve( );
// Supreme
// Can't solve :( do supreme puzzles require alot of guessing, and checking?
// I think I'm going to impliment a "brute force" method, which finds the number with the
// least amount of possibles, and plugs one of those numbers in until it works. I think
// that should theoretically work
test = new Sudoku ( "puzzle4.sdk" );
test.CompleteSolve( );
// World's hardest Sudoku Puzzle
test = new Sudoku ( "worldshardestsudokupuzzle.sdk" );
test.CompleteSolve( );
// Another hard one
test = new Sudoku ( "puzzle5.sdk" );
test.CompleteSolve( );;
// Another easy one
test = new Sudoku ( "easiest.sdk" );
test.CompleteSolve( );
test = new Sudoku ( "mypuzzle.sdk" );
test.CompleteSolve( );
}
}