Thought Process :
I am not a very expert level sudoku solver. So I think I know only the basic rules and the basic methods to solve a Sudoku. Hence in real life I am able to solve the "Easy" levels , struggle with "Medium" and "Hard".
The solution I came up with employs only the basic strategies. The answer given by my algorithm is the max I can go manually. I am not able to solve any more than this algorithm. Others can expand on this and add more functions and strategies.
Code : Class describing each of the block in a Sudoku grid
public class Sudoku {
// 2D array to store the sudoku elements
ArrayList<ArrayList<SudokuBlock>> sb;
// This variable stores the number of unsolved blocks
int unsolved;
public Sudoku(int arr[][]){
// Initialize the sudoku by taking in an array of values
sb = new ArrayList<ArrayList<SudokuBlock>>();
unsolved = 81;
for(int i=0;i<9;i++)
{
ArrayList<SudokuBlock> asb = new ArrayList<SudokuBlock>();
for(int j=0;j<9;j++)
{
if(arr[i][j] != 0){
SudokuBlock sbb = new SudokuBlock(true,arr[i][j]);
asb.add(sbb);
unsolved--;
}
else {
SudokuBlock sbb = new SudokuBlock();
asb.add(sbb);
}
}
sb.add(asb);
}
}
public void print(){
for(int i=0;i<9;i++)
{ if(i>0 && i%3==0) System.out.println("- - - - - - - - - - - -");
for(int j=0;j<9;j++)
{
if(j>0 && j%3==0) System.out.print(" | ");
System.out.print(sb.get(i).get(j).sv+" ");
}
System.out.println();
}
}
public void print(int i, int j){
// Can be used to debug
if(sb.get(i).get(j).isSet)
System.out.print(sb.get(i).get(j).sv+" ");
else
System.out.print(sb.get(i).get(j).sud_values.toString());
}
public void solve(){
// Main function which triggers different algorithms to solve the sudoku
// Check the smaller 3 * 3 blocks and try to fill the values
smallBlock();
// Check the row and column for solved entries and removes them from other blocks Set
inlines();
// Check 3 adjacent rows/columns at a time and attempt to fill values
triples();
// Check to complete a row/column
fillrow();
}
public int unsolved(){
// Calculates the number of unsolved spaces left
unsolved = 81;
for(int i=0;i<9;i++)
for(int j=0;j<9;j++)
if(sb.get(i).get(j).isSet)
unsolved--;
return unsolved;
}
public void fillrow(){
// Check for values to complete a row
for(int i=0;i<9;i++){
for(int j=0;j<9;j++){
if(!sb.get(i).get(j).isSet){
HashSet<Integer> ms = (HashSet<Integer>) sb.get(i).get(j).sud_values.clone();
for(int k=0;k<9;k++){
if(sb.get(i).get(k).isSet && j!=k ){
ms.removeAll(sb.get(i).get(k).sud_values);
}
}
if(ms.size() ==1 && !sb.get(i).get(j).isSet){
sb.get(i).get(j).isSet = true;
sb.get(i).get(j).sv = (Integer) ms.toArray()[0];
solve();
}
}
if(!sb.get(i).get(j).isSet){
// For columns
HashSet<Integer> ms = (HashSet<Integer>) sb.get(i).get(j).sud_values.clone();
for(int k=0;k<9;k++){
if(sb.get(k).get(j).isSet && i!=k ){
ms.removeAll(sb.get(k).get(j).sud_values);
}
}
if(ms.size() ==1 && !sb.get(i).get(j).isSet){
sb.get(i).get(j).isSet = true;
sb.get(i).get(j).sv = (Integer) ms.toArray()[0];
solve();
}
}
}
}
}
public void triples(){
// Check the 3 rows and columns to see if value should be set
//check in the remaining columns in the set
//if exists then check in remaining rows in the set
//if exists then set it !
// Attempt to find the row edges and column edges for a particular block
int row_min=0;
int row_max=0;
int col_min=0;
int col_max=0;
// Dividing up the entire sudoku into 9 3*3 blocks
for(int i=0;i<9;i++){
int cal = i%3;
row_min = (i/3)*3 ;
row_max = row_min + 2;
col_min = cal/3 + cal*3;
col_max = col_min + 2;
for(int a=row_min;a<=row_max;a++)
for(int b=col_min;b<=col_max;b++)
{
if(!sb.get(a).get(b).isSet){
// Not using iterator because we plan to change the values
Object[] it = sb.get(a).get(b).sud_values.toArray();
for(int iti=0;iti< it.length;iti++){
// Variable which holds number of rows/column a particular value occurs
int count_r=0;
int count_c=0;
Integer n = (Integer) it[iti];
for(int k=0;k<9;k++){
if(a!=row_min && n == sb.get(row_min).get(k).sv)
count_r++;
if(a!=(row_min+1) && n == sb.get(row_min+1).get(k).sv)
count_r++;
if(a!=(row_min+2) && n == sb.get(row_min+2).get(k).sv)
count_r++;
if(b!=col_min && n == sb.get(k).get(col_min).sv)
count_c++;
if(b!=(col_min+1) && n == sb.get(k).get(col_min+1).sv)
count_c++;
if(b!=(col_min+2)&& n == sb.get(k).get(col_min+2).sv)
count_c++;
if (count_c ==2 && count_r ==2)
{ sb.get(a).get(b).sv = n;
sb.get(a).get(b).isSet = true;
// Whenever we find a new value, reiterate from the beginning
solve();
}
else if (count_c ==2 && count_r !=2){
int in1, in2;
if(a==row_min)
{in1=row_min+1;in2=row_min+2;}
else if((a==row_min+1)){
in1=row_min;in2=row_min+2;
}
else {
in1=row_min;in2=row_min+1;
}
if(!sb.get(in1).get(b).sud_values.contains(n) && !sb.get(in2).get(b).sud_values.contains(n)){
sb.get(a).get(b).isSet = true;
sb.get(a).get(b).sv = n;
solve();
}
}
else if (count_c !=2 && count_r ==2){
int in1, in2;
if(b==col_min)
{in1=col_min+1;in2=col_min+2;}
else if((b==col_min+1)){
in1=col_min;in2=col_min+2;
}
else {
in1=col_min;in2=col_min+1;
}
if(!sb.get(a).get(in1).sud_values.contains(n) && !sb.get(a).get(in2).sud_values.contains(n)){
sb.get(a).get(b).isSet = true;
sb.get(a).get(b).sv = n;
solve();
}
}
}
}
}
if(sb.get(a).get(b).isSet)
sb.get(a).get(b).sud_values.clear();
}
}
}
public void inlines(){
//Checks if a number exists in the row or column if yes then remove from the set
for(int i=0;i<9;i++){
for(int j=0;j<9;j++){
for(int k=0;k<9;k++){
if(!sb.get(i).get(j).isSet){
sb.get(i).get(j).sud_values.remove(sb.get(i).get(k).sv);
sb.get(i).get(j).sud_values.remove(sb.get(k).get(j).sv);
}
}
if(!sb.get(i).get(j).isSet)
if (sb.get(i).get(j).sud_values.size() == 1)
{
sb.get(i).get(j).sv = (Integer) (sb.get(i).get(j).sud_values.toArray()[0]);
sb.get(i).get(j).isSet = true;
// If any new value is found recurse !
solve();
}
}
}
}
public void smallBlock(){
// Compare with the smaller block and fill possible values
int row_min=0;
int row_max=0;
int col_min=0;
int col_max=0;
for(int i=0;i<9;i++){
HashSet<Integer> hs_np_val = new HashSet<Integer>();
for(int j=1;j<10;j++)
hs_np_val.add(j);
int cal = i%3;
row_min = (i/3)*3 ;
row_max = row_min + 2;
col_min = cal/3 + cal*3;
col_max = col_min + 2;
for(int a=row_min;a<=row_max;a++)
for(int b=col_min;b<=col_max;b++)
{
if(sb.get(a).get(b).isSet){
hs_np_val.remove(sb.get(a).get(b).sv);
}
}
//Fill the blocks with possible values
for(int a=row_min;a<=row_max;a++)
for(int b=col_min;b<=col_max;b++)
if(!sb.get(a).get(b).isSet)
{ //sb.get(a).get(b).sud_values = hs_np_val;
sb.get(a).get(b).sud_values.clear();
sb.get(a).get(b).sud_values.addAll(hs_np_val);
if(sb.get(a).get(b).sud_values.size() ==1){
sb.get(a).get(b).sv = (Integer) (sb.get(a).get(b).sud_values.toArray()[0]);
sb.get(a).get(b).isSet = true;
solve();
}
}
}
}
private class SudokuBlock {
// Variable to hold possible set of values
public HashSet<Integer> sud_values;
// Variable which identifies if the value is found or not
boolean isSet;
// Variable value
public int sv;
public SudokuBlock(){
isSet = false;
sv =0;
sud_values = new HashSet<Integer>();
for(int i=1;i<=9;i++)
sud_values.add(new Integer(i));
}
public SudokuBlock(boolean is, int isv){
isSet = is;
sv =isv;
sud_values = new HashSet<Integer>();
}
}
public static void main(String[] args) {
// TODO Auto-generated method stub
/*
// Easy Level
int arr[][] = {{0,0,0,1,0,5,0,0,0},
{1,4,0,0,0,0,6,7,0},
{0,8,0,0,0,2,4,0,0},
{0,6,3,0,7,0,0,1,0},
{9,0,0,0,0,0,0,0,3},
{0,1,0,0,9,0,5,2,0},
{0,0,7,2,0,0,0,8,0},
{0,2,6,0,0,0,0,3,5},
{0,0,0,4,0,9,0,0,0}};
*/
// Medium
int arr[][] =
{{4,0,0,0,1,0,0,0,0},
{0,0,0,3,0,9,0,4,0},
{0,7,0,0,0,5,0,0,9},
{0,0,0,0,6,0,0,2,1},
{0,0,4,0,7,0,6,0,0},
{1,9,0,0,5,0,0,0,0},
{9,0,0,4,0,0,0,7,0},
{0,3,0,6,0,8,0,0,0},
{0,0,0,0,3,0,0,0,6}};
Sudoku sd = new Sudoku(arr);
System.out.println("Original. Unsolved : "+sd.unsolved());
sd.print();
sd.solve();
System.out.println("After. Unsolved : "+sd.unsolved());
sd.print();
}
}
The code has all the comments included in it ! I don't think it should be hard to decipher that. This code obviously cannot solve all the sudokus. The result of this code is the maximum level I can go manually. I'll hone my own skills and add functions accordingly ! Till then here it is.
