Knight's Tour and Maze Path Problems: Backtracking on Grids

def knights_tour(n):
    board = [[-1]*n for _ in range(n)]
    moves = [(2,1),(2,-1),(-2,1),(-2,-1),(1,2),(1,-2),(-1,2),(-1,-2)]

    def get_degree(x, y):
        count = 0
        for dx, dy in moves:
            nx, ny = x+dx, y+dy
            if 0<=nx<n and 0<=ny<n and board[nx][ny]==-1:
                count += 1
        return count

    def bt(x, y, move_num):
        board[x][y] = move_num
        if move_num == n*n - 1: return True
        # Warnsdorff's heuristic: sort by degree (fewest onward moves)
        neighbors = []
        for dx, dy in moves:
            nx, ny = x+dx, y+dy
            if 0<=nx<n and 0<=ny<n and board[nx][ny]==-1:
                neighbors.append((get_degree(nx,ny), nx, ny))
        neighbors.sort()
        for _, nx, ny in neighbors:
            if bt(nx, ny, move_num+1): return True
        board[x][y] = -1  # backtrack
        return False

    bt(0, 0, 0)
    return board

# Maze Solver (find any path)
def solve_maze(maze):
    rows, cols = len(maze), len(maze[0])
    path = []
    visited = [[False]*cols for _ in range(rows)]

    def bt(r, c):
        if r == rows-1 and c == cols-1:
            path.append((r, c))
            return True
        if r<0 or r>=rows or c<0 or c>=cols: return False
        if maze[r][c] == 1 or visited[r][c]: return False
        visited[r][c] = True
        path.append((r, c))
        if bt(r+1,c) or bt(r,c+1) or bt(r-1,c) or bt(r,c-1):
            return True
        path.pop()
        visited[r][c] = False
        return False

    bt(0, 0)
    return path

# Count all paths in maze
def count_paths(maze):
    rows, cols = len(maze), len(maze[0])
    visited = [[False]*cols for _ in range(rows)]
    def bt(r, c):
        if r==rows-1 and c==cols-1: return 1
        if r<0 or r>=rows or c<0 or c>=cols or maze[r][c]==1 or visited[r][c]: return 0
        visited[r][c] = True
        count = sum(bt(r+dr, c+dc) for dr,dc in [(1,0),(-1,0),(0,1),(0,-1)])
        visited[r][c] = False
        return count
    return bt(0, 0)

#include <bits/stdc++.h>
using namespace std;

bool solveMaze(vector<vector<int>>& maze, int r, int c, vector<pair<int,int>>& path) {
    int rows = maze.size(), cols = maze[0].size();
    if (r < 0||r>=rows||c<0||c>=cols||maze[r][c]==1) return false;
    path.push_back({r, c});
    if (r==rows-1 && c==cols-1) return true;
    maze[r][c] = 1; // mark visited
    int dr[] = {1,-1,0,0}, dc[] = {0,0,1,-1};
    for (int d = 0; d < 4; d++) {
        if (solveMaze(maze, r+dr[d], c+dc[d], path)) return true;
    }
    path.pop_back();
    maze[r][c] = 0; // unmark
    return false;
}