I have got a couple of interviews this week, which I love preparing for as it a good way to refresh my C++ and at the same time, I get to implement some pretty interesting algorithms.
As most of us would do, I have been searching for the past few days about frequently asked interview questions and have been trying to solve most of the algorithm design questions myself. This post is about an interview question asked by google interviewers for an internship position. The question is about checking if a Sudoku Solution is correct or not.
Here is my attempt, which took me around 10 mins (its not that hard if you know how sudoku works). I have tried to greatly reduce the computational complexity of this algorithm by utilizing booleans and taking the advantage of a repetitive pattern in all the rows, columns and 3x3 boxes.
#include <iostream>
using namespace std;
int sud[9][9] ={ {4,5,7, 3,8,1, 2,6,9}, {1,6,2, 5,4,9, 8,7,3}, {9,3,8, 2,7,6, 4,5,1}, {3,7,4, 8,6,2, 1,9,5}, {8,2,5, 9,1,7, 3,4,6}, {6,1,9, 4,3,5, 7,2,8}, {2,4,1, 6,5,8, 9,3,7}, {5,8,3, 7,9,4, 6,1,2}, {7,9,6, 1,2,3, 5,8,4}};
bool checkRows();bool checkCols();bool check3x3();
bool checkRows(){ bool checkAll[9]; for(int i = 0; i < 9; i++) { checkAll[i] = false; }
for(int j = 0; j < 9; j++) { for(int i = 0; i <9; i++) { int idx = sud[i][j]-1; checkAll[idx] = !checkAll[idx]; } }
bool retVal = true; for(int i = 0; i < 9; i++) { retVal = retVal & checkAll[i]; }
return retVal;}
bool checkCols(){ bool checkAll[9]; for(int i = 0; i < 9; i++) { checkAll[i] = false; }
for(int i = 0; i < 9; i++) { for(int j = 0; j <9; j++) { int idx = sud[i][j]-1; checkAll[idx] = !checkAll[idx]; } }
bool retVal = true; for(int i = 0; i < 9; i++) { retVal = retVal & checkAll[i]; }
return retVal;}
bool check3x3(){ bool checkAll[9]; for(int i = 0; i < 9; i++) { checkAll[i] = false; }
for(int iI = 0; iI < 9; iI+=3) { for(int jJ = 0; jJ < 9; jJ+=3) { for(int i = iI; i < iI+3; i++) { for(int j = jJ; j <jJ+3; j++) { checkAll[sud[i][j]-1] = !checkAll[sud[i][j]-1]; } } } }
bool retVal = true; for(int i = 0; i < 9; i++) { retVal = retVal & checkAll[i]; }
return retVal;}
int main(){ if(checkRows() & checkCols() & check3x3()) cout << "Sudoku solution is correct!" << endl; else cout << "Sudoku solution is wrong!" << endl; return 1;}
