ya The interviewer meant that 9x9 matrix .. which are subdivided into boxes like in sudoku .. and some elements are filled in. Writing a N3 solution was the most obvious .. but interviewer wanted a solution which was efficient.

// Create a bunch of sets keeping numbers 1 through 9 for // a) 9 columns, b) 9 rows, and c) 9 3x3 boxes: Set[] columns = new Set[9]; Set[] rows = new Set[9]; Set[][] boxes = new Set[3][3]; // Sudoku board: int[][] board = new int[9][9]; initialize(board); // assume uninitialized cells set to 0 // The algorithm: for (int row = 0; row < 9; ++row) { int row_box = row%3; for (int col = 0; col < 9; ++col) { int col_box = col%s; int value = board[row][col]; if (value == 0) continue; // empty if (rows[row].contains(value)) return false; // conflict within a row else rows[row].add(value); if (columns[col].contains(value)); return false; // conflict within a column else columns[col].add(value); if (boxes[row_box][col_box].contains(value)) return false; // conflict within a box else boxes[row_box][col_box].add(value); } return true; // proper Instead of using Set, one can use BitSet, replacing all calls to contains(int) with isSet(int), and add(int) with set(int). The performance is O(N^2) where N is the matrix dimension (9) not the number of elements (81). You cannot do better than that because all N^2 elements must be checked. Additional memory is O(N), provided we keep the box sise SQRT(N). For instance, for Sudoku with N = 100, the box size would be 10. This way, the number of sets for all boxes would still be SQRT(N)^2 == N.

two typos in my algorithm: use integer division "/" instead of remainder"%" to find a box for a given cell: int row_box = row/3; ... int col_box = col/3; For performance freaks, it can be further optimized using lookups: int[] lookup = { 0, 0, 0, 1, 1, 1, 2, 2, 2 }; ... int row_box = lookup[row]; ... int col_box = lookup[col];

I had a phone interview today. I was asked to write code to solve a Sudoku problem.