CODEWITHSUNDEEP
javascriptarrays
Ciorap
Ciorap

Reputation: 23

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

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.

Upvotes: 2

Views: 307

Answers (3)

Alex L
Alex L

Reputation: 4241

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

Upvotes: 1

AJ_
AJ_

Reputation: 1485

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

Upvotes: 2

AKX
AKX

Reputation: 169378

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.

Upvotes: 5

Related Questions