import java.util.*;
import java.io.*;
public class Sudoku
{
public static int count = 0;
public static int[][] a =
{
{1,0,0,0,0,7,0,9,0},
{0,3,0,0,2,0,0,0,8},
{0,0,9,6,0,0,5,0,0},
{0,0,5,3,0,0,9,0,0},
{0,1,0,0,8,0,0,0,2},
{6,0,0,0,0,4,0,0,0},
{3,0,0,0,0,0,0,1,0},
{0,4,0,0,0,0,0,0,7},
{0,0,7,0,0,0,3,0,0}
};
public static void main(String args[])
{
for(int k=0; k<9; k++)
{
for (int j=0; j<9; j++)
System.out.print(a[k][j]);
System.out.println();
}
System.out.println("Here is the solution");
// for(int i=0; i<9; i++)
// {System.out.println("row "+i);
// for (int j=0; j<9; j++)
// { System.out.println("input next int, zero for blank");
// Scanner t = new Scanner(System.in);
// a[i][j] = t.nextInt();
// }
// }
if (solve(0,0))
{
for(int k=0; k<9; k++)
{
for (int j=0; j<9; j++)
System.out.print(a[k][j]);
System.out.println();
}
System.out.println("Number of Attempts is " + count);
}
else
System.out.println("No Solutions");
}
public static boolean solve(int r, int c)
{ if (r == 9) return true;
if (a[r][c] == 0)
{
for (int i =1; i<=9; i++)
if ( checkr(i,r,c) && checkc(i,r,c) && checks(i,r,c) )
{
a[r][c] = i; count++;
// System.out.println (r + " " + c + " "+ a[r][c]);
if (solve(nextrow(r,c), nextcol(r,c))) return true;
}
a[r][c]=0; // count++; System.out.println (r + " " + c + " "+ a[r][c]);
return false;
}
else
return (solve(nextrow(r,c),nextcol(r,c)));
}
public static int nextrow(int row,int column)
{
if (column < 8) return row; else return row+1;
}
public static int nextcol(int row,int column)
{
if (column < 8) return column+1; else return 0;
}
public static boolean checkr(int num, int row, int column)
{boolean out = true;
for (int i=0; i<9; i++)
if ((num == a[row][i]) && (i != column)) return(false);
return out;
}
public static boolean checkc(int num, int row, int column)
{boolean out = true;
for (int i=0; i<9; i++)
if ((num == a[i][column]) && (i != row)) return(false);
return out;
}
public static boolean checks(int num, int row, int column)
{boolean out = true;
int sr = (row/3)*3; // find row of containing 3x3
int sc = (column/3)*3;
for (int i=sr; i<sr+3; i++)
for (int j=sc; j<sc+3;j++)
if ((num == a[i][j]) && (i != row) && (j != column)) return(false);
// Illegal for a number to appear twice in same subbox
// Since we already performed checkr and checkc via short-circuit, it is enough to check only (row,column) pairs
// that are not in "row" and not in "colummn", that is, && (i != row) && (j != column)
// Note that && ((i != row) || (j != column)) works as well
return out;
}
}