Tứ hậu

main.js

// Create new array width & height filled by 0
function initArray(width, height) {
  const arr = []

  for (let i = 0; i < height; i++) {
    const row = new Array(width).fill(0)
    arr.push(row)
  }

  return arr
}

// Find empty points
function findEmptyPoints(arr, width, height) {
  const points = []

  for (let i = 0; i < height; i++) {
    for (let j = 0; j < width; j++) {
      if (arr[i][j] == 0) {
        points.push({x: i, y: j})
      }
    }
  }

  return points
}

// Fill number to array
function fillNumber(arr, width, height, number, x, y) {
  // 1. Fill horizontal
  for (let j = 0; j < width; j++) {
    if (arr[x][j] == 0) {
      arr[x][j] = number;
    }
  }

  // 2. Fill vertical
  for (let i = 0; i < height; i++) {
    if (arr[i][y] == 0) {
      arr[i][y] = number;
    } 
  }

  // 3. Fill \
  // 3.1 Fill up
  for (let i = x, j = y; i >= 0 && j >= 0; i--, j--) {
    if (arr[i][j] == 0) {
      arr[i][j] = number;
    } 
  }
  // 3.2 Fill down
  for (let i = x, j = y; i < height && j < width; i++, j++) {
    if (arr[i][j] == 0) {
      arr[i][j] = number;
    } 
  }
  
  // 4. Fill /
  // 4.1 Fill up
  for (let i = x, j = y; i >= 0 && j < width; i--, j++) {
    if (arr[i][j] == 0) {
      arr[i][j] = number;
    }
  }
  // 4.2 Fill down
  for (let i = x, j = y; i < height && j >= 0; i++, j--) {
    if (arr[i][j] == 0) {
      arr[i][j] = number;
    }
  }
}

// Clear number in array
function clearNumber(arr, width, height, number) {
  for (let i = 0; i < height; i++) {
    for (let j = 0; j < width; j++) {
      if (arr[i][j] == number) {
        arr[i][j] = 0
      }
    }
  }
}

// Find solution
function findSolution(arr, width, height, currentPoint, totalPoint, points, solutions) {
  const emptyPoints = findEmptyPoints(arr, width, height)

  // Each empty point we can fill currentPoint, and if currentPoint >= totalPoint then we got a solution
  emptyPoints.forEach((point) => {
    points[currentPoint - 1] = point

    if (currentPoint >= totalPoint) {
      // We got a solution
      solutions.push(JSON.parse(JSON.stringify(points)))
      return
    } 

    // Fill number for current point
    fillNumber(arr, width, height, currentPoint, point.x, point.y)

    // Find next point
    const nextPoint = currentPoint + 1
    findSolution(arr, width, height, nextPoint, totalPoint, points, solutions)

    // Clear current attempt
    clearNumber(arr, width, height, currentPoint)
  })
}

// Make points signature
// 1. Sort points
// 2. Combine x and y
function makeSignature(points) {
  const sortedPoints = points.sort((p1, p2) => {
    if ((p1.x == p2.x) && (p1.y == p2.y)) {
      return 0
    }

    if ((p1.x < p2.x) || (p1.x == p2.x && p1.y < p2.y)) {
      return -1
    }

    return 1
  })

  const signature = sortedPoints.map((p) => `${p.x}.${p.y}`).join("_")
  return signature
}

// ---------------------------
// Main function
function main() {
  const width = 4
  const height = 4
  const totalPoint = 4
  const solutions = []
  const points = new Array(totalPoint)

  // Init array
  const arr = initArray(width, height)

  // Find solution
  const firstPoint = 1
  findSolution(arr, width, height, firstPoint, totalPoint, points, solutions)

  console.log("-----------------")
  console.log("Solutions: ", solutions)
  
  // --------------
  // If we want to find unique solutions
  const pointMap = solutions.reduce((acc, points) => {
    const signature = makeSignature(points)
    acc[signature] = points
    return acc
  }, {})
  const uniqueSolutions = Object.values(pointMap)
  console.log("-----------------")
  console.log("Unique Solutions: ", uniqueSolutions)
}  


main()