[伯俊2580]斯多庫(JAVA)
質問する
https://www.acmicpc.net/problem/2580
に答える
バックグラウンドトラッキングで解決できます.水平線、垂直線、太い線の部分(1から9)を確認し、戻ります.
コード#コード#
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;
public class Main {
static boolean[][] x, y;
static boolean[][][] area;
static int[][] sudoku;
static ArrayList<Loc> empty = new ArrayList<>();
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
x = new boolean[9][10];
y = new boolean[9][10];
area = new boolean[3][3][10];
sudoku = new int[9][9];
for (int i = 0; i < 9; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
for (int j = 0; j < 9; j++) {
int num = Integer.parseInt(st.nextToken());
if (num > 0) {
sudoku[i][j] = num;
x[i][num] = true;
y[j][num] = true;
area[i/3][j/3][num] = true;
} else {
empty.add(new Loc(i, j));
}
}
}
check(0);
for (int[] ints : sudoku) {
for (int i : ints) {
sb.append(i).append(' ');
}
sb.append('\n');
}
System.out.println(sb);
br.close();
}
public static boolean check(int index) {
if (index == empty.size()) {
return true;
}
Loc loc = empty.get(index);
for (int i = 1; i <= 9; i++) {
if (x[loc.x][i] || y[loc.y][i] || area[loc.x / 3][loc.y / 3][i]) continue;
x[loc.x][i] = true;
y[loc.y][i] = true;
area[loc.x/3][loc.y/3][i] = true;
sudoku[loc.x][loc.y] = i;
if (check(index + 1)) return true;
x[loc.x][i] = false;
y[loc.y][i] = false;
area[loc.x/3][loc.y/3][i] = false;
sudoku[loc.x][loc.y] = 0;
}
return false;
}
public static class Loc {
int x, y;
public Loc(int x, int y) {
this.x = x;
this.y = y;
}
}
}
Reference
この問題について([伯俊2580]斯多庫(JAVA)), 我々は、より多くの情報をここで見つけました https://velog.io/@solser12/백준-2580-스도쿠-JAVAテキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol