洛谷P1784 数独 题解 Java版C++版

题解 Java版C++版"/>

洛谷P1784 数独 题解 Java版C++版

目录

• 题目描述
• 输入格式
• 输出格式
• 输入输出样例
• • 输入 #1
  • 输出 #1
• Java题解
• C++题解

题目描述

数独是根据9×9 盘面上的已知数字，推理出所有剩余空格的数字，并满足每一行、每一列、每一个粗线宫内的数字均含 1 - 9 ，不重复。每一道合格的数独谜题都有且仅有唯一答案，推理方法也以此为基础，任何无解或多解的题目都是不合格的。

芬兰一位数学家号称设计出全球最难的“数独游戏”，并刊登在报纸上，让大家去挑战。

这位数学家说，他相信只有“智慧最顶尖”的人才有可能破解这个“数独之谜”。

据介绍，目前数独游戏的难度的等级有一到五级，一是入门等级，五则比较难。不过这位数学家说，他所设计的数独游戏难度等级是十一，可以说是所以数独游戏中，难度最高的等级。他还表示，他目前还没遇到解不出来的数独游戏，因此他认为“最具挑战性”的数独游戏并没有出现。

输入格式

一个未填的数独。

输出格式

填好的数独。

输入输出样例

输入 #1

8 0 0 0 0 0 0 0 0
0 0 3 6 0 0 0 0 0
0 7 0 0 9 0 2 0 0
0 5 0 0 0 7 0 0 0
0 0 0 0 4 5 7 0 0
0 0 0 1 0 0 0 3 0
0 0 1 0 0 0 0 6 8
0 0 8 5 0 0 0 1 0
0 9 0 0 0 0 4 0 0

输出 #1

8 1 2 7 5 3 6 4 9
9 4 3 6 8 2 1 7 5
6 7 5 4 9 1 2 8 3
1 5 4 2 3 7 8 9 6
3 6 9 8 4 5 7 2 1
2 8 7 1 6 9 5 3 4
5 2 1 9 7 4 3 6 8
4 3 8 5 2 6 9 1 7
7 9 6 3 1 8 4 5 2

Java题解

import java.util.Scanner;/*** @author liangpeibin* @ClassName P1784* @Description P1784 数独* @since 2022/4/2 16:10*/
public class Main {/*** sudoku存储数独数据(9*9)* 下标从1到9,所以长度为10*/public static int[][] sudoku = new int[10][10];/*** row用于判断行重复* col用于判断列重复* phalanx用于判断方阵重复(3*3)* 如何判断属于哪个方阵？*/public static boolean[][] row = new boolean[10][10], col = new boolean[10][10], phalanx = new boolean[10][10];public static void main(String[] args) {Scanner sc = new Scanner(System.in);/*** 读数据*/for (int i = 1; i <= 9; i++){for (int j = 1; j <= 9; j++){int t = sc.nextInt();/*** 如果不为0则代表原来此位置存在数据* 找对应的行、列、方阵标记存在某个数字*/if (t != 0){row[i][t]= col[j][t]= phalanx[(i-1)/3*3+(j-1)/3+1][t]=true;}//在对应的位置进行赋值sudoku[i][j] = t;}}//从第一行，第一列进行搜索dfs(1,1);}/*** 输出方阵*/public static void print(){for (int i = 1; i <= 9; i++) {for (int j = 1; j <= 9; j++) {System.out.print(sudoku[i][j]+" ");}System.out.println();}}/*** 深搜* @param x 行* @param y 列*/public static void dfs(int x, int y){if (sudoku[x][y] != 0){//x=9 & y=9 证明填充完毕，进行输出if (x == 9 && y == 9){print();}else if (y == 9){//y=9 证明搜完这一行了，则进行下一行搜索dfs(x+1,1);}else {//搜索同一行的下个位置dfs(x,y+1);}}else {for (int i = 1; i <= 9; i++) {//判断同一行，同一列，同一方阵不存在i则进行填充if((!row[x][i])&&(!col[y][i])&&(!phalanx[(x-1)/3*3+(y-1)/3+1][i])){//填充！sudoku[x][y]=i;//打上标记。row[x][i]= col[y][i]= phalanx[(x-1)/3*3+(y-1)/3+1][i]=true;if(x==9&&y==9){//全部填完！输出~print();} else if(y==9){//搜下一行。dfs(x+1,1);} else {//搜下一列！dfs(x,y+1);}//恢复标记。sudoku[x][y]=0;//恢复标记。row[x][i]= col[y][i]= phalanx[(x-1)/3*3+(y-1)/3+1][i]=false;}}}}
}

C++题解

#include <bits/stdc++.h>
using namespace std;
int sd[10][10];
bool p[10][10],l[10][10],fz[10][10];
void _out()
{for(int i=1;i<=9;i++){	for(int j=1;j<=9;j++)cout<<sd[i][j]<<" ";cout<<endl;}exit(0); 
}
void dfs(int x,int y)
{if(sd[x][y]!=0) if(x==9&&y==9)_out();else if(y==9)dfs(x+1,1); else dfs(x,y+1);elsefor(int i=1;i<=9;i++)if((!p[x][i])&&(!l[y][i])&&(!fz[(x-1)/3*3+(y-1)/3+1][i])) {sd[x][y]=i;p[x][i]=l[y][i]=fz[(x-1)/3*3+(y-1)/3+1][i]=true;if(x==9&&y==9)_out();else if(y==9)dfs(x+1,1);else dfs(x,y+1);sd[x][y]=0; p[x][i]=l[y][i]=fz[(x-1)/3*3+(y-1)/3+1][i]=false;}
}
int main()
{for(int i=1;i<=9;i++)for(int j=1;j<=9;j++){int t;cin>>t;if(t!=0)p[i][t]=l[j][t]=fz[(i-1)/3*3+(j-1)/3+1][t]=true;	sd[i][j]=t;。 }	dfs(1,1);return 0;
}