赞
踩
数独是一个我们都非常熟悉的经典游戏,运用计算机我们可以很快地解开数独难题,现在有一些简单的数独题目,请编写一个程序求解。
如有多解,输出一个解
输入描述:
输入9行,每行为空格隔开的9个数字,为0的地方就是需要填充的。
输出描述:
输出九行,每行九个空格隔开的数字,为解出的答案。
输入例子1:
输出例子1:
- import java.util.*;
- public class Main {
- private static boolean findAns = false;
- private static boolean check(int[][] dp, int row, int col, int val) {
- for(int i = 1; i < 10; i++) {
- if(val == dp[row][i]) {
- return false;
- }
- }
- for(int i = 1; i < 10; i++) {
- if(val == dp[i][col]) {
- return false;
- }
- }
- int rowLe = 1;
- while(rowLe + 3 <= row) {
- rowLe += 3;
- }
- int rowRi = rowLe + 3;
- int colLe = 1;
- while(colLe + 3 <= col) {
- colLe += 3;
- }
- int colRi = colLe + 3;
- for(int i = rowLe; i < rowRi; i++) {
- for(int j = colLe; j < colRi; j++) {
- if(rowLe == row && colLe == col) {
- continue;
- }
- if(val == dp[i][j]) {
- return false;
- }
- }
- }
- return true;
- }
- private static void dfs(int[][] dp, int row, int col) {
- if(col == 10) {
- row++;
- col = 1;
- }
- if(row == 10 && col == 1) {
- findAns = true;
- return;
- }
- if(dp[row][col] == 0) {
- for(int i = 1; i < 10; i++) {
- if(check(dp, row, col, i)) {
- dp[row][col] = i;
- dfs(dp, row, col + 1);
- if(findAns) {
- return;
- }
- dp[row][col] = 0;
- }
- }
- } else {
- dfs(dp, row, col + 1);
- }
- }
- private static void solve(Scanner sc) {
- int[][] dp = new int [10][10];
- for(int i = 1; i < 10; i++) {
- for(int j = 1; j < 10; j++) {
- dp[i][j] = sc.nextInt();
- }
- }
- findAns = false;
- dfs(dp, 1, 1);
- for(int i = 1; i < 10; i++) {
- System.out.print(dp[i][1]);
- for(int j = 2; j < 10; j++) {
- System.out.print(' ');
- System.out.print(dp[i][j]);
- }
- System.out.println();
- }
- }
- public static void main(String[] args) {
- Scanner sc = new Scanner(System.in);
- while(sc.hasNextInt()) {
- solve(sc);
- }
- }
- }
赞
踩
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。