CareerCup

the ones that are completed signify that the user has gone right uptil now. Next you should do some bookkeeping to find some possible solutions. when user puts wrong entry do a backtracking.

we just need to validate input, nothing about solving the sudoku itself.

public boolean checkValid(int [][] board, int row, int col, int num ) {
if(row<0 || row >=9 )
return false;
if(col<0 || col >=9)
return false;
if(num<=0 || num>9 )
return false;
for(int j=0;j<9;j++)
if(num==board[row][j])
return false;
for(int i=0;i<9;i++)
if(num==board[i][col])
return false;
int seci= row/3;
int secj= col/3;
for(int i=seci;i<seci+3;i++)
for(int j= secj; j<secj+3;j++)
if(num==board[i][j])
return false;
return true;
}

In the above code, shouldnt seci be (row/3)*3 and also secj similarly...

Agree with Maruthi...

Have 3 trie: 1 for the horizontal colums, 1 for the vertical rows and 1 for 9 3x3 boxes.

Do a scan and insert each of the values of the board into the 3 tries, depending on their x and y positions. If there is a collision, sudoku board is invalid.

I had the same question for my Google interview. What interviewer wants is a single function which takes in dimensions of array/matrix which is always going to be 9 cells, and return true/false. Then you can call this function for all rows/ columns / and matrices.
isValid(starti, startj, endi, endj) {
loop through all the cells in given range

}

"check whether the current input is valid." means two things for me:
1. Whether the current input doesn't conflict all the rules (on the same row or the same column, no duplicated number appear, this is the only rule I know, I hardly play sudoku and never finish any single game).
2. Whether the current input can lead to a completed correct solution.
Here is my question: if the current input doesn't conflict the rules, will it always lead to a solution? I really don't know sudoku, so could someone help me answer this question? But in eight queens game, not every valid input can lead to a finish game.

If we don't care about the second point, then the question looks like find duplicated char in a string. I guess use a hashset is not bad.

#include<iostream>

#define N -1

#define M 9
#define P 3

using namespace std;

bool sudoku_solution(int board[][M], const int i, const int j, const int n)
{
if (i < 0 || i > M || j < 0 || j > M || n < 0 || n > M)
return false;

for (int k = 0; k < M; k++)
{
if (board[i][k] == n || board[k][j] == n)
return false;
}

int si = i / P;
int sj = j / P;

for (int k = 0; k < P; k++)
{
for (int l = 0; l < P; l++)
{
if (board[si * P + k][sj * P + l] == n)
return false;
}
}

return true;
}

int main (void)
{
// Book, p48
int board[][M] = {{N, N, N, N, 4, 2, 7, N, 6},
{N, 9, 6, 7, 3, N, N, N, N},
{7, 2, N, N, N, N, N, 5, 8},

{N, N, 2, N, N, N, 8, 6, 7},
{N, 8, N, 2, N, 3, N, 4, N},
{N, 4, 1, N, 7, 8, N, N, N},

{4, N, 5, N, N, 7, 1, N, N},
{1, N, N, 5, N, N, 6, 7, N},
{2, N, N, 3, 6, N, N, N, 4}};

cout << "Sudoku Solution? " << sudoku_solution(board, 4, 2, 7) << endl;
cout << "Sudoku Solution? " << sudoku_solution(board, 4, 2, 4) << endl;

return 0;
}

<pre lang="" line="1" title="CodeMonkey92327" class="run-this"> public static boolean isValid(int [][] sudoku) {

Set<Integer>[] rows = new HashSet[9];
Set<Integer>[] cols = new HashSet[9];
Set<Integer>[][] boxes = new HashSet[3][3];


for(int i =0; i<9; i++) {
int rowbox = i /3;
for(int j =0; j<9; j++) {
int colbox = j /3;

if(rows[i] == null)
rows[i] = new HashSet<Integer>();


if(cols[j] == null)
cols[j] = new HashSet<Integer>();

if(boxes[rowbox][colbox] == null)
boxes[rowbox][colbox] = new HashSet<Integer>();



int val = sudoku[i][j];

if(rows[i].contains(val)) {
System.out.println("Row validation failed for row and column - " + i + " " + j);
return false;
} else {
rows[i].add(val);
}

if(cols[j].contains(val)) {
System.out.println("Column validation failed for row and column - " + i + " " + j);
return false;
}
else {
cols[j].add(val);
}

if(boxes[rowbox][colbox].contains(val)) {
System.out.println("Box failed for rowbox and column - " + i + " " + j);
return false;
}
else {
boxes[rowbox][colbox].add(val);
}

}
}

return true;
}</pre><pre title="CodeMonkey92327" input="yes">
</pre>

A naive way could be:

Scanning vertically all the coloumns-->
Copy the coloumn to a store[9]
Sorting and checking for duplicates

Doing the same Horizontally and for each 3*3 Matrix.

If anytime we encounter a duplicate we break out repoting an error.