<Codesignal> Sudoku

Medium

Sudoku is a number-placement puzzle. The objective is to fill a 9 × 9 grid with digits so that each column, each row, and each of the nine 3 × 3 sub-grids that compose the grid contains all of the digits from 1 to 9.

This algorithm should check if the given grid of numbers represents a correct solution to Sudoku.

Example

• For

grid = [[1, 3, 2, 5, 4, 6, 9, 8, 7],

              [4, 6, 5, 8, 7, 9, 3, 2, 1],

              [7, 9, 8, 2, 1, 3, 6, 5, 4],

              [9, 2, 1, 4, 3, 5, 8, 7, 6],

              [3, 5, 4, 7, 6, 8, 2, 1, 9],

              [6, 8, 7, 1, 9, 2, 5, 4, 3],

              [5, 7, 6, 9, 8, 1, 4, 3, 2],

              [2, 4, 3, 6, 5, 7, 1, 9, 8],

              [8, 1, 9, 3, 2, 4, 7, 6, 5]]

the output should be
sudoku(grid) = true;

• For

grid = [[1, 3, 2, 5, 4, 6, 9, 2, 7],

              [4, 6, 5, 8, 7, 9, 3, 8, 1],

              [7, 9, 8, 2, 1, 3, 6, 5, 4],

              [9, 2, 1, 4, 3, 5, 8, 7, 6],

              [3, 5, 4, 7, 6, 8, 2, 1, 9],

              [6, 8, 7, 1, 9, 2, 5, 4, 3],

              [5, 7, 6, 9, 8, 1, 4, 3, 2],

              [2, 4, 3, 6, 5, 7, 1, 9, 8],

              [8, 1, 9, 3, 2, 4, 7, 6, 5]]

the output should be
sudoku(grid) = false.

The output should be false: each of the nine 3 × 3 sub-grids should contain all of the digits from 1 to 9.
These examples are represented on the image below.

Input/Output

• [execution time limit] 0.5 seconds (c)

• [input] array.array.integer grid

  A matrix representing 9 × 9 grid already filled with numbers from 1 to 9.

  Guaranteed constraints:
  grid.length = 9,
  grid[i].length = 9,
  1 ≤ grid[i][j] ≤ 9.

• [output] boolean

  • true if the given grid represents a correct solution to Sudoku, false otherwise.

[C] Syntax Tips

// Prints help message to the console
// Returns a string
char * helloWorld(char * name) {
    char * answer = malloc(strlen(name) + 8);
    printf("This prints to the console when you Run Tests");
    strcpy(answer, "Hello, ");
    strcat(answer, name);
    return answer;
}

---

Solution

// Arrays are already defined with this interface:
// typedef struct arr_##name {
//   int size;
//   type *arr;
// } arr_##name;
//
// arr_##name alloc_arr_##name(int len) {
//   arr_##name a = {len, len > 0 ? malloc(sizeof(type) * len) : NULL};
//   return a;
// }
//
//
bool sudoku(arr_arr_integer grid)
{
	for(int i=0;i<9;i++)
	{
		int row[9]={0, }, col[9]={0, };
		for(int j=0;j<9;j++)
		{
			if(i%3==0 && j%3==0)
			{
				int square[9]={0, };
				for(int x=0;x<3;x++)
					for(int y=0;y<3;y++)
					{
						if(square[grid.arr[i+y].arr[j+x]-1]!=0)
							return false;
						square[grid.arr[i+y].arr[j+x]-1]=1;
					}
			}

			if(row[grid.arr[i].arr[j]-1]!=0 || col[grid.arr[j].arr[i]-1]!=0)
				return false;
			row[grid.arr[i].arr[j]-1]=1;
			col[grid.arr[j].arr[i]-1]=1;
		}
	}

	return true;
}