A collection of backtracking algorithms implemented in TypeScript for studying

BacktrackingAlgorithm.ts

//=========================- - Backtracking Algorithms - -=========================//

/*
- Backtracking algorithms:
  are a type of algorithmic technique that is used to solve problems by trying out different
  possible solutions and "backtracking" or undoing a choice when it is found to be incorrect or not feasible.
  These algorithms are useful for solving problems where there are many possible solutions,
  but only a few of them are actually valid or optimal.

- Sudoku puzzles: Backtracking algorithms are often used to solve Sudoku puzzles, which involve filling a 9x9 grid with
  numbers so that each row, column, and 3x3 sub-grid contains all the numbers from 1 to 9 without any repeats.

- Graph coloring: Backtracking algorithms can be used to solve problems that involve coloring the vertices of a graph so
  that no two adjacent vertices have the same color.

- Subset sum: Backtracking algorithms can be used to solve problems that involve finding a subset of numbers that add up
  to a specific target value.

- N-Queens problem: Backtracking algorithms can be used to solve the classic "N-Queens" problem, which involves placing
  N queens on an NxN chessboard so that no two queens threaten each other.

- Knapsack problem: Backtracking algorithms can be used to solve problems that involve selecting a subset of items with
  maximum value that fit in a given knapsack or container.
*/

namespace BacktrackAlgorithm {
  export type QueenPositions = number[][];

  export const solveNQueens = (boardSize: number) => {
    const solutions = findQueenPositions([], [], [], boardSize);

    const board = solutions.map((solution) => getBoard(boardSize, solution))

    const log = board.map(x => x.map(y => y.toString()).join('\n')).join('\n\n')

    return {
      solutions,
      board,
      log,
    }
  }

  const findQueenPositions = (positions: number[], posDiagonals: number[], negDiagonals: number[], boardSize: number) => {
    const row = positions.length;

    return row === boardSize ? [positions] : range(boardSize)
        .filter((col) => isValidPlacement(col, positions, posDiagonals, negDiagonals))
        .flatMap((col) =>
          findQueenPositions(
            [...positions, col],
            [...posDiagonals, row + col],
            [...negDiagonals, row - col],
            boardSize
          )
        );
    }

  const isValidPlacement = (col: number, positions: number[], posDiagonals: number[], negDiagonals: number[]) => {
    const row = positions.length;

    return (
      !positions.includes(col) &&
      !posDiagonals.includes(row + col) &&
      !negDiagonals.includes(row - col)
    );
  }

  const range = (n: number) => [...Array(n).keys()]

  const getBoard = (boardSize: number, positions: number[]) =>
    range(boardSize).map((x) =>
      range(boardSize).map((y) => (y === positions[x] ? 1 : 0))
    );

  export type Board = number[][];

  export function solveSudoku(board: Board) {
    const emptyCell = findEmptyCell(board)

    if (!emptyCell) {
      return board
    }

    const [row, col] = emptyCell

    // The reason we use the number 9 here is because of the specific rules of Sudoku,
    // where the numbers must be between 1 and 9. In our code, however, we represent empty spaces with the number 0.
    for (let num = 1; num <= 9; num++) {
      if (isValidMove(board, row, col, num)) {
        board[row][col] = num

        const result = solveSudoku(board)

        if (result) {
          return result
        }

        board[row][col] = 0
      }
    }

    return null
  }

  function findEmptyCell(board: Board) {
    for (let row = 0; row < 9; row++) {
      for (let col = 0; col < 9; col++) {
        if (board[row][col] === 0) {
          return [row, col]
        }
      }
    }

    return null
  }

  function isValidMove(board: Board, row: number, col: number, num: number) {
    return (
      isRowValid(board, row, num) &&
      isColValid(board, col, num) &&
      isBoxValid(board, row, col, num)
    );
  }

  //Cannot have the repeated numbers in the row
  function isRowValid(board: Board, row: number, num: number) {
    for (let col = 0; col < 9; col++) {
      if (board[row][col] === num) {
        return false
      }
    }

    return true
  }

  //Cannot have the repeated numbers in the column
  function isColValid(board: Board, col: number, num: number) {
    for (let row = 0; row < 9; row++) {
      if (board[row][col] === num) {
        return false
      }
    }

    return true
  }

  //Cannot have the repeated numbers in inner square sector
  function isBoxValid(board: Board, row: number, col: number, num: number) {
    const startRow = row - (row % 3)
    const startCol = col - (col % 3)

    for (let row = 0; row < 3; row++) {
      for (let col = 0; col < 3; col++) {
        if (board[startRow + row][startCol + col] === num) {
          return false
        }
      }
    }

    return true
  }

  export type Vertex = { name: string; color: string | null; neighbours: Vertex[] }

  export type Graph = { vertices: Vertex[] }

  const visualizeGraph = (graph: Graph) =>
    graph.vertices.map(vertex => `Vertex ${vertex.name} has color: ${vertex.color} and has neighbors: ${vertex.neighbours.map(n => n.name).join(", ")}`)

  const canColor = (vertex: Vertex, color: string) =>
    vertex.neighbours.every(neighbour => neighbour.color !== color)

  const backtrack = (graph: Graph, vertexIndex: number, colors: string[]) => {
    if (vertexIndex === graph.vertices.length) {
      return true
    }

    const vertex = graph.vertices[vertexIndex]

    for (let color of colors) {
      if (canColor(vertex, color)) {
        vertex.color = color

        const nextVertex = vertexIndex + 1

        if (backtrack(graph, nextVertex, colors)) {
          return true
        }

        vertex.color = null
      }
    }

    return false
  }

  export const graphColoring = (graph: Graph, colors: string[]) => {
    const beforeColoring = visualizeGraph(graph)
    console.log(beforeColoring)

    backtrack(graph, 0, colors)

    const afterColoring = visualizeGraph(graph)
    console.log(afterColoring)

    return afterColoring
  };
}

const { solveNQueens, solveSudoku, graphColoring } = BacktrackAlgorithm

// - The n-queens algorithm places n chess queens on an n×n board so that no two queens threaten each other.
//   It uses a recursive backtracking approach to explore all possible solutions, placing one queen at a time and checking for conflicts.
//   If a conflict is found, the algorithm backtracks and tries a different placement. It continues this process until a valid solution is found or all possibilities have been explored.

// Example usage
const nQueensResult = solveNQueens(4)
//solutions return the queen position per row.
console.log(nQueensResult.solutions)
console.log(nQueensResult.board)
console.log(nQueensResult.log)
//============== Output:
/*
    0,1,0,0
    0,0,0,1
    1,0,0,0
    0,0,1,0

    0,0,1,0
    1,0,0,0
    0,0,0,1
    0,1,0,0
*/

// - The Sudoku solving algorithm fills a 9x9 grid with digits from 1 to 9 so that each row, column, and 3x3 sub-grid contains all the digits.
//   It uses a recursive backtracking approach to explore all possible solutions, placing one digit at a time and checking for conflicts.
//   If a conflict is found, the algorithm backtracks and tries a different digit. It continues this process until a valid solution is found or all possibilities have been explored.

const board: BacktrackAlgorithm.Board = [
  [0, 0, 0, 2, 6, 0, 7, 0, 1],
  [6, 8, 0, 0, 7, 0, 0, 9, 0],
  [1, 9, 0, 0, 0, 4, 5, 0, 0],
  [8, 2, 0, 1, 0, 0, 0, 4, 0],
  [0, 0, 4, 6, 0, 2, 9, 0, 0],
  [0, 5, 0, 0, 0, 3, 0, 2, 8],
  [0, 0, 9, 3, 0, 0, 0, 7, 4],
  [0, 4, 0, 0, 5, 0, 0, 3, 6],
  [7, 0, 3, 0, 1, 8, 0, 0, 0],
]

console.log(solveSudoku(board));

// - The graph coloring algorithm assigns colors to the vertices of a graph so that no two adjacent vertices share the same color.
//   It uses a greedy approach, assigning the first available color to each vertex and backtracking if a conflict arises until all vertices are colored.

const graph: BacktrackAlgorithm.Graph = {
  vertices: [
    { name: "A", color: null, neighbours: [] },
    { name: "B", color: null, neighbours: [] },
    { name: "C", color: null, neighbours: [] },
    { name: "D", color: null, neighbours: [] },
  ],
}

// Usage example
graph.vertices[0].neighbours.push(graph.vertices[1])
graph.vertices[1].neighbours.push(graph.vertices[0])
graph.vertices[1].neighbours.push(graph.vertices[2])
graph.vertices[2].neighbours.push(graph.vertices[1])
graph.vertices[2].neighbours.push(graph.vertices[3])
graph.vertices[3].neighbours.push(graph.vertices[2])

const colors = ["red", "green", "blue"]
const result = graphColoring(graph, colors)
console.log(result)