POJ 2676 Sudoku深搜

xiaoxiao2021-03-01  8

题意:给你一个数独,然后填写,cell内是0的话就填入一个数字(1-9),每一行,每一列数字不能重复,3*3方块(不是每一个,看图就懂了,一共9个3*3)每一个数字不能重复。

想法:对于每一个cell,枚举1-9,然后填入判断行,列和3*3方块是否有重复数字,没有填入,有的话就换一个数字。然后任意输出一个解即可。

#include<stdio.h> #include<string.h> int sudoku[10][10]; char sudoku_char[15][15]; void init() { memset(sudoku_char, '\0', sizeof(sudoku_char)); } int get_lu(int x) { if(x >= 1 && x <= 3) return 1; if(x >= 4 && x <= 6) return 4; return 7; } bool Judge(int x, int y, int num) { int cnt = 0; for(int i = 1; i <= 9; ++i){ if(sudoku[x][i] == num) return false; if(sudoku[i][y] == num) return false; } int left_up_x = get_lu(x); int left_up_y = get_lu(y); for(int i = left_up_x; i <= left_up_x + 2; ++i){ for(int j = left_up_y; j <= left_up_y + 2; ++j){ if(sudoku[i][j] == num) return false; } } return true; } int DFS(int x, int y) { if(x == 10 && y == 10) return 1; if(y != 9) y %= 9; if(sudoku[x][y]){ if(DFS(x + y/9, y + 1)) return 1; } else{ for(int i = 1;i <= 9; ++i){ if(!Judge(x, y, i)) continue; sudoku[x][y] = i; if(DFS(x + y/9, y + 1)) return 1; sudoku[x][y] = 0; } } return 0; } int main() { int T; scanf("%d",&T); while(T--){ init(); for(int i = 1;i <= 9; ++i){ scanf("%s",sudoku_char[i] + 1); } for(int i = 1;i <= 9; ++i){ for(int j = 1;j <= 9; ++j){ sudoku[i][j] = sudoku_char[i][j] - '0'; } } DFS(1,1); for(int i = 1; i <= 9; ++i){ for(int j = 1; j <= 9; ++j){ printf("%d",sudoku[i][j]); } printf("\n"); } } return 0; }
转载请注明原文地址: https://www.6miu.com/read-3649949.html

最新回复(0)