Sudoku game generation using backtracking algorithm

backtrack.py

import random
import json

def solve(grid):
    empty = empty_locations(grid)
    if len(empty) == 0:
        return True

    x, y = empty[0]


    values = list(range(1,10))
    random.shuffle(values)

    for val in values:
        if check_valid(grid, x, y, val):
            grid[x][y] = val
            if solve(grid): 
                return True 
            grid[x][y] = 0 


    return False 


def check_valid(grid, x, y, value):

    if value in get_row(grid, x): return False
    if value in get_col(grid, y): return False
    if value in get_square(grid, x, y): return False

    return True


def get_row(grid, x):
    return grid[x]
    
def get_col(grid, y):
    return [grid[row][y] for row in range(9)]

    
def get_square(grid, x, y):
    start_row = (x // 3) * 3
    start_col = (y // 3) * 3
    end_col = start_col + 3

    square = []
    for i in range(3):
        square += grid[start_row+i][start_col:end_col]

    return square


def empty_locations(grid): 
    return [ (x,y)  for x in range(9) for y in range(9) if grid[x][y]==0] 

def print_grid(grid):
    print()
    for row in grid:
        print(row)

def generate_game(difficulty=1):

    # print_grid(grid)

    difficulty = max(min(difficulty, 3), 1)

    num_squares = {1:40, 2:30, 3:20}[difficulty]

    grid = [ [0 for _ in range(9)] for _ in range(9)] 
    solve(grid)

    locations = [(x,y) for x in range(9) for y in range(9)]
    locations = random.sample(locations, num_squares) 

    game = { 'squares':[] }
    for l in locations: 
        x = l[0]
        y = l[1]

        game['squares'].append({'x':x, 'y':y, 'value': grid[x][y] }) 
    return json.dumps(game)