Grokking the Coding Interview: Patterns for Coding Questions
Vote

0% completed

​

Solution: Sudoku Solver

Problem Statement

Write a program to solve a Sudoku puzzle by filling the empty cells.

A sudoku solution must satisfy all of the following rules:

  • Each of the digits 1-9 must occur exactly once in each row.
  • Each of the digits 1-9 must occur exactly once in each column.
  • Each of the digits 1-9 must occur exactly once in each of the 9 3x3 sub-boxes of the grid.

The '.' character indicates empty cells.

Example 1:
Input:

            {'5', '3', '.', '.', '7', '.', '.', '.', '.'},
            {'6', '.', '.', '1', '9', '5', '.', '.', '.'},
            {'.', '9', '8', '.', '

.....

.....

.....

Like the course? Get enrolled and start learning!
Arturo Calderón

Arturo Calderón

· 3 years ago

One would expect that the expected result to be the solution of the given sudoku. Why is that the test cases expect a True or False answer? What is the question then?

G

greenwald.juj

· 3 years ago

For the isValid Function, can't you just put it like this instead of having a for loop in it?

  def isValid(self, board, row, col, num):
    '''return True if Valid and False if not valid'''
    ### NEW VERSION ### - this passes the tests
    # Check if in ROW
    if board[row][:] == num: return False
    # Check if in COL
    if board[:][col] == num: return False
    # Check if in 3 x 3 GRID
    if (board[(row//3)*3 + row//3][(col//3)*3 + col%3] == num):
        return False
    return True
   
   ### ORIGINAL VERSION ### 
    for x in range(9):
    # Check if in ROW
      if board[row][x] == num: return False
      # Check if in COL
      if board[x][col] == num: return False
      # Check if in 3 x 3 GRID
      if (board[(row//3)*3 + x//3][(col//3)*3 + x%3] == num):
Show 1 reply
M

mailman14736

· 2 months ago

You can optimize quite a bit by pruning more paths early (only attempting non-used numbers) and using sets instead of iterating in is valid:

class Solution:
    def solveSudoku(self, board):
        row_sets, col_sets, grid_sets = dict(), dict(), dict()
        for i in range(len(board)):
            for j in range(len(board[i])):
                if i not in row_sets:
                    row_sets[i] = set()
                if j not in col_sets:
                    col_sets[j] = set()
                if (i // 3, j // 3) not in grid_sets:
                    grid_sets[(i // 3, j // 3)] = set()
                if board[i][j] != '.':
                    row_sets[i].add(board[i][j])
                    col_sets[j].add(board[i][j])
                    grid_sets[(i // 3, j // 3)].add(b