Sudoku

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.

Image Credit : Code Signal

Input/Output

• [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.

Solution

PYTHON

def sudoku(grid):
    # check each row for duplicates
    for row in grid:
        if len(row) != len(set(row)):
            return False

    # check each column for duplicates
    for i in range(len(grid)):
        col = [row[i] for row in grid]
        if len(col) != len(set(col)):
            return False

    # create 3x3 2D matrix as a flat 1D and check for duplicate
    for row in range(0, 9, 3):
        for col in range(0, 9, 3):
            f = []
            for i in range(row, row + 3):
                for j in range(col, col + 3):
                    f.append(grid[i][j])
            if len(f) != len(set(f)):
                return False

    return True


print(sudoku([
    [1, 2, 3, 4, 5, 6, 7, 8, 9],
    [1, 2, 3, 4, 5, 6, 7, 8, 9],
    [1, 2, 3, 4, 5, 6, 7, 8, 9],
    [1, 2, 3, 4, 5, 6, 7, 8, 9],
    [1, 2, 3, 4, 5, 6, 7, 8, 9],
    [1, 2, 3, 4, 5, 6, 7, 8, 9],
    [1, 2, 3, 4, 5, 6, 7, 8, 9],
    [1, 2, 3, 4, 5, 6, 7, 8, 9],
    [1, 2, 3, 4, 5, 6, 7, 8, 9]
]))

JAVASCRIPT

function sudoku(grid) {
  // check each row for duplicates
  for (let row of grid) {
    if (row.length !== new Set(row).size) {
      return false;
    }
  }

  // check each column for duplicates
  for (let i = 0; i < grid.length; i++) {
    let col = [];
    for (let j = 0; j < grid.length; j++) {
      col.push(grid[j][i]);
    }
    if (col.length !== new Set(col).size) {
      return false;
    }
  }

  // create 3x3 2D matrix as a flat 1D and check for duplicate
  for (let row = 0; row < 9; row += 3) {
    for (let col = 0; col < 9; col += 3) {
      let f = [];
      for (let i = row; i < row + 3; i++) {
        for (let j = col; j < col + 3; j++) {
          f.push(grid[i][j]);
        }
      }
      if (f.length !== new Set(f).size) {
        return false;
      }
    }
  }

  return true;
}

console.log(
  sudoku([
    [1, 2, 3, 4, 5, 6, 7, 8, 9],
    [1, 2, 3, 4, 5, 6, 7, 8, 9],
    [1, 2, 3, 4, 5, 6, 7, 8, 9],
    [1, 2, 3, 4, 5, 6, 7, 8, 9],
    [1, 2, 3, 4, 5, 6, 7, 8, 9],
    [1, 2, 3, 4, 5, 6, 7, 8, 9],
    [1, 2, 3, 4, 5, 6, 7, 8, 9],
    [1, 2, 3, 4, 5, 6, 7, 8, 9],
    [1, 2, 3, 4, 5, 6, 7, 8, 9],
  ])
);