Algorithm - Backtracking (2)

Leetcode backtracking problem collection (2) - Hard

• 51.N-Queens
• 37.Sudoku Solver

51. N-Queens

For this problem, the trickiest part for me is how to store diagonals.
check this video
use 2 array to index dale and hill diagonals, both length are $n * 2 - 1$

Hill Diagonals: idx = row + col
0 1 2 3 4
1 2 3 4 5
2 3 4 5 6
3 4 5 6 7
4 5 6 7 8

Dale Diagonals: idx = row - col

0 -1 -2 -3 -4
1 0 -1 -2 -3
2 1 0 -1 -2
3 2 1 0 -1
4 3 2 1 0

Use updateBoard(r, c, is_put) to update private variables.
Bacause Python string cannot update element by index (need to slice), so store board in 2d array, then melt the array into string whtn solution found.

def solveNQueens(self, n: int) -> List[List[str]]:
        
    def available(r, c):
        return not cols[c] and not dale[r - c] and not hill[r + c]
    
    def updateBoard(r, c, is_put):
        cols[c] = is_put
        dale[r - c] = is_put
        hill[r + c] = is_put
        board[r][c] = 'Q' if is_put else '.'
    
    def getBoard(board):
        return [''.join(x) for x in board]
    
    def backtrack(r):
        if r == n:
            res.append(getBoard(board))
            return
        
        for c in range(n):
            if not available(r, c):
                continue
            updateBoard(r, c, 1)
            backtrack(r + 1)
            updateBoard(r, c, 0)
    
    cols = [0] * n
    dale = [0] * (2 * n - 1)
    hill = [0] * (2 * n - 1)
    board = [['.'] * n for _ in range(n)]
    res = []
    backtrack(0)
    return res

37. Sudoku Solver

First, this one is really hard. Unlike the n-queen problem, indexing cubes is easy. But Desidning backtrack and how to end the track is pretty hard.
For indexing, I just assign an array from 0 - 9, 10 space to log the fill in number. Just ignore the 0.
For grids, draw it down on a paper then you will find in order to get

0, 1, 2,
3, 4, 5,
6, 7, 8

can be converted from

0, 1, 2
1, 2, 3
2, 3, 4

which is generate by row // 3 + col // 3

def solveSudoku(self, board: List[List[str]]) -> None:
        
    def updateBoard(r, c, n, is_fill):
        board[r][c] = str(n) if is_fill else '.'
        rows[r][n] = is_fill
        cols[c][n] = is_fill
        grids[r // 3 * 3 + c // 3][n] = is_fill
    
    def available(r, c, n):
        return not (rows[r][n] or cols[c][n] or grids[r // 3 * 3 + c // 3][n])

    def backtrack(r, c):
        if r == 9:
            return True
        if c == 9:
            return backtrack(r + 1, 0)
        
        if board[r][c] != '.':
            return backtrack(r, c+1)
        
        for n in range(1, 10):
            if not available(r, c, n):
                continue
            updateBoard(r, c, n, 1)
            if backtrack(r, c + 1):
                return True
            updateBoard(r, c, n, 0)
        return False
    
    rows = [[0] * 10 for _ in range(9)]
    cols = [[0] * 10 for _ in range(9)]
    grids = [[0] * 10 for _ in range(9)]  # idx = row // 3 * 3 + col // 3
    
    # initial rows, cols, and grids
    for i, row in enumerate(board):
        for j, n in enumerate(row):
            if n != '.':
                updateBoard(i, j, int(n), 1)
    
    backtrack(0, 0)

Reference

• http://zxi.mytechroad.com/blog/searching/leetcode-37-sudoku-solver/