游戏规则:数独是源自18世纪瑞士的一种数学游戏。
玩家需要根据9×9盘面上的已知数字,推理出所有剩余空格的数字,
并满足每一行、每一列、每一个粗线宫(3*3)内的数字均含1-9,不重复。
在本项目中,需要对1000道数独问题进行求解,在保证解的正确性的前提下,
保证程序的运行时间少于模拟端程序(运行时间约200秒)。
我只能完成主体部分,对数独进行运算解答,但是无法完成将题目自动导入和输出功能,各位有没有什么办法帮忙
#include <iostream>
#include <string>
using namespace std;
int a[10][10];//存储数字
int is_row_col_repeat(int row,int col,int num){//判断行列是否重复
//判断行是否重复
for (int i=1;i<=9;i++) {
if (a[row][i]==num) {
return 0;//行重复,返回0
}
}
//判断列是否重复
for (int i=1;i<=9;i++) {
if (a[i][col]==num) {
return 0;//列重复,返回0
}
}
return 1;//行列不重复,返回1
}
int check_row_range(int row){//判断行的范围
if (row>=1 && row<=3) {
return 1;
}else if(row>=4&&row<=6){
return 4;
}else {
return 7;
}
}
int check_col_range(int col){//判断列的范围
if(col>=1&&col<=3){
return 1;
}else if (col>=4&&col<=6) {
return 4;
}else {
return 7;
}
}
int is_block_repeat(int row,int col,int num){//判断同色九宫格是否重复
int x,y;
x=check_row_range(row);
y=check_col_range(col);
for (int i=x;i<=x+2;i++) {
for (int j=y;j<=y+2;j++) {
if (a[i][j]==num) {
return 0;//重复,返回0
}
}
}
return 1;//不重复,返回1
}
void dfs(int row,int col){
if (row>9) {//如果行超出9行,直接输出
for (int i=1;i<=9;i++) {
for (int j=1;j<=9;j++) {
printf("%d",a[i][j]);
}
printf("\n");
}
exit(0);
}
if (a[row][col]==0) {//如果没有填数字
for (int i=1;i<=9;i++) {
if (is_row_col_repeat(row, col, i) && is_block_repeat(row, col, i)) {//如果行列九宫格不重复
a[row][col]=i;//填充数字
dfs(row+(col+1)/10, (col+1)%10);//继续搜索
}
}
a[row][col]=0;//重新置为0
}else{//如果已经填了,继续搜索
dfs(row+(col+1)/10, (col+1)%10);
}
}
int main(int argc, char *argv[]) {
string s;
for(int i=1;i<=9;i++){
cin >> s;//输入字符串
for(int j=1;j<=9;j++){
char ss=s.at(j-1);//取s的第j-1的字符
a[i][j]=ss-'0';//将ss转化为整数
}
}
dfs(1,1);
return 0;
}
其对比的程序是这样的
```c++
/*
* 数独学生端程序
* 左妍
* 计算机科学与技术系
* 2017/6/12
*/
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#define ROW 9
#define COL 9
#define CORRECT 0
#define WRONG -1
#define MAXNUM 1000 /*数独游戏个数*/
int checkSudoku(const char a[][COL]){
int i,j,x,y;
for( i = 0; i < ROW ; i++){
for(j = 0 ; j < COL ; j++){
for(x = 0 ; x < COL ; x++)
if(a[i][x] == a[i][j] && x != j )
return WRONG;
for(x = 0 ; x < ROW ; x++)
if(a[x][j] == a[i][j] && x != i )
return WRONG;
for(x = i/3*3 ; x < i/3*3+3 ; x ++)
for(y = j/3*3 ; y < j/3*3+3 ; y++)
if(a[x][y] == a[i][j] && (x != i && y != j))
return WRONG;
}
}
return CORRECT;
}
void printSudoku(const char a[][COL]){
int i,j;
printf("\n ┌────┬────┬────┐\n");
for( i = 0 ; i < ROW ; i++){
if(i != 0 && i%3 == 0) printf(" ├────┼────┼────┤\n");
printf(" │");
for( j = 0 ; j < COL ; j++){
if(j != 0 && j%3 == 0) printf(" │");
if(a[i][j])
printf(" %d",a[i][j]);
else printf(" ");
}
printf(" │\n");
}
printf(" └────┴────┴────┘\n");
}
void readFromFile(char a[][COL], const char filename[]){
// To Be Solved
// 从文件filename中读取到的数独初盘存储到数组a[][COL]中
}
void solveSudoku(const char a[][COL], char b[][COL]){
// To Be Solved
// 参数const char a[][COL]表示初盘二维数组;
// 参数char b[][COL]表示解的二维数组。
}
int main(){
char starting_grid[ROW][COL]={0};
char result[ROW][COL]={0};
char filename[50];
int rr;
double time_from, time_to, time_sum = 0;
int i;
for( i = 0; i < MAXNUM ; i++){
sprintf(filename,"sudoku\\%04d.txt",i);
readFromFile(starting_grid,filename);
printf("\n\n *%4d *",i);
printSudoku(starting_grid);
time_from = clock();
solveSudoku(starting_grid,result);
time_to = clock();
time_sum += time_to - time_from;
printSudoku(result);
rr = checkSudoku(result);
if( rr == WRONG){
printf("Something goes wrong...\n");
return WRONG;
}
else printf(" Correct!!!\n");
printf(" ==============================");
}
printf("\n Congretulations! ToTal Time:%fs\n",time_sum / CLOCKS_PER_SEC);
return 0;
}
大哥,能帮我看下这两部分代码怎么运行吗,实在是不会弄啊
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#define ROW 9
#define COL 9
#define CORRECT 0
#define WRONG -1
#define MAXNUM 1000 /数独游戏个数/
int checkSudoku(const char a[][COL]){
int i,j,x,y;
for( i = 0; i < ROW ; i++){
for(j = 0 ; j < COL ; j++){
for(x = 0 ; x < COL ; x++)
if(a[i][x] == a[i][j] && x != j )
return WRONG;
for(x = 0 ; x < ROW ; x++)
if(a[x][j] == a[i][j] && x != i )
return WRONG;
for(x = i/3*3 ; x < i/3*3+3 ; x ++)
for(y = j/3*3 ; y < j/3*3+3 ; y++)
if(a[x][y] == a[i][j] && (x != i && y != j))
return WRONG;
}
}
return CORRECT;
}
void printSudoku(const char a[][COL]){
int i,j;
printf("\n ┌────┬────┬────┐\n");
for( i = 0 ; i < ROW ; i++){
if(i != 0 && i%3 == 0) printf(" ├────┼────┼────┤\n");
printf(" │");
for( j = 0 ; j < COL ; j++){
if(j != 0 && j%3 == 0) printf(" │");
if(a[i][j])
printf(" %d",a[i][j]);
else printf(" ");
}
printf(" │\n");
}
printf(" └────┴────┴────┘\n");
}
void readFromFile(char a[][COL], const char filename[]){
// To Be Solved
// 从文件filename中读取到的数独初盘存储到数组a[][COL]中
}
void solveSudoku(const char a[][COL], char b[][COL]){
// To Be Solved
// 参数const char a[][COL]表示初盘二维数组;
// 参数char b[][COL]表示解的二维数组。
}
int main(){
char starting_grid[ROW][COL]={0};
char result[ROW][COL]={0};
char filename[50];
int rr;
double time_from, time_to, time_sum = 0;
int i;
for( i = 0; i < MAXNUM ; i++){
sprintf(filename,"sudoku\%04d.txt",i);
readFromFile(starting_grid,filename);
printf("\n\n *%4d *",i);
printSudoku(starting_grid);
time_from = clock();
solveSudoku(starting_grid,result);
time_to = clock();
time_sum += time_to - time_from;
printSudoku(result);
rr = checkSudoku(result);
if( rr == WRONG){
printf("Something goes wrong...\n");
return WRONG;
}
else printf(" Correct!!!\n");
printf(" ==============================");
}
printf("\n Congretulations! ToTal Time:%fs\n",time_sum / CLOCKS_PER_SEC);
return 0;
}
#include<stdio.h>
#include<stdlib.h>
#include<sys/stat.h>
#define ROW 9
#define COL 9
#define CORRECT 0
#define WRONG -1
#define MAXNUM 1000 /数独个数/
#define SEED 20171212 /随机数生成种子/
unsigned int seed = SEED;
int Digit(char a[][COL], int i, int j){ /递归填充数独元素/
if(i < ROW && j < COL){
int x,y,k;
char check[COL+1]={CORRECT};/用于排除已经使用过的的数字/
for(x = 0 ; x < i ; x++)
check[a[x][j]] = WRONG;
for(x = 0 ; x < j ; x++)
check[a[i][x]] = WRONG;
for(x = i/33 ; x <= i; x++){
if(x == i)
for(y = j/33 ; y < j; y++)
check[a[x][y]] = WRONG;
else
for(y = j/33 ; y < j/33 + 3; y++)
check[a[x][y]] = WRONG;
}
int flag = 0;
for(k = 1; k <= COL && flag == 0 ; k++){/从check数组中查找安全的数字/
if(check[k] == CORRECT){
flag = 1;
a[i][j] = k;
if(j == COL-1 && i != ROW-1){
if(Digit(a,i+1,0) == CORRECT) return CORRECT;
else flag = 0;
}
else if(j != COL-1){
if(Digit(a,i,j+1) == CORRECT) return CORRECT;
else flag = 0;
}
}
}
if( flag == 0 ){
a[i][j] = 0;
return WRONG;
}
}
return CORRECT;
}
void randomFirstRow(char a0[], int n){/随机生成第一行/
int i,j;
srand(seed++);
for( i = 0 ; i < n ; i++){
a0[i] = rand()%9 + 1;
j = 0 ;
while(j < i){
if(a0[i] == a0[j]){
a0[i] = rand()%9 + 1;
j = 0;
}
else j++;
}
}
}
void createSudoku(char a[][COL]){ /生成数独/
randomFirstRow(a[0],COL);
Digit(a,1,0);
}
void createStartinggrid(const char a[][COL], char b[][COL], int numDigits){/随机生成初盘/
int i,j,k;
srand(seed ++);
for( i = 0; i < ROW ; i ++)
for( j = 0; j < COL ; j++)
b[i][j] = a[i][j];
char c[numDigits][2];
int m,flag = 0;
for( i = 0; i < numDigits ; i++){
j = rand()%9;
k = rand()%9;
flag = 0;
for(m = 0; m < i ; m++)
if( j == c[m][0] && k == c[m][1])
flag = 1;
if(flag == 0){
b[j][k] = 0;
c[i][0] = j;
c[i][1] = k;
}
else
i--;
}
}
int checkSudoku(const char a[][COL]){/检查函数/
int i,j,x,y;
for( i = 0; i < ROW ; i++){
for(j = 0 ; j < COL ; j++){
for(x = 0 ; x < COL ; x++)
if(a[i][x] == a[i][j] && x != j )
return WRONG;
for(x = 0 ; x < ROW ; x++)
if(a[x][j] == a[i][j] && x != i )
return WRONG;
for(x = i/3*3 ; x < i/3*3+3 ; x ++)
for(y = j/3*3 ; y < j/3*3+3 ; y++)
if(a[x][y] == a[i][j] && (x != i && y != j))
return WRONG;
}
}
return CORRECT;
}
void printToFile(const char a[][COL], const char filename[]){/打印数独数组到文件/
FILE * fp;
int i,j;
fp = fopen(filename,"w");
for( i = 0 ; i < ROW ; i++){
for( j = 0 ; j < COL ; j++)
fprintf(fp , "%d ", a[i][j]);
fprintf(fp , "\n");
}
fclose(fp);
}
void createSudokuToFile(void){/生成数独初盘到文件中/
char sudoku[ROW][COL]={0};
char starting_grid[ROW][COL]={0};
char filename[50];
int i;
mkdir("sudoku");
for( i = 0; i < MAXNUM ; i++){
createSudoku(sudoku);
createStartinggrid(sudoku,starting_grid,i%81+1);
sprintf(filename,"sudoku\\%04d.txt",i);
printToFile(starting_grid,filename);
}
}
int main(){
createSudokuToFile();
}