Why does the original array change when I change the copy?

Question

I'm trying to make a sudoku solver using backtracking and I ran into a problem. Whenever I change a copy of the grid array, the original changes too.

Can someone help me please?

The algorithm:

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);

I looked it up online and couldn't find any other answer than "use ... or slice", which I did, as you can see.

`[...grid]` is a **shallow** copy (as is a single `.map`, @lfaruki). — jonrsharpe, Jun 15 '20 at 13:50
Does this answer your question? [Modifying a copy of a JavaScript object is causing the original object to change](https://stackoverflow.com/questions/29050004/modifying-a-copy-of-a-javascript-object-is-causing-the-original-object-to-change) — ControlAltDel, Jun 15 '20 at 13:51
That's because of Javascript references. There is only one array and references to it. You need to [deep clone](https://stackoverflow.com/questions/4459928/how-to-deep-clone-in-javascript) your original array/object. — Jeremy Thille, Jun 15 '20 at 13:51
`let newGrid = [...grid];` is changing the outside array's reference, but the inner references are still the same. — M0nst3R, Jun 15 '20 at 13:52
Relevant: [Create copy of multi-dimensional array, not reference - JavaScript](https://stackoverflow.com/q/13756482) — VLAZ, Jun 15 '20 at 13:54

score 5 · Answer 1 · answered Jun 15 '20 at 13:51

5

Because

let newGrid = [...grid];

makes a shallow copy, and the sub-arrays aren't copied. You'll need a deep copy; for a simple array like this, an ugly and slow (but easy and effective) way is to round-trip via JSON:

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

If you don't want to do that, e.g. Lodash comes with a cloneDeep() function.

answered Jun 15 '20 at 13:51

AKX

152,115
15
115
172

God I hate that this is actually the best answer – jmkmay Jun 15 '20 at 13:53
@jmkmay define "best"? – VLAZ Jun 15 '20 at 13:55
@VLAZ correct, most elegant, most widely used, etc. – jmkmay Jun 15 '20 at 13:56
@jmkmay correct - check. Elegant - I wouldn't say so. Most widely used - because it's the shortest. There are also drawbacks to that easily remedied by making a simple function that will do the cloning. – VLAZ Jun 15 '20 at 13:57
Yea its not pretty, hence my comment – jmkmay Jun 15 '20 at 14:04

score 2 · Accepted Answer · answered Jun 15 '20 at 13:55

2

The problem is that the arrays inside newGrid are still the original arrays, you are just changing what array they are apart of. Try using .map()...

newGrid = grid.map(r => [...r])

answered Jun 15 '20 at 13:55

AJ_

1,455
8
10

score 1 · Answer 3 · answered Jun 15 '20 at 13:55

For your specific problem try this (shallow copy of each row is sufficient for your use case):

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.map(row => [...row]);

//mutate original grid:
grid[0][1] = 1;

//newGrid is not affected by above mutation
console.log("old", grid, "new", newGrid);

Why does the original array change when I change the copy?

3 Answers3