如何解决以下问题中的运行时错误?

发布于 2025-01-10 04:14:03 字数 3373 浏览 2 评论 0 原文

(Leetcode que 37)

数独求解器

编写一个程序,通过填充空单元格来解决数独难题。

数独解决方案必须满足以下所有规则:

数字 1-9 中的每个数字必须在每行中恰好出现一次。 数字 1-9 中的每个数字必须在每列中恰好出现一次。 每个数字 1-9 必须在网格的 9 个 3x3 子框中恰好出现一次。 这 '。'字符表示空单元格。

约束:

board.length == 9

board[i].length == 9

board[i][j] 是数字或“.”。

保证输入板只有一种解。

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

错误信息: ==32==错误:AddressSanitizer:地址 0x613000000550 在 pc 0x000000345984 bp 0x7ffc49a143f0 sp 0x7ffc49a143e8 上发生堆缓冲区溢出 在 0x613000000550 线程 T0 处读取大小 8 #2 0x7faad28ed0b2 (/lib/x86_64-linux-gnu/libc.so.6+0x270b2) 地址0x613000000550是一个野指针。 有缺陷的地址周围的影子字节: 0x0c267fff8050:发发发发发发发发发发发发发发发发发发发发发 0x0c267fff8060:发发发发发发发发发发发发发发发发发发发发发 0x0c267fff8070:发发发发发发发发发发发发发发发发发发发发发 0x0c267fff8080:发发发发发发发发发发发发发发发发发发发发发 0x0c267fff8090:发发发发发发发发发发发发发发发发发发发发发 =>0x0c267fff80a0: 发发发发发发发发发发发发发发发发发发发发发发发发发发发发发发发发发发发发发发发发发发发发发发发发发发发发发发发发发发发发发发发发发发发发发发发发发发发发发发发发发发发 0x0c267fff80b0:发发发发发发发发发发发发发发发发发发发发发 0x0c267fff80c0:发发发发发发发发发发发发发发发发发发发发发 0x0c267fff80d0:发发发发发发发发发发发发发发发发发发发发发 0x0c267fff80e0:发发发发发发发发发发发发发发发发发发发发发 0x0c267fff80f0:发发发发发发发发发发发发发发发发发发发发发 影子字节图例(1 个影子字节代表 8 个应用程序字节): 可寻址:00 部分可寻址:01 02 03 04 05 06 07 堆左红区:fa 释放的堆区域:fd 堆栈左红区:f1 堆栈中红区:f2 堆栈右红区:f3 返回后堆栈:f5 范围后的堆栈使用:f8 全局红区:f9 全局初始化顺序:f6 被用户中毒:f7 容器溢出:fc 数组cookie:ac 对象内红区:bb 峨山内部:fe 左分配红区:ca 右分配红区:cb 阴影间隙:cc ==32==正在中止

(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

如果你对这篇内容有疑问,欢迎到本站社区发帖提问 参与讨论,获取更多帮助,或者扫码二维码加入 Web 技术交流群。

扫码二维码加入Web技术交流群

发布评论

需要 登录 才能够评论, 你可以免费 注册 一个本站的账号。

评论(1

So尛奶瓶 2025-01-17 04:14:03

堆缓冲区溢出和影子字节被触及意味着您超出了程序中某处的范围,这会调用未定义的行为。由于这是关于堆溢出的,因此您的 std::vector 可能被错误地访问,可能在某个地方发生了差一错误。当您绝对确定自己在边界内时,可以使用 [] 访问向量,为了进行调试,您可以切换到 .at() 调用,该调用会进行边界检查,并会在触摸未初始化的内存时抛出异常。

我看到你有一个从 1 到 9 的 for 循环(i <= 9),这真的是正确的行为吗?由于你的棋盘在任何方向上都有 9 个位置,因此索引将从 0 到 8。触摸 [9] 会让所有东西爆炸。

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.

~没有更多了~
我们使用 Cookies 和其他技术来定制您的体验包括您的登录状态等。通过阅读我们的 隐私政策 了解更多相关信息。 单击 接受 或继续使用网站,即表示您同意使用 Cookies 和您的相关数据。
原文