c - 蛮力算法导致未定义的行为
问题描述
我必须为解决数独难题的作业创建一个程序。用户需要输入包含数字的二进制文件的名称（不是真正的二进制文件，它只是扩展名为 .bin，也可以用记事本、notepad++ 等打开）。这些数字代表拼图上的坐标以及这些坐标中包含的数字，例如 432 表示第 4 行第 3 列包含数字 2。填写拼图后，我需要解决它并将其打印在屏幕上。执行程序后它崩溃了，所以我决定使用一些开发人员认为最好的 MSVC 2017 调试器来查找和修复错误。这是我的代码：
数独.c
#include <stdio.h>
#include <stdlib.h>
#include "stdafx.h"
#include "sudokulib.h"
#define MALLOC_ERROR 0xFF
#define FILE_NOT_FOUND 0xFFF
#define ROWS 9
#define COLUMNS 9
int main(int argc, char ** argv)
{
char **matrix;
int i, args;
int row, column, num;
FILE * fp;
char * filename;
char * importedData;
matrix = (char **)malloc(ROWS * sizeof(char *));
if (!matrix)
exit(MALLOC_ERROR);
for (i = 0; i<ROWS; ++i)
{
matrix[i] = (char *)malloc(COLUMNS * sizeof(char));
if (!matrix[i])
exit(MALLOC_ERROR);
}
initSudoku(matrix);
printf ("Give me the name of data file: ");
filename = (char *)malloc(100 * sizeof(char));
if (!filename)
exit(MALLOC_ERROR);
scanf("%99s", filename);
fp = fopen(filename, "rb");
if (!fp)
{
printf ("File not found\n");
exit(FILE_NOT_FOUND);
}
importedData = (char *)malloc(sizeof(char)*ROWS*COLUMNS * 3);
if (!importedData)
exit (MALLOC_ERROR);
args = fread(importedData, 1, 243, fp);
i = 0;
while (importedData[i] != ' ' && importedData[i + 1] != ' ' && importedData[i + 2] != ' ' && importedData[i] >= '1' && importedData[i + 1] >= '1' && importedData[i + 2] >= '1' && importedData[i] <= '9' && importedData[i + 1] <= '9' && importedData[i + 2] <= '9' && i < 243)
{
row = importedData[i] - '0' - 1; /* Convert from ascii code to number */
column = importedData[i + 1] - '0' - 1;
num = importedData[i + 2] - '0';
matrix[row][column] = num;
i = i + 3;
}
printf("Sudoku after importing data:\n\n");
printSudoku(matrix);
system("pause");
if (solvePuzzle(matrix))
{
printSudoku(matrix);
}
else
printf ("Puzzle has no solution\n");
fclose(fp);
free(filename);
for (i = 0; i<9; ++i)
{
free(matrix[i]);
}
free(matrix);
return 0;
}
数独库
#pragma once
#include <stdlib.h>
#include <stdio.h>
/* Function Prototypes Begin Here */
void printSudoku(char **);
void initSudoku(char **);
int checkRow(char **, int, int);
int checkCol(char **, int, int);
int check3x3(char **, int, int, int);
int checkIfEmpty(char **, int*, int*);
int solvePuzzle (char **);
/* Function Prototypes End Here */
void printSudoku(char ** Mat)
{
int i, j;
for (i = 0; i<9; ++i)
{
printf ("-------------------\n");
printf("|");
for (j = 0; j<9; ++j)
{
printf("%d|", Mat[i][j]);
}
printf("\n");
}
printf ("-------------------\n");
}
void initSudoku(char ** Mat)
{
int i, j;
for (i = 0; i<9; ++i)
for (j = 0; j<9; ++j)
Mat[i][j] = 0;
}
int checkRow (char ** Mat, int row, int num) // if row is free returns 1 else returns 0
{
int col;
for (col = 0; col < 9; col++)
{
if (Mat[row][col] == num)
{
return 0;
}
}
return 1;
}
int checkCol (char ** Mat, int col, int num) // if column is free returns 1 else returns 0
{
int row;
for (row = 0; row < 9; row++)
{
if (Mat[row][col] == num)
{
return 0;
}
}
return 1;
}
int check3x3 (char ** Mat, int row, int col, int num) // if number doesnt exist in the 3x3 grid returns 1 else returns 0
{
row = (row / 3) * 3; // set to first row in the grid
col = (col / 3) * 3; // set to first col in the grid
int i;
int j;
for (i = 0; i < 3; i++) // grid is 3x3
{
for (j = 0; j < 3; j++)
{
if (Mat[row + i][col + j] == num)
{
return 0;
}
}
}
return 1;
}
int isValid (char ** Mat, int row, int col, int num)
{
return (checkRow(Mat, row, num) && checkCol(Mat, col, num) && check3x3(Mat, row, col, num));
}
int checkIfPuzzleSolved (char ** Mat, int *row, int *col) // if function finds a box empty (puzzle not solved) returns 0 else returns 1
{
for (*row = 0; *row < 9; *row++)
{
for (*col = 0; *col < 9; *col++)
{
printf("ROW: %d COL: %d\n",*row,*col);
if (Mat[*row][*col] == 0)
{
return 0;
}
}
}
return 1;
}
int solvePuzzle (char ** Mat)
{
int row;
int col;
if (checkIfPuzzleSolved(Mat, &row, &col))
{
return 1;
}
int num;
for (num = 1; num <= 9; num++)
{
//if (checkRow (Mat,row,num) && checkCol (Mat,col,num) && check3x3 (Mat,row,col,num))
if (isValid(Mat, row, col, num))
{
Mat[row][col] = num;
if (solvePuzzle(Mat))
return 1;
Mat[row][col] = 0;
}
}
return 0;
}
调试器在这个函数中发现了一个错误：
int checkIfPuzzleSolved (char ** Mat, int *row, int *col) // if function finds a box empty (puzzle not solved) returns 0 else returns 1
{
for (*row = 0; *row < 9; *row++)
{
for (*col = 0; *col < 9; *col++)
{
printf("ROW: %d COL: %d\n",*row,*col);
if (Mat[*row][*col] == 0) /* DEBUGGER ERROR CODE 0xC0000005: Access violation reading location 0xCDCA247C
{
return 0;
}
}
}
return 1;
}
让我困惑的两件事：
1）我不明白为什么solvePuzzle会在拼图中的第一个框（第一行第一列）被卡住。似乎checkIfPuzzleSolved认为第一个框是空的（包含 0），即使使用printSudoku我可以看到修改该框的算法将其值在 3 和 4 之间切换，并且显然是 0！= 3 和 0！= 4。
2）在屏幕checkIfPuzzleSolved上printf打印行号和列号，并不断产生以下结果：
ROW: 0 COL: 0
ROW: 0 COL: 0
ROW: 0 COL: -858993460
还使用调试器仔细检查了这一点，这些值确实是提到的那些。
我的思路如下：
1)checkIfEmpty用于判断一盒拼图是否包含 0，表示拼图尚未解开。row 和 col 变量是通过引用传入函数的，所以当函数找到一个空框并返回时，row 和 col 会保存空框的坐标。
2) 在循环中，调用checkRow,checkCol并check3x3检查是否可以在不违反数独规则的情况下将数字放入所需的框中。isValid是否出于可读性目的。
3)solvePuzzle递归调用，直到解开谜题，同时如果数字错误，将其重置为 0。
我已经尝试了我能想到的一切来解决这个问题，浪费了几个小时一次又一次地阅读我的代码以找到一个逻辑错误，但一切似乎都还好。有任何想法吗？
编辑：应 Michael Beer 的要求，这是一个示例二进制文件：
data.bin
142156177191216228257289311329364375418422441484534546562579625663682698739743787794824855883896917933951968
解决方案
*row++;解析为*(row++);，相当于 just row++。您正在增加指针，而不是计数器。– 美泊美尼
我懂了。那么我是否将指针增加 sizeof(int) 而不是将其引用的值增加 1？如果是这样，关于语法，编写“将您指向的地址的值增加 1”的正确方法是什么？
(*row)++或++(*row)或++*row或*row += 1。– 美泊美尼
推荐阅读
- javascript - React 中快速更新的进度条
- sql - 通过串行方法收集分区表的统计信息
- entity-framework - 如何从linq中的同一列表中减去金额
- javascript - 无法调用其类型缺少调用签名的表达式...没有兼容的调用签名
- spring - 在 SpringDataRest 中，如何在收到 http 请求时添加自定义逻辑
- amazon-web-services - 为什么我们应该只使用 s3 作为 AWS Glue 中的数据源？
- ocaml - 在 mirageos 中使用 C 库
- css - 保持 btn:focus 样式
- javascript - JavaScript - 在悬停时突出显示元素
- vba - VBA - 如何在表格中的文本中途开始选择