Skip to content

Instantly share code, notes, and snippets.

@chadstewart

chadstewart/backtracking_template.py

Forked from RuolinZheng08/backtracking_template.py
Created December 7, 2021 14:59
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save chadstewart/35e1fda93e7fd8ec332011de0ceb359d to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save chadstewart/35e1fda93e7fd8ec332011de0ceb359d to your computer and use it in GitHub Desktop.
Download ZIP

Revisions

  1. @RuolinZheng08 RuolinZheng08 revised this gist Jun 28, 2021. 4 changed files with 168 additions and 60 deletions.
    28 changes: 14 additions & 14 deletions backtracking_template.py
    View file
    Original file line number Diff line number Diff line change
    @@ -1,22 +1,22 @@
    def is_valid_state(state):
    # check if it is a valid solution
    return True
    # check if it is a valid solution
    return True

    def get_candidates(state):
    return []
    return []

    def search(state, solutions):
    if is_valid_state(state):
    solutions.append(state.copy())
    # return
    if is_valid_state(state):
    solutions.append(state.copy())
    # return

    for candidate in get_candidates(state):
    state.add(candidate)
    search(state, solutions)
    state.remove(candidate)
    for candidate in get_candidates(state):
    state.add(candidate)
    search(state, solutions)
    state.remove(candidate)

    def solve():
    solutions = []
    state = set()
    search(state, solutions)
    return solutions
    solutions = []
    state = set()
    search(state, solutions)
    return solutions
    52 changes: 52 additions & 0 deletions leetcode_nqueens.py
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,52 @@
    class Solution:
    """
    example on the left: [1, 3, 0, 2]
    example on the right: [2, 0, 3, 1]
    """
    def solveNQueens(self, n: int) -> List[List[str]]:
    solutions = []
    state = []
    self.search(state, solutions, n)
    return solutions

    def is_valid_state(self, state, n):
    # check if it is a valid solution
    return len(state) == n

    def get_candidates(self, state, n):
    if not state:
    return range(n)

    # find the next position in the state to populate
    position = len(state)
    candidates = set(range(n))
    # prune down candidates that place the queen into attacks
    for row, col in enumerate(state):
    # discard the column index if it's occupied by a queen
    candidates.discard(col)
    dist = position - row
    # discard diagonals
    candidates.discard(col + dist)
    candidates.discard(col - dist)
    return candidates

    def search(self, state, solutions, n):
    if self.is_valid_state(state, n):
    state_string = self.state_to_string(state, n)
    solutions.append(state_string)
    return

    for candidate in self.get_candidates(state, n):
    # recurse
    state.append(candidate)
    self.search(state, solutions, n)
    state.pop()

    def state_to_string(self, state, n):
    # ex. [1, 3, 0, 2]
    # output: [".Q..","...Q","Q...","..Q."]
    ret = []
    for i in state:
    string = '.' * i + 'Q' + '.' * (n - i - 1)
    ret.append(string)
    return ret
    102 changes: 102 additions & 0 deletions leetcode_sudoku.py
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,102 @@
    class Solution:
    from itertools import product

    SHAPE = 9
    GRID = 3
    EMPTY = '.'
    DIGITS = set([str(num) for num in range(1, SHAPE + 1)])

    def solveSudoku(self, board: List[List[str]]) -> None:
    """
    Do not return anything, modify board in-place instead.
    """
    self.search(board)

    def is_valid_state(self, board):
    # check if it is a valid solution
    # validate all the rows
    for row in self.get_rows(board):
    if not set(row) == self.DIGITS:
    return False
    # validate columns
    for col in self.get_cols(board):
    if not set(col) == self.DIGITS:
    return False
    # validate sub-boxes
    for grid in self.get_grids(board):
    if not set(grid) == self.DIGITS:
    return False
    return True

    def get_candidates(self, board, row, col):
    used_digits = set()
    # remove digits used by the same row
    used_digits.update(self.get_kth_row(board, row))
    # remove digits used by the same column
    used_digits.update(self.get_kth_col(board, col))
    # remove digits used by the 3x3 sub-box
    used_digits.update(self.get_grid_at_row_col(board, row, col))
    used_digits -= set([self.EMPTY])
    candidates = self.DIGITS - used_digits
    return candidates

    def search(self, board):
    if self.is_valid_state(board):
    return True # found solution

    # find the next empty spot and take a guess
    for row_idx, row in enumerate(board):
    for col_idx, elm in enumerate(row):
    if elm == self.EMPTY:
    # find candidates to construct the next state
    for candidate in self.get_candidates(board, row_idx, col_idx):
    board[row_idx][col_idx] = candidate
    # recurse on the modified board
    is_solved = self.search(board)
    if is_solved:
    return True
    else:
    # undo the wrong guess and start anew
    board[row_idx][col_idx] = self.EMPTY
    # exhausted all candidates
    # but none solves the problem
    return False
    # no empty spot
    return True

    # helper functions for retrieving rows, cols, and grids
    def get_kth_row(self, board, k):
    return board[k]

    def get_rows(self, board):
    for i in range(self.SHAPE):
    yield board[i]

    def get_kth_col(self, board, k):
    return [
    board[row][k] for row in range(self.SHAPE)
    ]

    def get_cols(self, board):
    for col in range(self.SHAPE):
    ret = [
    board[row][col] for row in range(self.SHAPE)
    ]
    yield ret

    def get_grid_at_row_col(self, board, row, col):
    row = row // self.GRID * self.GRID
    col = col // self.GRID * self.GRID
    return [
    board[r][c] for r, c in
    product(range(row, row + self.GRID), range(col, col + self.GRID))
    ]

    def get_grids(self, board):
    for row in range(0, self.SHAPE, self.GRID):
    for col in range(0, self.SHAPE, self.GRID):
    grid = [
    board[r][c] for r, c in
    product(range(row, row + self.GRID), range(col, col + self.GRID))
    ]
    yield grid
    46 changes: 0 additions & 46 deletions n_queens.py
    View file
    Original file line number Diff line number Diff line change
    @@ -1,46 +0,0 @@
    def main():
    sol = solveNQueens(8)
    print('Expect 92 solutions, got', len(sol))

    def is_valid_state(state, N):
    return len(state) == N

    def get_candidates(state, N):
    # trim down the search space as much as possible
    if not state:
    return range(N)

    # the next position in state to populate
    position = len(state)
    candidates = set(range(N))
    for col, row in enumerate(state):
    # discard occupied row_index
    candidates.discard(row)
    dist = position - col
    # discard diagonals
    candidates.discard(row + dist)
    candidates.discard(row - dist)

    return candidates

    def search(state, solutions, N):
    if is_valid_state(state, N):
    solutions.append(state.copy())
    return

    for candidate in get_candidates(state, N):
    state.append(candidate)
    search(state, solutions, N)
    state.pop()

    def solveNQueens(N):
    if N < 4: # no solution
    return 0
    solutions = []
    # a list of row indices, len N
    state = []
    search(state, solutions, N)
    return solutions

    if __name__ == '__main__':
    main()
  2. @RuolinZheng08 RuolinZheng08 revised this gist Nov 20, 2020. 1 changed file with 3 additions and 3 deletions.
    6 changes: 3 additions & 3 deletions backtracking_template.py
    View file
    Original file line number Diff line number Diff line change
    @@ -1,9 +1,9 @@
    def is_valid_state(state):
    # check if it is a valid solution
    return True
    # check if it is a valid solution
    return True

    def get_candidates(state):
    return []
    return []

    def search(state, solutions):
    if is_valid_state(state):
  3. @RuolinZheng08 RuolinZheng08 revised this gist Nov 20, 2020. No changes.
  4. @RuolinZheng08 RuolinZheng08 created this gist Nov 20, 2020.
    22 changes: 22 additions & 0 deletions backtracking_template.py
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,22 @@
    def is_valid_state(state):
    # check if it is a valid solution
    return True

    def get_candidates(state):
    return []

    def search(state, solutions):
    if is_valid_state(state):
    solutions.append(state.copy())
    # return

    for candidate in get_candidates(state):
    state.add(candidate)
    search(state, solutions)
    state.remove(candidate)

    def solve():
    solutions = []
    state = set()
    search(state, solutions)
    return solutions
    46 changes: 46 additions & 0 deletions n_queens.py
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,46 @@
    def main():
    sol = solveNQueens(8)
    print('Expect 92 solutions, got', len(sol))

    def is_valid_state(state, N):
    return len(state) == N

    def get_candidates(state, N):
    # trim down the search space as much as possible
    if not state:
    return range(N)

    # the next position in state to populate
    position = len(state)
    candidates = set(range(N))
    for col, row in enumerate(state):
    # discard occupied row_index
    candidates.discard(row)
    dist = position - col
    # discard diagonals
    candidates.discard(row + dist)
    candidates.discard(row - dist)

    return candidates

    def search(state, solutions, N):
    if is_valid_state(state, N):
    solutions.append(state.copy())
    return

    for candidate in get_candidates(state, N):
    state.append(candidate)
    search(state, solutions, N)
    state.pop()

    def solveNQueens(N):
    if N < 4: # no solution
    return 0
    solutions = []
    # a list of row indices, len N
    state = []
    search(state, solutions, N)
    return solutions

    if __name__ == '__main__':
    main()