//	©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( );
	}  
}