CareerCup

int isValid(int (*sudoku)[SIZE],int row,int col)
{
	int i,j,start_row,start_col;
	// initialise a hash of size 10 with each slot containing 3.

	for(j=0;j<col;j++)
	for(i=0;i<SIZE;i++)// checking each column
		if(hash[sudoku[i][j]]==3)
			hash[sudoku[i][j]]--;
		else return 0;
	
	for(j=0;j<row;j++)		
	for(i=0;i<SIZE;i++)// checkin each row
		if(hash[sudoku[j][i]]==2)
			hash[sudoku[j][i]]--;
		else
			return 0;
		
	return 1;
}

If all the rows & all the columns have been checked for correctnes, then there is no need to check correctness of each grid.

public boolean isValid(int[][] m) {
int[][] t = new int[3][3];
int[] row = new int[10];

for (int i = 0; i < m.length; i++) {
int col = 0;
for (int j = 0; j < m.length; j++) {
/* assert value */
if(m[i][j] < 1 || m[i][j] > 9)
return false;
col += m[i][j];
t[i / 3][j / 3] += m[i][j];
row[i] += m[i][j];
if (col > 45 || t[i / 3][j / 3] > 45 || row[i] > 45)
return false;
}
}
return true;
}

acc. to me a simple soln would be. making a hasmap 9 hashmaps. per row. then 9 hashmaps per column and then 9 hashmaps per block. if we get any hashmap out of 27 hashmaps of those with lenght less than 9. then the soln is wrong. this is of complexity O(n) as no. of elements are 27 and we have 27 insert operations. we are making hashmaps of key as the value in cell and value can be left blank, in python this can also be done with the helps of sets.

boolean isValidAns(int[][] sudoku){
    //Check the correctness for each row and column
    for (int i = 0; i< sudoku.length; i++){
        HashMap<Integer, Boolean> row = new HashMap<Integer,Boolean>();
        HashMap<Integer, Boolean> column = new HashMap<Integer,Boolean>();
        for (int j = 0; j< sudoku.length; j++){
            if( row.get (sudoku[i][j]) | | column.get( sudoku[j][i])){
                  return false;
            }else{ 
                  row.put( sudoku[i][j], true);
                  column.put(sudoku[j][i], true);
           }
        }
    }
   
    return true;
}

A sudoku block can contain numbers from 0 to 9 . Convert all the numbers into bit feilds enable numbers .
1 == 0x0000 0001
2 == 0x0000 0002
3 == 0x0000 0004
.
.
9 == 0x0000 0200

SUM == 0x0000 02FF == ( bit-wise OR every number)

Guarentees uniqueness + FAST !

A simple solution would be
1. Make an array of n+1 size, with all elements initialized to zero
2. Scan first row and for every element, increase its count, then check the array if any element has count!=1, return false. Repeat the same for every row
3. Repeat the same for every column

At the end return true

this could be done without using the extra space as we know the sum of no in rows and columns and the no are also consecutive in rows and column as well as in 3x3 squares.

find the sum of all the rows and columns..and the 3*3 matrix.!
it shud be constant