• entries
56
80
• views
41750

# Sudoku Solver

254 views

I was rummaging through some of my projects the other day, and I had completely forgotten about a Sudoku solver I had written in Java back in March.

It wasn't completed due to other projects that took higher priorities, but I feel like I should share it.

I attempted to code it so the puzzle would be solved logically, not brute forced.

It should solve the easier puzzles without a hitch, but it will struggle with harder puzzles. It solves what it can, and if it can't solve anymore it'll just dump the solved portion.

SudokuSolver.java
//	Copyright 2007 Jonathan Bastnagel.//	Created between March 2, 2007 - March 7, 2007import 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;        private int		m_Count = 0;        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;                    }                }            }            for( int i = 0; i < 9; i++ )            {                int numfalse	= 0;                int numtrue		= 0;                int therow		= 0;                int thecolumn	= 0;                for( int row = 0; row < 9; row++ )                {                    for( int column = 0; column < 9; 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;                }            }            for( int i = 0; i < 9; i++ )            {                int numfalse	= 0;                int numtrue     = 0;                int therow	= 0;                int thecolumn	= 0;                for( int column = 0; column < 9; column++ )                {                    for( int row = 0; row < 9; row++ )                    {                        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;                }            }            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_Count++;                    //	System.out.println( "( " + therow + ", " + thecolumn + " ) " + " set to : \'" + (i+1) + "\' using single box elmination." );                    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 = 	"[ This puzzle can't be completely solved logically ]\n";                result +=	"[ The following is what could be solved ]\n";                result += 	PrintResults( ) + "\n";            }            return result;        }    }    public static void main ( String args[] ) //throws Exception    {        System.out.println( "[ Logic Sudoku Solver. ]" );        System.out.println( "[ Won't solve a puzzle if it can't be solved logically ]\n" );        Sudoku test;        test = new Sudoku( "puzzle.sdk" );        test.CompleteSolve( );    }  }

This is how the puzzles are laid out in files.
0's are blank portions in the puzzle.

Puzzle.sdk
0 6 0 1 7 0 2 0 40 4 0 0 0 2 5 0 03 7 0 4 0 0 0 0 06 3 0 7 9 0 0 0 01 0 0 3 0 4 0 0 60 0 0 0 1 6 0 4 70 0 0 0 0 1 0 6 20 0 6 9 0 0 0 8 08 0 5 0 6 7 0 9 0

Seems sweet man, good luck with your current project or something [wink]

Thanks. I've been watching your blog as well, 2D tile based games are always fun :).

You create your own map format?