Solving easy sudoku(backtracking)

In this article I’d like to consider backtracking technique. Backtracking is a type of BFS (Brute-force-search) algorithm. Backtracking is DFS(depth first search), because it’ll completely go through one branch before moving to the next.

Short description of the algorithm

Briefly, the program would put 1 in the first cell and check if it’s allowed(checking row, column and box). If it is, go to the next cell, put 1 and check. If it finds out it’s invalid, then increase the number and check again. If a cell is discovered where none of the 9 digits are allowed, then leaves that cell blank and moves back to the previous cell, the number in that cell incremented by one.

Advantages of this method are

• A solution is guaranteed(As long as sudoku is valid)
• Quite simple code in comparison with another methods 
• Solving time is mostly unrelated to “degree of difficulty” of sudoku

The main disadvantage is that solving time might be so slow compared to algorithms modeled after deductive methods. Also sudoku can be designed against backtracking method.

Solution

I’m going to use python for solving it but solutions can be easily implemented in another language. First of all, I’d like to create three checking functions: used_row, used_col, used_box. Used_row function just checks if we find the same number in row. Here comes used_row function.

def used_row(puzzle, row, num):    
    for i in range(9):        
        if puzzle[row][i] == num:            
            return True    
    return False        

Used_col checks if we find the same number in col. That’s pretty simple.

def used_col(puzzle, row, num):
    for i in range(9):
        if puzzle[i][col] == num:
            return True
    return False

Used_box checks if we find the same number in box 3 x 3. I think you shouldn't struggle with understanding it.

def used_box(puzzle, row, col, num):    
    for i in range(3):        
        for j in range(3):            
            if puzzle[i + row][j + col] == num:                
                return True    
    return False

Next function will be is_safe. It’s gonna check if one of these functions return true.

def is_safe(puzzle, row, col, num):    
    return not used_row(puzzle, row, num) and 
        not used_col(puzzle, col, num) and 
        not used_box(puzzle, row - row % 3, col - col % 3, num)

The reason why I pass this kind of arguments (row - row % 3 and col - col % 3) that's becuase we need to check if we find number in square 3x3, that's the easiest way to do it.

Next function is find_empty_cell. l_vars contain i and j indexes; in other words these list stores index of empty cell.

def find_empty_cell(puzzle, l_vars):    
    for i in range(9):        
        for j in range(9):            
            if puzzle[i][j] == 0:                
                l_vars[0], l_vars[1] = i, j                
                return True    
     return False

Last function is solve_sudoku. It is a recursive function, which returns False if sudoku is unsolvable

def solve_sudoku(puzzle):    
    l_vars = [0, 0]    
    if not find_empty_cell(puzzle, l_vars):        
        return True            
     
     row, col = l_vars[0], l_vars[1]
             
     for num in range(1, 10):        
         if is_safe(puzzle, row, col, num):            
             puzzle[row][col] = num            
             if solve_sudoku(puzzle):                
                 return True            
         puzzle[row][col] = 0                
     return False

So, that's it. If you still got problems with implementing it you can go thorugh my code.

Link to GitHub repo: https://github.com/rastr-0/teletype_source_files

See ya soon

@rastr