白駿2580)数独

質問する

スドックは18世紀にスイスの数学者が作った「ラテン方形」とパズルに起源があり、現在人気がある.このゲームは下図のように横、縦各9個の81個の小格子の正方形板で行われ、ゲーム開始前の部分格子には1から9までの数字の1つが書かれています.
残りのスペースを埋める方法は次のとおりです.
各横線と縦線には、1～9の数字しか表示されません.
太い線で区切られた3×3正方形では、1～9の数字も1回しか現れません.
上記の例では、最初の行には1以外の2～9の数字が表示されているので、最初の行のスペースには1が含まれている必要があります.
また、上の真ん中にある3 x 3正方形については、3以外の数字が書かれているので、真ん中のスペースには3が含まれているはずです.
これにより、スペースを順番に入力すると、次の最終結果が得られます.
ゲームが始まる前に、数桁の情報が与えられると、プログラムを作成し、すべてのスペースの最終結果を出力します.

入力

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

しゅつりょく

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

入力例1

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

サンプル出力1

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

に答える

スドックは3つの部分を確認する必要があります.

だからこの部分を一列に並べました.

	static boolean[][] row = new boolean[10][10];
	static boolean[][] cul = new boolean[10][10];
	static boolean[][][] box = new boolean[3][3][10];

このrow[i][j]配列がtrueである場合、i番目にjが存在することを示す.
この問題で注意すべき点はarr[x][y]に数字を加えて
arr[x][y]=0を再初期化するタイミング.

インプリメンテーション

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	static int[][] arr = new int[9][9];
	static boolean[][] row = new boolean[10][10];
	static boolean[][] cul = new boolean[10][10];
	static boolean[][][] box = new boolean[3][3][10];


	public static void go(int x, int y) {
		if (x == 9) {
			for (int i = 0; i < 9; i++) {
				for (int j = 0; j < 9; j++) {
					System.out.print(arr[i][j] + " ");
				}
				System.out.println();
			}
			System.exit(0);
		}
		if (y == 9) {
			go(x + 1, 0);
			return;
		}
		if (arr[x][y] == 0) {
			for (int k = 1; k <= 9; k++) {
				if (cul[y][k] == false && row[x][k] == false && box[x / 3][y / 3][k] == false) {
					arr[x][y] = k;
					box[x / 3][y / 3][k] = true;
                                       //해당 숫자를 사용 못하게
					row[x][k] = true;
					cul[y][k] = true;
					go(x, y + 1);
                                        //해당 숫자를 사용 가능
					box[x / 3][y / 3][k] = false;
					row[x][k] = false;
					cul[y][k] = false;

				}
			}
			arr[x][y] = 0;	 //이 부분 중요!!
			return;
		}
		go(x, y + 1);
	}

	public static void main(String[] args) throws IOException {
		BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer tokenizer;
		arr = new int[9][9];
		for (int i = 0; i < 9; i++) {
			tokenizer = new StringTokenizer(reader.readLine());
			for (int j = 0; j < 9; j++) {
				arr[i][j] = Integer.parseInt(tokenizer.nextToken());
				row[i][arr[i][j]] = true;
				cul[j][arr[i][j]] = true;
				box[i / 3][j / 3][arr[i][j]] = true;
			}
		}
		go(0, 0);
	}
}