質問する

スドックは18世紀にスイスの数学者が作った「ラテン方形」とパズルに起源があり、現在人気がある.このゲームは下図のように横、縦各9個の81個の小格子の正方形板で行われ、ゲーム開始前の部分格子には1から9までの数字の1つが書かれています.

残りのスペースを埋める方法は次のとおりです.

の横線と縦線に1～9の数字しか表示されません.

の太い線で区切られた3 x 3正方形でも、1～9の数字は1回しか現れません.

上記の例では、最初の行には1以外の2～9の数字が表示されているので、最初の行のスペースには1が含まれている必要があります.

また、上の真ん中にある3 x 3正方形については、3以外の数字が書かれているので、真ん中のスペースには3が含まれているはずです.

これにより、スペースを順番に入力すると、次の最終結果が得られます.

ゲームが始まる前に、数桁の情報が与えられると、プログラムを作成し、すべてのスペースの最終結果を出力します.

入力

ゲームが始まる前に、9行まで数えて、9行まで数えて、数から数まで数えて、数から1行まで数えて、それから順番に与えます.数独版のスペースには0を指定します.シングルボードを規則的に充填できない場合は、入力は提供されません.

しゅつりょく

すべてのスペースを埋め尽くした数独版の最終像を、9行に分けて9行ずつ出力します.
数独板を充填する方法が多い場合は、そのうちの1つだけが出力されます.

制限

baekjoonの遡及アルゴリズムで解くことができる入力のみを与える.次に、アルゴリズムの実行時間を示します.

C++14: 80ms

Java: 292ms

PyPy3: 1172ms

に答える

この問題を遡及して解決するためには、再帰呼び出しの部分と適切な数を実現する必要がある.
check(map,x,y)という関数を作成して、適切な数値を追加します.
1.水平(行)に重複がないかチェックする
2.縦(列)に冗長性がないかチェックする
3.3 x 3矩形に重複する位置がないかチェックする
これら3つをチェックし、重複してfalse重複がない場合はtrueを返します.
次にbacktrackingセクションの再帰呼び出し関数について説明します.パラメータとして行(x)と列(y)の位置を受け入れます.
1.行が満たされている場合は、次の行の最初の列から開始します.
2.行と列が入力されている場合、出力後のシステム.exit(0); コール終了.
3.0に遭遇した場合、for文を1-9に移動し、check()がtrueの場合、その位置に値を入力し、backtracking関数を再度呼び出します.
4.map[x][y]=0は、戻りコードを含み、これは逆追跡方式で行われ、不適切な場所に遭遇した場合は元の位置に戻る.

ソース

import java.io.*;

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int[][] map = new int[9][9];

		for (int i = 0; i < 9; i++) {
			String[] str = br.readLine().split(" ");
			for (int j = 0; j < 9; j++) {
				map[i][j] = Integer.parseInt(str[j]);
			}
		}

		backtracking(map, 0, 0);

	}

	public static void backtracking(int[][] map, int x, int y) {

		// 해당 행이 다 채워진 상태라면 다음 행의 0번 열부터진행
		if (y == 9) {
			backtracking(map, x + 1, 0);
			return;
		}

		// 행과 열이 모두 채워지면 출력
		if (x == 9) {
			print(map);
			System.exit(0);
		}

		if (map[x][y] == 0) {
			for (int i = 1; i <= 9; i++) {
				if (check(map, x, y, i)) {
					map[x][y] = i;
					backtracking(map, x, y + 1);
				}
			}
			map[x][y] = 0;
			return;
		}

		backtracking(map, x, y + 1);
	}

	public static boolean check(int[][] map, int x, int y, int value) {

		// 행에 중복된 원소가 있는지 검사
		for (int i = 0; i < 9; i++) {
			if (map[x][i] == value) {
				return false;
			}
		}

		// 열에 중복된 원소가 있는지 검사
		for (int i = 0; i < 9; i++) {
			if (map[i][y] == value) {
				return false;
			}
		}

		// 3x3 사각형에 중복된 원소가 있는지 검사
		int row = (x / 3) * 3;
		int col = (y / 3) * 3;

		for (int i = row; i < row + 3; i++) {
			for (int j = col; j < col + 3; j++) {
				if (map[i][j] == value) {
					return false;
				}
			}
		}

		return true;

	}

	public static void print(int[][] map) {
		for (int i = 0; i < 9; i++) {
			for (int j = 0; j < 9; j++) {
				System.out.print(map[i][j] + " ");
			}
			System.out.println();
		}
	}

}