Sign in to follow this  
  • entries
    56
  • comments
    80
  • views
    41568

Sudoku Solver

Sign in to follow this  
bladerunner627

206 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.

Sorry about the lack of comments, and it's overall convoluted self.

SudokuSolver.java

// 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;
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 4
0 4 0 0 0 2 5 0 0
3 7 0 4 0 0 0 0 0
6 3 0 7 9 0 0 0 0
1 0 0 3 0 4 0 0 6
0 0 0 0 1 6 0 4 7
0 0 0 0 0 1 0 6 2
0 0 6 9 0 0 0 8 0
8 0 5 0 6 7 0 9 0





Sign in to follow this  


2 Comments


Recommended Comments

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now