Google Interview Question Software Engineer / Developers
0of 0 votesWrite a function to validate a SuDoKu board.
#define CSUM 45
#define CPROD 362880
bool ValidateBoard(int a[9][9])
{
int i,j;
int Tsum, Tprod;
// Checking rows
for (i=0;i<9;i++)
{
Tsum = 0, Tprod = 1;
for (j=0;j<9;j++)
{
Tsum += a[i][j];
Tprod *= a[i][j];
}
if (Tsum != CSUM || Tprod != CPROD)
return false;
}
// Checking columns
for (j=0;j<9;j++)
{
Tsum = 0, Tprod = 1;
for (i=0;i<9;i++)
{
Tsum += a[i][j];
Tprod *= a[i][j];
}
if (Tsum != CSUM || Tprod != CPROD)
return false;
}
// Checking boxes
// Even with 4 nested loops, its O(n^2)
int m,n;
for (i=0;i<9;i+=3)
{
for (j=0;j<9;j+=3)
{
Tsum = 0, Tprod = 1;
for (m=i;m<i+3;m++)
{
for (n=j;n<j+3;n++)
{
Tsum += a[m][n];
Tprod *= a[m][n];
}
}
if (Tsum != CSUM || Tprod != CPROD)
return false;
}
}
return true;
}
Is it really needed to check the sum of each row and each column? Checking for presence of each number from 1 to 9 in each row/column should do i believe because if that is present sum will be correct
How can we prove that if a sequence of n numbers has a sum = n * (n - 1)/2 and product is n! then the sequence contains all unique numbers from { 1, 2, ... ,n}
That's exactly what I am doing... In single iteration, I am computing both the sum and product... Now if all the numbers from 1 to 9 are present without any duplicates, the sum and product will come out to be as CSUM and CPROD... this is just a easy way to check the conditions for the sudoku board...
No
The following sequence's sum is also 45 but the sequence is incorrect
1 1 3 4 5 6 7 9 9
Only when both sum and product match, we can say that we have the correct set of numbers.
get the sum =n(n+1)/2.. and then get row and col. item from the board, and subtract from this sum.. if the sum is not zero at any moment.. then the board is invalid.This should do it...
I don't see the importance of checking the product of the numbers??
Hold on a second, are you sure sum and product are enough to assure a permutation of 1 ... 9? I don't think so.
Here's a counter-example (and the only one I believe):
1,2,4,4,4,5,7,9,9
Having said that, there's a much simpler way to compute whether each digit from [1...9] is present:
bool checkDigits(int a[9]) {
int bitset = 0;
for (int i = 0; i < 9; i++) {
assert((1 <= a[i]) && (a[i] <= 9));
bitset |= (1 << (a[i]-1));
}
// true if 1's in rightmost 9 bits
return (bitset == 0x1ff);
}
Another point is that your code is too repetitive. You should consider making the check of 9 digits a function (like checkDigit()) you can call for row, column and boxes rather than repeating the same check everywhere.
After some work, I can produce a configuration that won't fail under sum and product check of all rows, columns and subsquares:
124549497
549497124
497124549
245494971
494971245
971245494
454949712
949712454
712454949
You can verify that all rows, columns and subsquares have sum 45 and product 362880.
In Ruby, heavily relies on sets. Doesn't add up any rows, columns, or subsquares. It checks if each row, column and subsquare is same as the set
<1,2,3,4,5,6,7,8,9>
require 'set'
class SudokuValidator
def initialize(board)
@board = board
@all_numbers = (1..9).to_set
end
def valid?()
return (1..9).all? do |n|
subsquare_valid?(n) and row_valid?(n) and column_valid?(n)
end
end
# check if nth sub-square contains 1..9
def subsquare_valid?(nth)
subsquare(nth) == @all_numbers
end
# check if nth row is valid
def row_valid?(nth)
row(nth) == @all_numbers
end
# check if nth column is valid
def column_valid?(nth)
column(nth) == @all_numbers
end
# return the nth subsquare as an array
def subsquare(nth)
start_row = ((nth - 1)/ 3) * 3
end_row = start_row + 2
start_col = (nth - 1) % 3
end_col = start_col + 2
@board[start_row..end_row].map { |row| row[start_col..end_col] }.flatten.to_set
end
# return the nth row as an array
def row(nth)
@board[nth - 1]
end
# return the nth column as an array
def column(nth)
@board.transpose[nth - 1]
end
end
Editing doesn't work here.. repasting:
require 'set'
class SudokuValidator
def initialize(board)
@board = board
@all_numbers = (1..9).to_set
end
def valid?()
return (1..9).all? do |n|
subsquare_valid?(n) and row_valid?(n) and column_valid?(n)
end
end
# check if nth sub-square contains 1..9
def subsquare_valid?(nth)
subsquare(nth) == @all_numbers
end
# check if nth row is valid
def row_valid?(nth)
row(nth) == @all_numbers
end
# check if nth column is valid
def column_valid?(nth)
column(nth) == @all_numbers
end
# return the nth subsquare as an array
def subsquare(nth)
start_row = ((nth - 1)/ 3) * 3
end_row = start_row + 2
start_col = (nth - 1) % 3
end_col = start_col + 2
@board[start_row..end_row].map { |row| row[start_col..end_col] }.flatten.to_set
end
# return the nth row as an array
def row(nth)
@board[nth - 1]
end
# return the nth column as an array
def column(nth)
@board.transpose[nth - 1]
end
end
maintain hashtables for :
1. each row
2. each coloumn
3. each 3X3 boxes.
now parse as:
for(int i=0;i<m;i++)
{ for(int j=0;j<n;j++)
{ check a[i][j] in its corresponding row_hash, col_hash, and 3X3_hash.
if any of these hash finds it then return false.
else insert it into the hash.
}
}
order will be O(m*n). guess this will be fast enough.
boolean validateSUDOKU(int[][] board, int row, int col ) {
for (int i = 0; i < 9; i++) {
if (i != col && board[row][i] == board[row][col]) {
return false;
}
if (i != row && board[i][col] == board[row][col]) {
return false;
}
}
int r = row - row%3;
int c = col - col%3;
int temp = c;
for (int i = 0; i < 3; i++, r++) {
for (int j = 0; j < 3; j++, temp++) {
if(r != row && temp != col && board[r][temp] == board[row][col]) {
return false;
}
}
temp = c;
}
return true;
}
boolean validateSUDOKU(int[][] board, int row, int col ) {
for (int i = 0; i < 9; i++) {
if (i != col && board[row][i] == board[row][col]) {
return false;
}
if (i != row && board[i][col] == board[row][col]) {
return false;
}
}
int r = row - row%3;
int c = col - col%3;
int temp = c;
for (int i = 0; i < 3; i++, r++) {
for (int j = 0; j < 3; j++, temp++) {
if(r != row && temp != col && board[r][temp] == board[row][col]) {
return false;
}
}
temp = c;
}
return true;
}
boolean validateSUDOKU(int[][] board, int row, int col ) {
for (int i = 0; i < 9; i++) {
if (i != col && board[row][i] == board[row][col]) {
return false;
}
if (i != row && board[i][col] == board[row][col]) {
return false;
}
}
int r = row - row%3;
int c = col - col%3;
int temp = c;
for (int i = 0; i < 3; i++, r++) {
for (int j = 0; j < 3; j++, temp++) {
if(r != row && temp != col && board[r][temp] == board[row][col]) {
return false;
}
}
temp = c;
}
return true;
}
boolean validateSUDOKU(int[][] board, int row, int col ) {
for (int i = 0; i < 9; i++) {
if (i != col && board[row][i] == board[row][col]) {
return false;
}
if (i != row && board[i][col] == board[row][col]) {
return false;
}
}
int r = row - row%3;
int c = col - col%3;
int temp = c;
for (int i = 0; i < 3; i++, r++) {
for (int j = 0; j < 3; j++, temp++) {
if(r != row && temp != col && board[r][temp] == board[row][col]) {
return false;
}
}
temp = c;
}
return true;
}
I think the sum and product method should work. Because if by any chance for a particular row(or column) the sum comes out to be n*(n+1)/2 and product comes out to be n!, for an illegal sequence of digits, then for sure that error will be reflected while computing the same for the coulmn(or row) of the respective numbers.
I think that should work.
Correct me If I am wrong.
You may be right but finding an error now becomes a more global problem than just checking a single row, column or sub-square. At an intermediate configuration where not all of the cells are filled, the user might have made an error that can only be discovered at a much later stage, thereby wasting a lot of the user's time in working on an illegal configuration. So it is far better if the error can be detected within a row, column or sub-square.
Besides, there is a much clearer and time and space efficient way to check for permutations on 9 letter by using a length-9 bitset. See my solution above for the C code.
In fact, after some work, I can produce a configuration that won't fail under sum and product check of all rows, columns and subsquares:
124549497
549497124
497124549
245494971
494971245
971245494
454949712
949712454
712454949
You can verify that all rows, columns and subsquares have sum 45 and product 362880.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Sudoku {
private static int [][] matrix = new int[9][9];
private static int [] P = {0,2,3,5,7,11,13,17,19,23};
private static int hashValue ;
public static void main(String [] args) throws IOException {
readInput();
printMatrix();
calcHashValue();
System.out.println("is sudoku right? " + verifySudoku());
}
public static boolean verifySudoku() {
if (!verifySudokuRows()) {
return false;
}
if (!verifySudokuCols()) {
return false;
}
if (!verifySudokuGrids()) {
return false;
}
return true;
}
public static boolean verifySudokuGrids() {
int [] rows = {0,3,6};
int [] cols = {0,3,6};
int gridSize = 3;
for (int i=0; i<rows.length; i++) {
for (int j=0; j<cols.length; j++) {
int hash = 1;
for (int x=rows[i]; x<rows[i]+gridSize; x++) {
for (int y=cols[j]; y<cols[j]+gridSize; y++) {
hash = hash*P[matrix[x][y]];
}
}
System.out.println("Grid : " + hash);
if (hash != hashValue) { return false; }
}
}
return true;
}
public static boolean verifySudokuCols() {
int row = matrix.length;
int col = matrix[0].length;
for (int i=0; i<col; i++) {
int hash = 1;
for (int j=0; j<row; j++) {
hash = hash*P[matrix[i][j]];
}
if (hash != hashValue) {
return false;
}
}
return true;
}
public static boolean verifySudokuRows() {
int row = matrix.length;
int col = matrix[0].length;
for (int i=0; i<row; i++) {
int hash = 1;
for (int j=0; j<col; j++) {
hash = hash*P[matrix[i][j]];
}
if (hash != hashValue) {
return false;
}
}
return true;
}
public static void calcHashValue() {
int len = P.length;
int sum = 1;
for (int i=1; i<len; i++) {
sum = sum * P[i];
}
hashValue = sum;
System.out.println("Hash value: " + hashValue);
}
public static void printMatrix() {
int row = matrix.length;
int col = matrix[0].length;
System.out.println("printing the sudoku data: ");
for (int i=0; i<row; i++) {
for (int j=0; j<col; j++) {
System.out.print(matrix[i][j] + " ");
}
System.out.println();
}
}
public static void readInput() throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = 9;
int r = 0;
while (n > 0) {
String [] str = br.readLine().split(" ");
int len = str.length;
for (int i=0; i<len; i++) {
matrix[r][i] = Integer.parseInt(str[i]);
}
++r;
--n;
}
}
}
I honestly don't understand why people like to do things the hard way. If you look through this thread there is a 9-line way to do this which is a lot more efficient than fooling around with prime numbers.
18 int main()
19 {
20 int i;
21 int row[9];
22 int col[9];
23 // algo goes here.
24 int arr[9][9];
25 for( i =0; i <9 ; i++)
26 {
27 memset(row, 9* sizeof(int), 0);
28 memset(col, 9* sizeof(int), 0);
29 memset(box, 9* sizeof(int), 0);
30 for( j =0; j < 9; j++)
31 {
32 box_i = ((i/3)*3) + (j%3);
33 box_j = ((i*3)%9) + (j%3);
34 if( (row[ arr[j][i] ] != 0) || (col[ arr[i][j] ] != 0) || (box[ arr[box_i][box_j] ] != 0))
35 return 1;
36 else
37 row[ arr[j][i] ] = col[ arr[i][j] ] = box[ arr[box_i][box_j] ] = 1;
38 }
39 }
40 return 0;
41 }
This works fine for me:
public static boolean verifyBoard(int board[][]){
int n = board.length;
int sumOfPositions[] = new int[n+1];
sumOfPositions[0]=0;
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
int value = i+j+2;
sumOfPositions[board[i][j]]+=value;
}
}
int expectedSum = (n*(n+1));
for(int i=1;i<sumOfPositions.length;i++){
if(sumOfPositions[i]!=expectedSum)
return false;
}
return true;
}
is there more efficient way to do this..
- Aditya June 09, 2010import java.io.BufferedReader; import java.io.File; import java.io.FileReader; import java.text.DecimalFormat; public class SudokuValidator { public static void main(String args[]){ int[][] matrix= new int[9][9]; try{ File f = new File("C:\\input.txt"); BufferedReader br = new BufferedReader(new FileReader(f)); String s = br.readLine(); int row=0; while(s!=null&&row<9){ for(int i=0;i<9;i++){ matrix[row][i] = Integer.parseInt(""+ s.charAt(i)); } row++; s=br.readLine(); } System.out.println(validate(matrix)); }catch(Exception ex){ System.out.println("Program failed due to : "+ ex.getMessage()); } } public static boolean validate(int[][] matrix){ double rowSum=0; double colSum=0; int j=0; double sum=0.123456789; DecimalFormat nineDForm = new DecimalFormat("#.#########"); //row and column validation. for(int i=0;i<9;i++){ rowSum=0; colSum=0; for(j=0;j<9;j++){ if(!(matrix[i][j]<10&& matrix[i][j]>=1)){ System.out.println("i= " + i+ "j = "+ j + " matrix[i][j] = "+ matrix[i][j]); return false; } rowSum=rowSum+(matrix[i][j]/Math.pow(10,matrix[i][j])); colSum=colSum+(matrix[j][i]/Math.pow(10,matrix[j][i])); } if(Double.valueOf(nineDForm.format(rowSum))!=sum || Double.valueOf(nineDForm.format(colSum))!=sum) { System.out.println("i= " + i+ "j = "+ j + " rowSum = "+ Double.valueOf(nineDForm.format(rowSum)) + " colSum = " + Double.valueOf(nineDForm.format(colSum))); return false; } } //3*3 matrix validation int rowIndex=0,colIndex=0; double matSum=0; for(int i=0;i<9&&rowIndex<9;i++){ matSum=0; for(int k=rowIndex;k<rowIndex+3;k++){ for(int l=colIndex;l<colIndex+3;l++){ matSum=matSum+(matrix[k][l]/Math.pow(10,matrix[k][l])); } } if(Double.valueOf(nineDForm.format(matSum))!=sum) { System.out.println("rowIndex= " + rowIndex+ "colIndex = "+ colIndex + " matSum = "+ Double.valueOf(nineDForm.format(matSum))); return false; } colIndex=colIndex+3; if(colIndex==9) { colIndex=0; rowIndex=rowIndex+3; } } return true; } }