Sudoku
UK newspapers are awash with Sudoku, a number puzzle. My paper carried this puzzle today:
You have to fill in the blanks so that the numbers 1 to 9 appear once in each row, once in each column and once in each 3x3 square. You're meant to solve it by brain power, but I get bored too quickly. Writing Java code keeps my attention, though. I'm sure that what I did it could be improved in any number of ways, but it finds the solution pretty quickly by brute force (i.e. lots of guessing).
|
|
|
|||||||||||||||||||||||||||
|
|
|
|||||||||||||||||||||||||||
|
|
|
You have to fill in the blanks so that the numbers 1 to 9 appear once in each row, once in each column and once in each 3x3 square. You're meant to solve it by brain power, but I get bored too quickly. Writing Java code keeps my attention, though. I'm sure that what I did it could be improved in any number of ways, but it finds the solution pretty quickly by brute force (i.e. lots of guessing).
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Date;
/**
* The general approach here is:
* <pre>
* writeIn ( grid, x, y ) : grid
* return a new grid
*
* findBlank ( grid ) : position
* for x = 1 to 9
* for y = 1 to 9
* if grid ( x, y ) is empty
* return ( x, y )
* return null
*
* guess ( grid ) : bool
* pos = findBlank ( grid )
* for i = 1 to 9
* newGrid = writeIn ( grid, pos, i )
* if valid ( newGrid )
* if null == findBlank ( newGrid )
* print newGrid
* return true
* else if guess ( newGrid )
* return true
* return false
* </pre>
*/
public class Sudoku
{
private static final int [] ROW = { -1, -1, -1, -1, -1, -1, -1, -1, -1, };
private static int guessCount = 0;
private static boolean chatty = false;
private static boolean verbose = false;
private static class Grid
implements Cloneable
{
public final int [][] rows = new int [ 9 ][];
{
for ( int row = 0; row < 9; row++ )
{
rows [ row ] = ( int [] ) ROW.clone ();
}
}
int get ( final Position pos )
{
return rows [ pos.x ][ pos.y ];
}
Grid set ( final Position pos, final int i )
{
rows [ pos.x ][ pos.y ] = i;
return this;
}
protected Object clone ()
{
final Grid result = new Grid ();
for ( int x = 0; x < 9; x++ )
{
for ( int y = 0; y < 9; y++ )
{
result.rows [ x ][ y ] = rows [ x ][ y ];
}
}
return result;
}
}
private static class Position
{
final int x;
final int y;
Position ( final int x, final int y )
{
this.x = x;
this.y = y;
}
public String toString ()
{
return "(" + x + ',' + y + ')';
}
}
private static Grid writeIn ( final Grid grid, final Position pos, final int i )
{
return ( ( Grid ) grid.clone () ).set ( pos, i );
}
private static Position findBlank ( final Grid grid )
{
for ( int x = 0; x < 9; x++ )
{
for ( int y = 0; y < 9; y++ )
{
final Position pos = new Position ( x, y );
if ( grid.get ( pos ) == -1 )
{
return pos;
}
}
}
return null;
}
private static void print ( final Grid grid )
{
System.out.println ();
for ( int y = 0; y < 9; y++ )
{
System.out.println ( y%3 == 0 ? "+=+=+=+=+=+=+=+=+=+" : "+-+-+-+-+-+-+-+-+-+" );
for ( int x = 0; x < 9; x++ )
{
final int i = grid.get ( new Position ( x, y ) );
final String s = x%3 == 0 ? "|" : ":";
System.out.print ( -1 == i ? s + " " : s + i );
}
System.out.println ( '|' );
}
System.out.println ( "+=+=+=+=+=+=+=+=+=+" );
}
private static boolean valid ( final Grid grid )
{
int flags = 0;
// Columns
if ( verbose ) System.out.println ( "Checking columns..." );
for ( int x = 0; x < 9; x++ )
{
flags = 0;
for ( int y = 0; y < 9; y++ )
{
if ( verbose ) System.out.println ( "" + ( ( flags & 1 ) == 0 ? 0 : 1 ) + ( ( flags & 2 ) == 0 ? 0 : 1 ) + ( ( flags & 4 ) == 0 ? 0 : 1 ) + ( ( flags & 8 ) == 0 ? 0 : 1 ) + ( ( flags & 16 ) == 0 ? 0 : 1 ) + ( ( flags & 32 ) == 0 ? 0 : 1 ) + ( ( flags & 64 ) == 0 ? 0 : 1 ) + ( ( flags & 128 ) == 0 ? 0 : 1 ) + ( ( flags & 256 ) == 0 ? 0 : 1 ) );
flags = checkPosition ( flags, grid.get ( new Position ( x, y ) ) );
if ( -1 == flags )
{
return false;
}
}
}
// Rows
if ( verbose ) System.out.println ( "Checking rows..." );
for ( int y = 0; y < 9; y++ )
{
flags = 0;
for ( int x = 0; x < 9; x++ )
{
if ( verbose ) System.out.println ( "" + ( ( flags & 1 ) == 0 ? 0 : 1 ) + ( ( flags & 2 ) == 0 ? 0 : 1 ) + ( ( flags & 4 ) == 0 ? 0 : 1 ) + ( ( flags & 8 ) == 0 ? 0 : 1 ) + ( ( flags & 16 ) == 0 ? 0 : 1 ) + ( ( flags & 32 ) == 0 ? 0 : 1 ) + ( ( flags & 64 ) == 0 ? 0 : 1 ) + ( ( flags & 128 ) == 0 ? 0 : 1 ) + ( ( flags & 256 ) == 0 ? 0 : 1 ) );
flags = checkPosition ( flags, grid.get ( new Position ( x, y ) ) );
if ( -1 == flags )
{
return false;
}
}
}
// Squares
if ( verbose ) System.out.println ( "Checking squares..." );
for ( int x2 = 0; x2 < 3; x2++ )
{
for ( int y2 = 0; y2 < 3; y2++ )
{
flags = 0;
for ( int x = 0 + 3*x2; x < 3*x2 + 3; x++ )
{
for ( int y = 0 + 3*y2; y < 3*y2 + 3; y++ )
{
if ( verbose ) System.out.println ( new Position ( x, y ).toString () + ": " + ( ( flags & 1 ) == 0 ? 0 : 1 ) + ( ( flags & 2 ) == 0 ? 0 : 1 ) + ( ( flags & 4 ) == 0 ? 0 : 1 ) + ( ( flags & 8 ) == 0 ? 0 : 1 ) + ( ( flags & 16 ) == 0 ? 0 : 1 ) + ( ( flags & 32 ) == 0 ? 0 : 1 ) + ( ( flags & 64 ) == 0 ? 0 : 1 ) + ( ( flags & 128 ) == 0 ? 0 : 1 ) + ( ( flags & 256 ) == 0 ? 0 : 1 ) );
flags = checkPosition ( flags, grid.get ( new Position ( x, y ) ) );
if ( -1 == flags )
{
return false;
}
}
}
}
}
return true;
}
private static int checkPosition ( final int flags, final int value )
{
int result = flags;
switch ( value )
{
case 1:
if ( 0 != ( result & 1 ) )
{
return -1;
}
result |= 1;
break;
case 2:
if ( 0 != ( result & 2 ) )
{
return -1;
}
result |= 2;
break;
case 3:
if ( 0 != ( result & 4 ) )
{
return -1;
}
result |= 4;
break;
case 4:
if ( 0 != ( result & 8 ) )
{
return -1;
}
result |= 8;
break;
case 5:
if ( 0 != ( result & 16 ) )
{
return -1;
}
result |= 16;
break;
case 6:
if ( 0 != ( result & 32 ) )
{
return -1;
}
result |= 32;
break;
case 7:
if ( 0 != ( result & 64 ) )
{
return -1;
}
result |= 64;
break;
case 8:
if ( 0 != ( result & 128 ) )
{
return -1;
}
result |= 128;
break;
case 9:
if ( 0 != ( result & 256 ) )
{
return -1;
}
result |= 256;
break;
}
return result;
}
private static boolean guess ( final Grid grid )
{
final Position pos = findBlank ( grid );
guessCount++;
if ( chatty ) System.out.print ( '.' );
if ( verbose ) System.out.println ( "Guessing on grid " + grid + ", found blank at " + pos );
for ( int i = 1; i <= 9; i++ )
{
final Grid newGrid = writeIn ( grid, pos, i );
if ( verbose ) System.out.println ( "Trying " + i + " at " + pos + " on " + newGrid + " derived from " + grid + ':' );
if ( verbose ) print ( newGrid );
if ( valid ( newGrid ) )
{
if ( null == findBlank ( newGrid ) )
{
print ( newGrid );
if ( chatty ) System.out.println ( "Guesses: " + guessCount );
return true;
}
else if ( guess ( newGrid ) )
{
return true;
}
}
}
return false;
}
public static void main ( final String [] args )
throws Exception // lazy programmer
{
final BufferedReader br = new BufferedReader ( new InputStreamReader ( System.in ) );
int rowCount = 0;
final Grid grid = new Grid ();
boolean timing = false;
for ( int i = 0; i < args.length; i++ )
{
if ( "-h".equals ( args [ i ] ) )
{
System.out.println ( "Sudoku solver" );
System.out.println ( "~~~~~~~~~~~~~" );
System.out.println ();
System.out.println ( "Syntax: java Sudoku [-t] [-c|-v]" );
System.out.println ( "Options: -c chatty - lots of output" );
System.out.println ( " -v verbose - humungous amounts of output" );
System.out.println ();
System.exit ( 0 );
}
if ( "-t".equals ( args [ i ] ) )
{
timing = true;
}
if ( "-c".equals ( args [ i ] ) )
{
chatty = true;
}
else if ( "-v".equals ( args [ i ] ) )
{
chatty = true;
verbose = true;
}
}
System.out.println ( "Enter the numbers one line at a time, with no gaps, but spaces for the blanks." );
while ( rowCount < 9 )
{
final String line;
rowCount++;
System.out.print ( "Row " + rowCount + ": " );
line = br.readLine ();
if ( line.length () != 9 )
{
System.out.println ( "You must enter nine characters per row. Please try this row again." );
rowCount--;
continue;
}
for ( int i = 0; i < 9; i++ )
{
final char c = line.charAt ( i );
switch ( c )
{
case '1':
case '2':
case '3':
case '4':
case '5':
case '6':
case '7':
case '8':
case '9':
grid.set ( new Position ( i, rowCount - 1 ), Character.digit ( c, 10 ) );
break;
case ' ':
// Do nothing
break;
default:
System.out.println ( "You must enter only numbers and spaces. Please try this row again." );
rowCount--;
continue;
}
}
if ( rowCount == 9 )
{
final String answer;
System.out.println ();
print ( grid );
System.out.println ();
System.out.print ( "Is this grid correct? [yes, no, exit] " );
answer = br.readLine ().toLowerCase ();
if ( "yes".equals ( answer) || "y".equals ( answer) )
{
final Date start = new Date ();
if ( ! guess ( grid ) )
{
System.out.println ( "No solution found!" );
}
if ( timing )
{
final long millis = new Date ().getTime () - start.getTime ();
System.out.println ( "Time taken: " + millis );
}
}
else if ( "no".equals ( answer) || "n".equals ( answer) )
{
rowCount = 0;
}
}
}
}
}You should be able to paste the code into Sudoku.java, compile and run.Curiously, the puzzle above took more guesses than any other I've tried, but wasn't rated by the newspaper at the hardest difficulty level.
Even more curiously, the compiler produces an anonymous inner class file (Sudoku$1.class) which I can't tie to any part of my code, and which doesn't seem to be required at run time (because if I delete it, nothing goes wrong).
