Как убрать повторяющиеся цифры (судоку)?

Для решения этой задачи, у нас есть несколько подходов. Мы можем использовать как алгоритмы на основе графов, так и алгоритмы на основе матрицы.

Один из наиболее эффективных способов решения этой задачи - использование алгоритма на основе матрицы.

Давайте разберемся, как мы можем решить эту задачу.

1) Создайте искомую матрицу размером 9х9, заполненную нулями.

2) Заполните эту матрицу значениями из судоку. Если значение уже присутствует в строке, столбце или квадрате 3х3, пропустите его и перейдите к следующему.

3) Создайте функцию, которая будет искать повторения в строке, столбце и квадрате 3х3.

4) Создайте вспомогательную функцию, которая будет проверять, есть ли уже значение в строке, столбце или квадрате 3х3.

5) Если значение уже существует, пропустите его и перейдите к следующему.

6) Повторяйте шаги 3-5 до тех пор, пока все значения не будут заполнены.

В результате выполнения этих шагов, мы получим судоку, в котором повторяющиеся цифры будут удалены.

Пример кода на TypeScript, реализующий этот алгоритм:

function removeDuplicates(sudoku: number[][]) {
  const n = sudoku.length;

  // Создание искомой матрицы
  const solvedSudoku: number[][] = [];
  for (let i = 0; i < n; i++) {
    const row = new Array(n).fill(0);
    solvedSudoku.push(row);
  }

  // Заполнение искомой матрицы
  for (let row = 0; row < n; row++) {
    for (let col = 0; col < n; col++) {
      const currVal = sudoku[row][col];
      if (isValid(solvedSudoku, row, col, currVal)) {
        solvedSudoku[row][col] = currVal;
      }
    }
  }

  return solvedSudoku;
}

// Функция проверки наличия повторений
function isValid(sudoku: number[][], row: number, col: number, num: number) {
  const n = sudoku.length;

  // Проверка наличия повторений в строке
  for (let i = 0; i < n; i++) {
    if (sudoku[row][i] === num) {
      return false;
    }
  }

  // Проверка наличия повторений в столбце
  for (let i = 0; i < n; i++) {
    if (sudoku[i][col] === num) {
      return false;
    }
  }

  // Проверка наличия повторений в квадрате 3х3
  const startRow = Math.floor(row / 3) * 3;
  const startCol = Math.floor(col / 3) * 3;
  for (let i = 0; i < 3; i++) {
    for (let j = 0; j < 3; j++) {
      if (sudoku[startRow + i][startCol + j] === num) {
        return false;
      }
    }
  }

  return true;
}

Теперь у вас есть алгоритм, который удаляет повторяющиеся цифры из судоку. Вы можете вызвать функцию removeDuplicates передав судоку в виде двумерного массива чисел.