I have a stupid bug in my code and I could not figure out for hours. My brain is about to stop.

I am solving sudoku solver. solved in javascript but I have a bug in python for loop. simple for loop producing different result. i need help please.

in javascript

const getBoxId = function (row, col) {
  const rowVal = Math.floor(row / 3) * 3;
  const colVal = Math.floor(col / 3);
  return rowVal   colVal;
};

var solveSudoku = function (board) {
  const n = board.length;
  const boxes = new Array(n),
    rows = new Array(n),
    cols = new Array(n);
  for (let i = 0; i < n; i  ) {
    boxes[i] = {};
    rows[i] = {};
    cols[i] = {};
    console.log(boxes);
  }
  for (let r = 0; r < n; r  ) {
    for (let c = 0; c < n; c  ) {
      // if a cell does not equal to "."
      if (board[r][c] !== ".") {
        const boxId = getBoxId(r, c);
        const val = board[r][c];
        boxes[boxId][val] = true;
        rows[r][val] = true;
        cols[c][val] = true;
        console.log(rows);
      }
    }
  }
};

board = [
  ["5", "3", ".", ".", "7", ".", ".", ".", "."],
  ["6", ".", ".", "1", "9", "5", ".", ".", "."],
  [".", "9", "8", ".", ".", ".", ".", "6", "."],
  ["8", ".", ".", ".", "6", ".", ".", ".", "3"],
  ["4", ".", ".", "8", ".", "3", ".", ".", "1"],
  ["7", ".", ".", ".", "2", ".", ".", ".", "6"],
  [".", "6", ".", ".", ".", ".", "2", "8", "."],
  [".", ".", ".", "4", "1", "9", ".", ".", "5"],
  [".", ".", ".", ".", "8", ".", ".", "7", "9"],
];

console.log(solveSudoku(board));

this is the "rows" in javascript

[
  { '3': true, '5': true, '7': true },
  { '1': true, '5': true, '6': true, '9': true },
  { '6': true, '8': true, '9': true },
  { '3': true, '6': true, '8': true },
  { '1': true, '3': true, '4': true, '8': true },
  { '2': true, '6': true, '7': true },
  { '2': true, '6': true, '8': true },
  { '1': true, '4': true, '5': true, '9': true },
  { '7': true, '8': true, '9': true }
]

Here is the headache part. Implementing same code in python;

import math
def get_box_id(r,c):
    row=int(math.floor(r/3)*3)
    col=int(math.floor(c/3))
    return row col
def solve_sudoku(board):
    n=len(board)
    rows=[{}]*n
    cols=[{}]*n
    boxes=[{}]*n
    for r in range(n):
        for c in range(n):  
            if board[r][c]!='.':
                box_id=get_box_id(r,c)     
                val=board[r][c]
                boxes[box_id][val]=True
                rows[r][val]=True
                cols[c][val]=True
                print(rows)
solve_sudoku(board) # same board as above

after 81 iteration, I am getting this:

    [{'5': True, '3': True, '7': True, '6': True, '1': True, '9': True, '8': True, '4': True, '2': True}, 
{'5': True, '3': True, '7': True, '6': True, '1': True, '9': True, '8': True, '4': True, '2': True}, {'5': True, '3': True, '7': True, '6': True, '1': True, '9': True, '8': True, '4': True, '2': True}, 
{'5': True, '3': True, '7': True, '6': True, '1': True, '9': True, '8': True, '4': True, '2': True}, 
{'5': True, '3': True, '7': True, '6': True, '1': True, '9': True, '8': True, '4': True, '2': True}, 
{'5': True, '3': True, '7': True, '6': True, '1': True, '9': True, '8': True, '4': True, '2': True}, 
{'5': True, '3': True, '7': True, '6': True, '1': True, '9': True, '8': True, '4': True, '2': True}, 
{'5': True, '3': True, '7': True, '6': True, '1': True, '9': True, '8': True, '4': True, '2': True}, 
{'5': True, '3': True, '7': True, '6': True, '1': True, '9': True, '8': True, '4': True, '2': True}]

CodePudding user response：

You just need to replace [{}]*n with [{} for i in range(n)]

Because both of them work differently:

list_a = [{}] * 9  # creating copy with reference to the same object {}

print(list_a)  # [{}, {}, {}, {}, {}, {}, {}, {}, {}]

#changing first object in the list
list_a[0]['hello'] = 'bye'

print(list_a) 

# output of above print statement
# [{'hello': 'bye'}, {'hello': 'bye'}, {'hello': 'bye'}, {'hello': 'bye'}, {'hello': 'bye'}, {'hello': 'bye'}, {'hello': 'bye'}, {'hello': 'bye'}, {'hello': 'bye'}]




# now try this

list_b = [{} for i in range(9)]

print(list_b) # [{}, {}, {}, {}, {}, {}, {}, {}, {}] 

list_b[0]['hello'] = 'bye'

print(list_b)

# output of above print statement 
# [{'hello': 'bye'}, {}, {}, {}, {}, {}, {}, {}, {}]

CodePudding user response：

Please try the following code and check if it helps.

import math
def get_box_id(r,c):
    row=int(math.floor(r/3)*3)
    col=int(math.floor(c/3))
    return row col
def solve_sudoku(board):
    n=len(board)
    rows=[{} for i in range (n)]
    cols=[{} for i in range (n)]
    boxes=[{} for i in range (n)]
    for r in range(n):
        for c in range(n):  
            if board[r][c]!='.':
                box_id=get_box_id(r,c)
                val=board[r][c]
                boxes[box_id][val]=True
                rows[r][val]=True
                cols[c][val]=True
    
    print(rows)
    
solve_sudoku(board) # same board as above

Update:

More info on the changes.

Change #1

changed [{}] * n to [{} for i in range (n)] because [{}] * n makes a list with n references to the same {} source.

Change #2

printing the rows when all the processing completed (this is only done to see all the rows after processing).