## Google Interview Question for SDE-2s

Country: India
Interview Type: Written Test

Comment hidden because of low score. Click to expand.
1
of 1 vote

Here is a non brute force solution

``````public static void Print()
{
var board = new int[4, 4];
var solutions = GetSolutions(board, 0, 0);
Console.WriteLine(solutions.Count);
}

public static List<int[,]> GetSolutions(int[,] board, int x, int y)
{
var res = new List<int[,]>();
if (y > 3)
{
return res;
}
var options = GetOptions(board, x, y);
int newX = x == 3 ? 0 : x+1;
int newY = x == 3 ? y+1 : y;
foreach (var number in options)
{
var newBoard = board.Clone() as int[,];
newBoard[x, y] = number;
}
return res;
}

private static List<int> GetOptions(int[,] board, int x, int y)
{
var options = new List<int>() { 1, 2, 3, 4 };
for (int i = 0; i < x; i++)
{
var val = board[i, y];
if (options.Contains(val))
{
options.Remove(val);
}
}

for (int i = 0; i < y; i++)
{
var val = board[x, i];
if (options.Contains(val))
{
options.Remove(val);
}
}
var xx = x / 2;
var yy = y / 2;
for (int i = xx*2; i < xx*2+2; i++)
{
for (int j = yy*2; j < yy*2+2; j++)
{
var val = board[i, j];
if (options.Contains(val))
{
options.Remove(val);
}
}
}
return options;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Here is a shitty brute-force solution with hardcoded numbers (python 2)

ideone.com/9QUxd3

{{

import math

def is_compatible(p1, p2, vertical=True, cache={}):
if (p1, p2, vertical) in cache:
return cache[(p1, p2, vertical)]
perm1 = index_to_permutation(p1, 4)
perm2 = index_to_permutation(p2, 4)
box1 = [perm1[:2], perm1[2:]]
box2 = [perm2[:2], perm2[2:]]
if vertical:
box = box1 + box2
else:
box = [b1 + b2 for (b1, b2) in zip(box1, box2)]
rows = len(box)
cols = len(box[0])
compatible = True
for r in xrange(rows):
if len(list(set(box[r]))) != cols:
compatible = False
break
else:
for c in xrange(cols):
if len(list(set(box[i][c] for i in xrange(rows)))) != rows:
compatible = False
break
cache[(p1, p2, vertical)] = compatible
return compatible

def index_to_permutation(p, size):
numbers = range(size)
result = []
for i in xrange(size):
if i < size - 1:
order = int(math.factorial(size - i - 1))
index = p / order
p -= index * order
else:
index = 0
result.append(numbers[index])
del numbers[index]
return result

def print_solution(a, b, c, d):
box = [[a, b], [c, d]]
matrix = [[0] * 4 for i in xrange(4)]
for i in xrange(2):
for j in xrange(2):
sub_box = index_to_permutation(box[i][j], 4)
for ii in xrange(2):
for jj in xrange(2):
matrix[i * 2 + ii][j * 2 + jj] = sub_box[ii * 2 + jj]
for row in matrix:
print row
print '#' * 80

def main():
solutions = []
for a11 in xrange(24):
for a12 in xrange(24):
if not is_compatible(a11, a12, False):
continue
for a21 in xrange(24):
if not is_compatible(a11, a21, True):
continue
for a22 in xrange(24):
if not is_compatible(a22, a12, True):
continue
if not is_compatible(a22, a21, False):
continue
solutions.append([a11, a12, a21, a22])

for solution in solutions:
print_solution(*solution)

print "Total %d solutions" % len(solutions)

if __name__ == '__main__':
main()

}}

Comment hidden because of low score. Click to expand.
0

``````import math

def is_compatible(p1, p2, vertical=True, cache={}):
if (p1, p2, vertical) in cache:
return cache[(p1, p2, vertical)]
perm1 = index_to_permutation(p1, 4)
perm2 = index_to_permutation(p2, 4)
box1 = [perm1[:2], perm1[2:]]
box2 = [perm2[:2], perm2[2:]]
if vertical:
box = box1 + box2
else:
box = [b1 + b2 for (b1, b2) in zip(box1, box2)]
rows = len(box)
cols = len(box[0])
compatible = True
for r in xrange(rows):
if len(list(set(box[r]))) != cols:
compatible = False
break
else:
for c in xrange(cols):
if len(list(set(box[i][c] for i in xrange(rows)))) != rows:
compatible = False
break
cache[(p1, p2, vertical)] = compatible
return compatible

def index_to_permutation(p, size):
numbers = range(size)
result = []
for i in xrange(size):
if i < size - 1:
order = int(math.factorial(size - i - 1))
index = p / order
p -= index * order
else:
index = 0
result.append(numbers[index])
del numbers[index]
return result

def print_solution(a, b, c, d):
box = [[a, b], [c, d]]
matrix = [[0] * 4 for i in xrange(4)]
for i in xrange(2):
for j in xrange(2):
sub_box = index_to_permutation(box[i][j], 4)
for ii in xrange(2):
for jj in xrange(2):
matrix[i * 2 + ii][j * 2 + jj] = sub_box[ii * 2 + jj]
for row in matrix:
print row
print '#' * 80

def main():
solutions = []
for a11 in xrange(24):
for a12 in xrange(24):
if not is_compatible(a11, a12, False):
continue
for a21 in xrange(24):
if not is_compatible(a11, a21, True):
continue
for a22 in xrange(24):
if not is_compatible(a22, a12, True):
continue
if not is_compatible(a22, a21, False):
continue
solutions.append([a11, a12, a21, a22])

for solution in solutions:
print_solution(*solution)

print "Total %d solutions" % len(solutions)

if __name__ == '__main__':
main()``````

Comment hidden because of low score. Click to expand.
0

so we represent each square as a permutation (of which there are 1 * 2 * 3 * 4 = 24) the uppert left square may have each permutation from 1-st to 24-th, the left bottom square must be compatible with upper left square, the same for right top square. And finally the bottom right square is taken to be compatible with left bottom and right top squares.

Comment hidden because of low score. Click to expand.
0
of 0 vote

I can't figure out anything else but to do a simple "brute force" with some minor optimizations. Undebugged solution in python 2:

``````import itertools

def isValid(l):
check = lambda x: len(set(x)) == 4 and min(x) == 1 and max(x) == 4
assert(all(check(x) for x in l))
assert(all(check(x) for x in zip(*l)))
squares = [[] for x in range(4)]
for idx1, row in enumerate(l):
for idx2, col in enumerate(row):
squares[2*(idx1//2) + idx2].append(col)
assert(all(check(x) for x in squares))

def getValidSolutionCount():
validPermutations = list(itertools.permutations((1,2,3,4)))
tot = 0
for p in itertools.product([validPermutations]*4):
try:
isValid(p)
tot += 1
except:
pass

Comment hidden because of low score. Click to expand.
0
of 0 vote

The obvious solution is the brute force one having (4^16)*48 steps (48 steps to check it). It can be reduced by using permutations of 1234 on each row. The total number of steps will be (4!*4!*4!*4!)*32 (32 steps to check it, since we don't need to check each row now).
This can be easily implemented in a dfs manner.

``````public void dfs(int r, int c, int[][] map, boolean[] values) {
if (r == 4 && c == 0) {

check(map);
return;
}

for (int i = 0; i < 4; i++) {
if (!values[i]) {
map[r][c] = i + 1;
values[i] = true;
if (c == 3) {
dfs(r + 1, 0, map, new boolean[4]);
} else {
dfs(r, c + 1, map, values);
}
values[i] = false;
}
}

}``````

The interesting thing would be the check method. It can be written in a very clean way for each of the small 2X2 squares.
Here's the complete code. Works perfectly :)

``````import java.util.ArrayList;

public class Impromptu {
ArrayList<int[][]> list = new ArrayList<int[][]>();
int[] dx = { 0, 1, 1, 0 };
int[] dy = { 0, 0, 1, 1 };

public void dfs(int r, int c, int[][] map, boolean[] values) {
if (r == 4 && c == 0) {

check(map);
return;
}

for (int i = 0; i < 4; i++) {
if (!values[i]) {
map[r][c] = i + 1;
values[i] = true;
if (c == 3) {
dfs(r + 1, 0, map, new boolean[4]);
} else {
dfs(r, c + 1, map, values);
}
values[i] = false;
}
}

}

public int[][] clone(int[][] map) {
int[][] ret = new int[4][4];
for (int i = 0; i < 4; i++) {
for (int j = 0; j < 4; j++) {
ret[i][j] = map[i][j];
}
}

return ret;
}

public void print(int[][] map) {
for (int i = 0; i < 4; i++) {
for (int j = 0; j < 4; j++) {
System.out.print(map[i][j]);
}
System.out.println("");
}

System.out.println("------------------");
}

public boolean check(int[][] map) {
int r = 0, c = 0;
for (int i = 0; i < 4; i++) {
int nr = r + 2 * dy[i];
int nc = c + 2 * dx[i];
boolean[] vals = new boolean[5];
for (int j = 0; j < 4; j++) {
int ncc = nc + dx[j];
int nrr = nr + dy[j];
if (vals[map[nrr][ncc]]) {
return false;
} else
vals[map[nrr][ncc]] = true;
}
}

for (int j = 0; j < 4; j++) {
boolean vals[] = new boolean[5];
for (int i = 0; i < 4; i++) {
if (vals[map[i][j]]) {
return false;
} else
vals[map[i][j]] = true;
}
}

print(map);
return true;
}

public static void main(String args[]) {

new Impromptu().dfs(0, 0, new int[4][4], new boolean[4]);
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Here is my Code in C++. Have a look.

#include<iostream>
#include<stdio.h>
#define MAX 4
using namespace std;
bool NotInSqr(int mat[][MAX],int i,int j,int k,int n)
{
int srow=0,scol=0;
if(i>=0 && i<n/2)
srow=0;
else
srow=n/2;
if(j>=0 && j<n/2)
scol=0;
else
scol=n/2;
for(i=srow;i<srow+2;i++)
{
for(j=scol;j<scol+2;j++)
{
if(mat[i][j]==k)
return false;
}
}
return true;
}
bool NotInCol(int mat[][MAX],int i,int j,int k,int n)
{
int r;
for(r=0;r<i;r++)
{
if(mat[r][j]==k)
return false;
}
return true;
}
bool NotInRow(int mat[][MAX],int i,int j,int k,int n)
{
int r;
for(r=0;r<j;r++)
{
if(mat[i][r]==k)
return false;
}
return true;
}
void sudoku(int mat[][MAX],int i,int j,int *cnt,int n)
{
if(i>n || j>n)
return;
else if(i==n && j==0)
{
(*cnt)++;
int i1,j1;
for(i1=0;i1<n;i1++)
{
cout<<"\n";
for(j1=0;j1<n;j1++)
cout<<mat[i1][j1]<<" ";
}
cout<<"\n\n";
return;
}
else if(i<n && j<n)
{
int k;
for(k=1;k<5;k++)
{
if(NotInRow(mat,i,j,k,n) && NotInCol(mat,i,j,k,n) && NotInSqr(mat,i,j,k,n))
{
mat[i][j]=k;
sudoku(mat,(i+(j+1)/n),(j+1)%n,cnt,n);
mat[i][j]=0;

}
}
}
}
int main()
{
int n=4,cnt=0,mat[MAX][MAX];
memset(mat,0,sizeof(mat));
sudoku(mat,0,0,&cnt,n);
cout<<"No. of solutions are "<<cnt<<"\n";
return 0;
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

The brutal force solution is O(N^(N^2)) I think, , here N is the length/width of the matrix.

If you use some knowledge from combination, which means choosing 2 different integers from 4 and interchange them, then you can optimize the process to be O(N^6). And if you use hashtable, then you can make it O(N^4).

Comment hidden because of low score. Click to expand.
0
of 0 vote

The entire solution fits into 32 bit int (every number is 2 bits). The row fits into one byte. Only 24 (out of 256) possible byte values a valid rows. Rows cannot repeat in the same solution, so permutate 4 different rows and note wich permutations are valid solutions. That is 24x23x22x21 about quarter of a million permutations.

Now, we can do better than that. Let's say rows are conflicting if at least one of the numbers is the same at the same positions, such as:

1234
and
3241

are conflicting because 2 at second position is the same.

1234
and
3421

are not conflicting.

So, when we do the permutations, when we loop through second row and on, we can select rows that are not conflicting to the previously selected. This will enourmously reduce amount of permutations and in addition we would have to validate only subsquares.

Comment hidden because of low score. Click to expand.
0
of 0 vote

Here is my java solution. it may need optimization of course :

``````package test;

import java.util.ArrayList;
import java.util.List;

public class SuDoku {

public static void main(String[] args) {

printSuDoku();

}

private static void printSuDoku() {
int total = 0;
int[][] arr = new int[][]{{1,2},{3,4}};
List<int[][]> allComb = findAllCombinations(arr);
List<int[]> allCombIndex = findAllCombIndex(allComb.size() -1);
for(int i = 0; i< allCombIndex.size() ; i++){
int[][] result = generatex4(allComb.get(allCombIndex.get(i)[0]), allComb.get(allCombIndex.get(i)[1]), allComb.get(allCombIndex.get(i)[2]), allComb.get(allCombIndex.get(i)[3]));
if(isValidRowColumnx4(result)){
printx4(result);
System.out.println("----------");
total ++;
}
}
System.out.println("total combinations : " + total);
}

private static void printx4(int[][] arr){
System.out.println(arr[0][0] +"|"+arr[0][1] + "|"+arr[0][2] + "|"+arr[0][3] + "|");
System.out.println(arr[1][0] +"|"+arr[1][1] + "|"+arr[1][2] + "|"+arr[1][3] + "|");
System.out.println(arr[2][0] +"|"+arr[2][1] + "|"+arr[2][2] + "|"+arr[2][3] + "|");
System.out.println(arr[3][0] +"|"+arr[3][1] + "|"+arr[3][2] + "|"+arr[3][3] + "|");
}

private static int[][] generatex4(int[][] arr1,int[][] arr2,int[][] arr3,int[][] arr4){
int[][] result = new int[4][4];
locatex4(result, arr1, 0, 0);
locatex4(result, arr2, 2, 0);
locatex4(result, arr3, 0, 2);
locatex4(result, arr4, 2, 2);

return result;
}

private static void locatex4(int[][] result, int[][] arr, int x,int y){
result[x][y] = arr[0][0];
result[x][y+1] = arr[0][1];
result[x+1][y] = arr[1][0];
result[x+1][y+1] = arr[1][1];
}

private static List<int[][]> findAllCombinations(int[][] arr){
List<int[][]> result =  new ArrayList<int[][]>();

int[] intArr = new int[]{arr[0][0], arr[0][1], arr[1][0], arr[1][1]};

for(int i = 0; i<4 ; i++){
for(int j = 0; j<4; j++){
for(int k = 0; k<4; k++){
for(int m = 0; m<4; m++){
if(i!=j && i!=k && i!= m && j != k && j!=m && k!= m){
}
}
}
}
}

return result;
}

private static List<int[]> findAllCombIndex(int index){

List<int[]> result =  new ArrayList<int[]>();

for(int i = 0; i<index ; i++){
for(int j = 0; j<index; j++){
for(int k = 0; k<index; k++){
for(int m = 0; m<index; m++){
if(i!=j && i!=k && i!= m && j != k && j!=m && k!= m){
}
}
}
}
}

return result;
}

private static boolean isValidRowColumnx4(int[][] arr){
boolean result = false;

List<int[]> rowList = new ArrayList<int[]>();
List<int[]> columnList = new ArrayList<int[]>();
for(int i = 0; i< arr.length; i++){
}
for(int i = 0; i< arr.length; i++){
}

for(int i = 0; i<rowList.size() ; i++){
if(isValid(rowList.get(i)) && isValid(columnList.get(i))){
result = true;
}else{
result= false;
break;
}
}

return result;
}

private static boolean isValid(int[] arr) {
boolean b1 = false,b2 = false,b3 = false,b4 = false;
for(int i = 0; i< arr.length; i++){
switch(arr[i]){
case 1 :
b1 = true;
break;
case 2 :
b2 = true;
break;
case 3 :
b3 = true;
break;
case 4 :
b4 = true;
break;
}
}
return b1 && b2 && b3 && b4;
}

}``````

Comment hidden because of low score. Click to expand.
0

this way, we have 220 solutions

Comment hidden because of low score. Click to expand.
0
of 2 vote

Aren't there 4! * 2 * 2 * 2 * 2 many possible solutions?

Consider the left top square. To fill in the square with a permutation of {1,2,3,4},
there are 4! possibilities. Determining the square, each row of the square on its right and
each column of the square on its bottom only have two possible numbers so each of them has the freedom of 2. Once you determine those three squares, the last square would have no freedom. Thus, there are 4! * 2 * 2 * 2 * 2 possible solutions.

To print all of them, use, e.g., next_permutation function with array [1,2,3,4] to fill the first square, and filling last of the square as described.

4! * 2 * 2 * 2 * 2 is just 384 so, simply store them using 384 * 16 * 4 bytes.

Comment hidden because of low score. Click to expand.
2

I was thinking along the same lines until the following counterexample. If the numbers are arranged as follows then it becomes impossible to fill the lower fourth square because both 4 and 1 must go in the lower right, which is clearly impossible.
| 1 2 | 4 3 |
| 3 4 | 1 2 |
------------ |
| 4 1 | * * |
| * * | * * |
This means we have to somehow take into account that after filling in the left top square, the top right square cannot have column with the same numbers as any row of the lower left square.

Also the following board should be impossible.
| 1 2 | 3 4 |
| 3 4 | 2 1 |
------------ |
| * * | * * |
| 4 1| * * |
In both of these cases it looks like there are two ways to fill in the lower left square rather than four, so this means that the total number of solutions should be 4!*2*4 + 4!*2*2 = 4!*2*6 = 288 instead of 384.

Comment hidden because of low score. Click to expand.
1
of 1 vote

Right. I missed that point. Thanks Michael.

Comment hidden because of low score. Click to expand.
1
of 1 vote

Sorry, I did not get it.
If 2x2 sudoku, should be 8 possibilities.
If 4x4 sudoku, should be 288.

``````2x2:
|  1 2  |  3  4
|  3 4  |  1  2
---------------
|  4 1  |  2  3
|  2 3  |  4  1

AB  AB  BA  BA  CD  CD  DC  DC
CD  DC  CD  DC  AB  BA  AB  BA``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

I have found 240 slutions with the following code. I thought that for the first row (top) we have 4! possibility and according to this elements we have 2 possibility for the first two columns of second row. Then, we have another 2 possibility for the last two places of second row. Here is the important point!! We should choose first two elements of the third row according to the following rules;

1 2 X Y
3 4 Z T HERE if (X == D && Z == F) || (X == F && Z == D) sudoku cannot be D FK L solved AND if there is no common element, again it cannot be solved
M NO P

``````import java.util.ArrayList;

public class Q3 {

public static void main(String[] args) {
// TODO Auto-generated method stub
ArrayList<String> seqs = new ArrayList<String>();
String bos = "";
String dolu = "1234";
findSubSeqs(seqs, bos, dolu);
ArrayList<String[]> sudokus = findAlternatives(seqs);
for (int a = 0;a < sudokus.size(); a++){
for (int b = 0; b < 4;b++){
System.out.println(sudokus.get(0)[b]);
}
System.out.println("--------------------");
}
System.out.println(sudokus.size());
}
public static void findSubSeqs(ArrayList<String> seqs, String bos, String dolu){
if (dolu.length()==0){
}
else{
for (int a = 0; a < dolu.length();a++){
String ch = dolu.charAt(a) + "";
bos += dolu.charAt(a) + "";
findSubSeqs(seqs, bos, dolu.replaceFirst(ch, ""));
bos = bos.substring(0, bos.length()-1);
}
}
}
public static ArrayList<String[]> findAlternatives(ArrayList<String> seqs){
ArrayList<String[]> arr = new ArrayList<String[]>();
for (int a = 0; a < seqs.size();a++){
String[] temp = new String[4];
temp[0] = seqs.get(a);
for (int b = 0; b < 2;b++){
if (b == 0){
temp[1] = seqs.get(a).charAt(2) + "";
temp[1] += seqs.get(a).charAt(3) + "";
}
else{
temp[1] = seqs.get(a).charAt(3) + "";
temp[1] += seqs.get(a).charAt(2) + "";
}
for (int c = 0; c < 2; c++){
temp[1] = temp[1].substring(0,2);
if (c == 0){
temp[1] += seqs.get(a).charAt(0) + "";
temp[1] += seqs.get(a).charAt(1) + "";
}
else{
temp[1] += seqs.get(a).charAt(1) + "";
temp[1] += seqs.get(a).charAt(0) + "";
}
for (int d = 0; d < 2; d++){
int f = Integer.parseInt(temp[0].substring(0, 1));
int s = Integer.parseInt(temp[1].substring(0,1));
int [] ds = new int[2];
int cs = 0;
for (int count = 1; count < 5; count++){
if (f != count && s != count){
ds[cs++] = count;
}
}
if (d == 0){
temp[2] = ds[0] + "";
}
else{
temp[2] = ds[1] + "";
}
for (int e = 0; e < 2; e++){
temp[2] = temp[2].substring(0,1);
if (e == 0){
temp[2] += f;

}
else
temp[2] += s;
if (((temp[2].charAt(0) + "").equals(temp[0].charAt(2) + "") && (temp[2].charAt(1)+"").equals(temp[1].charAt(2) + "")) || ((temp[2].charAt(0) + "").equals(temp[1].charAt(2) + "") && (temp[2].charAt(1) + "").equals(temp[0].charAt(2) + ""))  ){
break;
}
if ((!(temp[2].charAt(0) + "").equals(temp[0].charAt(2) + "") && !(temp[2].charAt(1)+"").equals(temp[1].charAt(2) + "")) && (!(temp[2].charAt(0) + "").equals(temp[1].charAt(2) + "") && !(temp[2].charAt(1) + "").equals(temp[0].charAt(2) + ""))){
break;
}
for (int g = 1;g < 5; g++){
if (g != Integer.parseInt(temp[2].substring(0,1)) && g != Integer.parseInt(temp[2].substring(1,2)) && g != Integer.parseInt(temp[1].substring(2,3)) &&g != Integer.parseInt(temp[0].substring(2,3)) ){
temp[2] += g+ "";
}
}
for (int g = 1;g < 5; g++){
if (g != Integer.parseInt(temp[2].substring(0,1)) && g != Integer.parseInt(temp[2].substring(1,2)) && g != Integer.parseInt(temp[2].substring(2,3))){
temp[2] += g+ "";
}
}
temp[3] = "";
for (int g = 0;g <4;g++){

for (int h = 1;h < 5;h++){
if (h != Integer.parseInt(temp[0].substring(g,g+1)) && h != Integer.parseInt(temp[1].substring(g,g+1)) && h != Integer.parseInt(temp[2].substring(g,g+1))){
temp[3] += h+ "";
}
}

}
}

}
}
}
}
return arr;

}

}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````#include<stdio.h>

void backtrack(int[][4], int, int) ;

int main() {
int a[4][4];
backtrack(a,0,0);
}

void backtrack(int a[][4], int i, int j) {
if(i==4) {
printf("\n");
for(int i=0;i<4;i++) {
for(int j=0;j<4;j++) {
printf("%d ",a[i][j]);
}
printf("\n");
}
}
for(int k=1;k<=4;k++) {
int x;
for(x=0;x<i && a[x][j]!=k;x++);
if(x<i)
continue;
for(x=0;x<j && a[i][x]!=k;x++);
if(x<j)
continue;
if(i%2) {
if(j%2) {
if(a[i-1][j-1]==k)
continue;
}
else {
if(a[i-1][j+1]==k)
continue;
}
}
a[i][j]=k;
backtrack(a,j==3?i+1:i,(j+1)%4);
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Here is my take to this:

``````import java.util.List;

class Sudoku2X2 {
public static void main (String[] args) {
int[][] array = {{0, 0, 0, 0}, {3, 0, 4, 0}, {0, 2, 0, 0}, {0, 0, 0, 0}};
SudokuBoard board = new SudokuBoard(array);
if (!board.isBoardValid()) {
System.err.println("The input board is not valid. Exiting..");
System.exit(1);
}
List<SudokuBoard> boards = getAllValidBoards(0, 0, board);
System.out.println("Number of boards = " + boards.size());
for (int i = 0; i < boards.size(); i++) {
System.out.println("Board " + i + ":");
boards.get(i).print();
}
}

public static List<SudokuBoard> getAllValidBoards(int x, int y, SudokuBoard board) {
if (x >= SudokuBoard.SIZE || y >= SudokuBoard.SIZE) {
}
else {
if (!board.isEmpty(x, y)) {
int x1 = x + 1;
int y1 = y;
if (x1 == SudokuBoard.SIZE) {
x1 = 0;
y1 ++;
}
}
else {
for (int i = 0; i <= SudokuBoard.SIZE; i++) {
if (board.isMoveValid(x, y, i)) {
SudokuBoard tempBoard = board.clone();
tempBoard.move(x, y, i);
int x1 = x + 1;
int y1 = y;
if (x1 == SudokuBoard.SIZE) {
x1 = 0;
y1 ++;
}
}
}
}
}
return boards;
}

}

class SudokuBoard {
public static final int SIZE = 4;

private int board[][];
private int validator[];

public SudokuBoard() {
board = new int[SIZE][SIZE];
validator = new int[SIZE];
}

public SudokuBoard(int[][] array) {
board = array;
validator = new int[SIZE];
}

public boolean isBoardValid() {
for (int i = 0; i < SIZE; i++) {
if (!validateRow(i) || !validateColumn(i) || !validateSquare(i%2, i/2)) {
return false;
}
}
return true;
}

public boolean isEmpty(int x, int y) {
return (board[x][y] == 0);
}

public boolean isBoardComplete() {
for (int i = 0; i < SIZE; i++) {
for (int j = 0; j < SIZE; j++) {
if (board[i][j] == 0) {
return false;
}
}
}
return true;
}

public void move(int x, int y, int move) {
board[x][y] = move;
}

public boolean isMoveValid(int x, int y, int move) {
if (x < 0 || y < 0 || move < 1 || x >= SIZE || y >= SIZE || move > SIZE) {
return false;
}
else if (board[x][y] != 0) {
return false;
}

board[x][y] = move;

if (validateRow(x) && validateColumn(y) && validateSquare(x/2, y/2)) {
board[x][y] = 0;
return true;
}
board[x][y] = 0;
return false;
}

private boolean validateRow(int row) {
if (row < 0 || row >= SIZE) {
return false;
}
resetValidator();
for (int i = 0; i < SIZE; i++) {
int element = board[row][i];
if (element == 0) {
continue;
}
if (validator[element - 1] != 0) {
return false;
}
else {
validator[element - 1] = 1;
}
}
return true;
}

private void resetValidator() {
for (int i = 0; i < SIZE; i++) {
validator[i] = 0;
}
}

private boolean validateColumn(int column) {
if (column < 0 || column >= SIZE) {
return false;
}
resetValidator();
for (int i = 0; i < SIZE; i++) {
int element = board[i][column];
if (element == 0) {
continue;
}
if (validator[element - 1] != 0) {
return false;
}
else {
validator[element - 1] = 1;
}
}
return true;
}

private boolean validateSquare(int sqRow, int sqColumn) {
if (sqRow < 0 || sqColumn < 0 || sqRow >= 2 || sqColumn >= 2) {
return false;
}
int startX = sqRow * 2;
int startY = sqColumn * 2;
resetValidator();
for (int i = 0; i < 2; i++) {
for (int j = 0; j < 2; j++) {
int element = board[i][j];
if (element == 0) {
continue;
}
if (validator[element - 1] != 0) {
return false;
}
else {
validator[element - 1] = 1;
}
}
}
return true;
}

public SudokuBoard clone() {
int board[][] = new int[SIZE][SIZE];
for (int i = 0; i < SIZE; i++) {
for (int j = 0; j < SIZE; j++) {
board[i][j] = this.board[i][j];
}
}
return new SudokuBoard(board);
}

public void print() {
for (int i = 0; i < SIZE; i++) {
for (int j = 0; j < SIZE; j++) {
System.out.print(board[i][j] + " ");
}
System.out.println();
}
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````import copy

def findPossibleNums(grid, index):
[i,j] = index
possibleNums = [1,2,3,4]

for x in range(i):
num = grid[x][j]
if num in possibleNums:
possibleNums.remove(num)

for y in range(j):
num = grid[i][y]
if num in possibleNums:
possibleNums.remove(num)

x = i%2
y = j%2

if x == 1:
if grid[i-1][j-y]in possibleNums:
possibleNums.remove(grid[i-1][j-y])
if grid[i-1][j-y+1] in possibleNums:
possibleNums.remove(grid[i-1][j-y+1])

if y == 1:
if grid[i][j-1] in possibleNums:
possibleNums.remove(grid[i][j-1])

return possibleNums

def find2Combo():
twoXtwoGrid = [[[0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0]]]
for i in xrange(4):
for j in xrange(4):
tempGridCollection = []

for grid in twoXtwoGrid:
possibleNums = findPossibleNums(grid, [i, j])

for num in possibleNums:
tempGrid = copy.deepcopy(grid)
tempGrid[i][j] = num
tempGridCollection.append(tempGrid)

twoXtwoGrid = tempGridCollection
return twoXtwoGrid``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Here is a c++ solution using bit operation.

``````#include <cstdio>

int get(unsigned int sokudo, int index) {
unsigned int mask1 = 1 << (2 * index), mask2 = 1 << (2 * index + 1);
}

unsigned int set(unsigned int sokudo, int index, int val) {
int bit1 = val & 1, bit2 = val >> 1;
unsigned int mask1 = 1 << (2 * index), mask2 = 1 << (2 * index + 1);
unsigned int mask3 = bit1 << (2 * index), mask4 = bit2 << (2 * index + 1);
}

void print(int sokudo) {
static int count = 0;
printf("%d solution:\n", ++count);
for (int i = 0; i < 4; i++) {
for (int j = 0; j < 4; j++) {
printf("%d ", get(sokudo, i*4+j));
}
printf("\n");
}
printf("\n");
}

void dfs(int index, unsigned int sokudo, unsigned int row, unsigned int column, unsigned int block) {
if (index == 16) {
print(sokudo);
return;
}
int x = index / 4, y = index % 4;
for (int i = 0; i < 4; i++) {
unsigned int mask1 = 1 << (4 * x + i);
unsigned int mask2 = 1 << (4 * y + i);
unsigned int mask3 = 1 << (4 * (x/2*2+y/2) + i);
sokudo = set(sokudo, index, i);
dfs(index + 1, sokudo, row, column, block);
}
}

int main() {
dfs(0, 0, 0, 0, 0);
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Here is solution using recursion to find all possible puzzles

``````import java.util.ArrayList;

public class SodukoSolutions {

public static int count = 0;
public static int fails = 0;

public static void main(String[] args) {

int[][] board = new int[4][4];
fillIt(board,0,0);
System.out.println("Count of solutions: "+count);
System.out.println("Count of failures: "+fails);

}
//Fills boards recursively and counts if the filling was a success or not
public static void fillIt(int[][]board, int x, int y){
ArrayList<Integer> pos = getPossibilities(board, x, y);
int[][] clone = clone(board);
if(pos.size()==0){
fails++;
return;
}
for (Integer integer : pos) {
clone[x][y] = integer;
if(x==3 && y==3){
if(checkBoard(clone)){
printBoard(clone);
count++;
return;
}
else{
System.out.println("Failed!");
}
}
if(x==3){
fillIt(clone,0,y+1);
}
else{
fillIt(clone,x+1,y);
}
}
}
public static int[][] clone(int[][] board){
int[][] ret = new int [4][4];
for(int i=0;i<4;i++){
for(int j=0;j<4;j++){
ret[i][j] = board[i][j];
}
}
return ret;
}
public static void printBoard(int[][] board){
for(int i=0;i<4;i++){
for(int j=0;j<4;j++){
System.out.print(board[i][j]);
}
System.out.println();
}
System.out.println();
}
//Gets all the possibilities for a cell
public static ArrayList<Integer> getPossibilities(int[][] board,int x,int y){
ArrayList<Integer> pos = new ArrayList<Integer>();
//Check rows
for(int i = 0;i<4;i++){
if(board[x][i]!=0){
if(pos.contains(board[x][i])){
pos.remove(pos.indexOf(board[x][i]));
}
}
}
//Check Columns
for(int i = 0;i<4;i++){
if(board[i][y]!=0){
if(pos.contains(board[i][y])){
pos.remove(pos.indexOf(board[i][y]));
}
}
}
//Check squares
int moveX = x-x%2;
int moveY = y-y%2;
for(int i=moveX;i<moveX+2;i++){
for(int j=moveY;j<moveY+2;j++){
if(board[i][j]!=0){
if(pos.contains(board[i][j])){
pos.remove(pos.indexOf(board[i][j]));
}
}
}
}
return pos;
}
//Not really necessary since the getPossibilities function gets only valid numbers
public static boolean checkBoard(int[][] board){
//check rows for duplicates
for(int i=0;i<4;i++){
for(int j=0;j<4;j++){
return false;
}
else{
}
}
}
for(int i=0;i<4;i++){
for(int j=0;j<4;j++){
return false;
}
else{
}
}
}
return true;

}

}``````

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.