为什么当我更改副本时原始数组会更改？

Question

我正在尝试使用回溯法制作数独求解器，但遇到了问题。每当我更改网格数组的副本时，原始数组也会更改。

有人能帮助我吗？

算法：

let grid = [
   [0, 0, 0, 0, 0, 0, 0, 0, 0],
   [0, 0, 0, 0, 0, 0, 0, 0, 0],
   [0, 0, 0, 0, 0, 0, 0, 0, 0],
   [0, 0, 0, 0, 0, 0, 0, 0, 0],
   [0, 0, 0, 0, 0, 0, 0, 0, 0],
   [0, 0, 0, 0, 0, 0, 0, 0, 0],
   [0, 0, 0, 0, 0, 0, 0, 0, 0],
   [0, 0, 0, 0, 0, 0, 0, 0, 0],
   [0, 0, 0, 0, 0, 0, 0, 0, 0],
];

// make a copy of the grid
let newGrid = [...grid];

// a vqriable that becomes true if we find a solution to the puzzle
let found = false;

// this function checks if the current choice for grid[row][col] is valid
const valid = (row, col) => {
   // check the row for the same number
   for (let j = 0; j < 9; j++)
      if (newGrid[row][col] === newGrid[row][j] && j !== col) return false;

   // check the column
   for (let i = 0; i < 9; i++)
      if (newGrid[row][col] === newGrid[i][col] && i !== row) return false;

   // check the smaller "box"

   // the number of the box that the current element is in
   const verticalNumber = Math.floor(row / 3);
   const horizontalNumber = Math.floor(col / 3);

   // iterate through the whole grid
   for (let i = 0; i < 9; i++)
      for (let j = 0; j < 9; j++) {
         const vertical = Math.floor(i / 3);
         const horizontal = Math.floor(j / 3);

         // if the elements are not in the same box or the element is the current element, skip it
         if (
            vertical !== verticalNumber ||
            horizontal !== horizontalNumber ||
            (i === row && j === col)
         )
            continue;

         if (newGrid[i][j] === newGrid[row][col]) return false;
      }

   // otherwise it's okay
   return true;
};

// this function checks if the algorithm is finished
const stop = (row, col) => {
   return row > 8;
};

const backtracking = (row, col) => {
   if (found) return;
   // if the algorithm finished, print the completed puzzle
   if (stop(row, col)) {
      console.log(newGrid);
      found = true;
      return;
   }

   // if the current cell already has a number, skip it
   if (grid[row][col]) {
      if (col === 8) backtracking(row + 1, 0);
      else backtracking(row, col + 1);

      // otherwise check every single posibility, and if it is valid go to the next cell
   } else {
      for (let i = 1; i <= 9 && !found; i++) {
         newGrid[row][col] = i;
         console.log(newGrid[row][col] === grid[row][col]);
         if (valid(row, col)) {
            if (col === 8) backtracking(row + 1, 0);
            else backtracking(row, col + 1);
         }
      }
   }
};


backtracking(0,0);

我在网上查了一下，除了“使用......或切片”之外找不到任何其他答案，正如你所看到的那样。

Answer 1

因为

let newGrid = [...grid];

进行浅拷贝，并且不复制子数组。你需要一个深拷贝；对于像这样的简单数组，一种丑陋而缓慢（但简单有效）的方法是通过 JSON 进行往返：

let newGrid = JSON.parse(JSON.stringify(grid));

如果您不想这样做，例如 Lodash 带有一个cloneDeep()函数。