CODEWITHSUNDEEP
c++recursive-backtracking
Pranav Verma
Pranav Verma

Reputation: 3

How to resolve the runtime error in the following problem?

(Leetcode que 37)

Sudoku Solver

Write a program to solve a Sudoku puzzle by filling the empty cells.

A sudoku solution must satisfy all of the following rules:

Each of the digits 1-9 must occur exactly once in each row. Each of the digits 1-9 must occur exactly once in each column. Each of the digits 1-9 must occur exactly once in each of the 9 3x3 sub-boxes of the grid. The '.' character indicates empty cells.

Constraints:

board.length == 9

board[i].length == 9

board[i][j] is a digit or '.'.

It is guaranteed that the input board has only one solution.

https://upload.wikimedia.org/wikipedia/commons/thumb/f/ff/Sudoku-by-L2G-20050714.svg/250px-Sudoku-by-L2G-20050714.svg.png

class Solution {
public:
    
    bool insertionSafe(vector<vector<char>>& board, int row, int col, int num)
    {
        for(int k=0;k<9;k++)
        {
            if(board[row][k] == num)
            {
                return false;
            }
            
            if(board[k][col] == num)
            {
                return false;
            }
            
            int rowFactor = row - (row % 3);
            int colFactor = col - (col % 3);
            
            for(int i=rowFactor; i<rowFactor+3; i++)
            {
                for(int j=colFactor; j<colFactor+3; j++)
                {
                    if(board[i][j] == num)
                    {
                        return false;
                    }
                }
            }
        }
        
        return true;
    }
    
    bool solveSudokuHelper(vector<vector<char>>& board, int row, int col)
    {
        if(row == 9)
        {
            return true;
        }
        
        if(col == 9)
        {
            return solveSudokuHelper(board, row+1, 0);
        }
        
        if(board[row][col] != 0)
        {
            return solveSudokuHelper(board, row, col+1);
        }
        
        for(int k=1; k<=9; k++)
        {
            if(insertionSafe(board, row, col, k))
            {
                board[row][col] = k;
                if(solveSudokuHelper(board, row, col+1))
                {
                    return true;
                }
            }
            
            board[row][col] = 0;
        }
        
        return false;
    }
    
    void solveSudoku(vector<vector<char>>& board) {
        
        int row, col;
        solveSudokuHelper(board, row, col);
    }
};

Error Message: ==32==ERROR: AddressSanitizer: heap-buffer-overflow on address 0x613000000550 at pc 0x000000345984 bp 0x7ffc49a143f0 sp 0x7ffc49a143e8 READ of size 8 at 0x613000000550 thread T0 #2 0x7faad28ed0b2 (/lib/x86_64-linux-gnu/libc.so.6+0x270b2) Address 0x613000000550 is a wild pointer. Shadow bytes around the buggy address: 0x0c267fff8050: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa 0x0c267fff8060: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa 0x0c267fff8070: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa 0x0c267fff8080: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa 0x0c267fff8090: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa =>0x0c267fff80a0: fa fa fa fa fa fa fa fa fa fa[fa]fa fa fa fa fa 0x0c267fff80b0: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa 0x0c267fff80c0: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa 0x0c267fff80d0: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa 0x0c267fff80e0: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa 0x0c267fff80f0: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa Shadow byte legend (one shadow byte represents 8 application bytes): Addressable: 00 Partially addressable: 01 02 03 04 05 06 07 Heap left redzone: fa Freed heap region: fd Stack left redzone: f1 Stack mid redzone: f2 Stack right redzone: f3 Stack after return: f5 Stack use after scope: f8 Global redzone: f9 Global init order: f6 Poisoned by user: f7 Container overflow: fc Array cookie: ac Intra object redzone: bb ASan internal: fe Left alloca redzone: ca Right alloca redzone: cb Shadow gap: cc ==32==ABORTING

Upvotes: 0

Views: 140

Answers (1)

wild-ptr
wild-ptr

Reputation: 100

heap-buffer-overflow and shadow bytes being touched means you go out of bounds somewhere in your program, which invokes undefined behaviour. Since this is about heap overflow, your std::vector is probably accessed incorrectly, probably an off-by-one error happens somewhere. Accessing vectors with [] is to be used when you are absolutely sure you are in bounds, for debugging you can switch to .at() call, which does bounds checking and will throw on touching uninitialized memory.

I see you have a for loop going from 1 to 9 inclusive (i <= 9), is this really correct behaviour? Since your board has 9 places in any direction, the indices will be from 0 to 8. Touching [9] would make everything explode then.

Upvotes: 0

Related Questions