[Java] BOJ 2580번 스도쿠

2580번: 스도쿠

---

풀이

재귀함수를 사용하여 해결했습니다.

이때, 스도쿠가 성립하는 경우가 여러개이므로 맨 처음 완성된 스도쿠만 출력하고 바로 종료하게하였습니다.

---

코드

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

public class Main {
	public static int[][] board;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = null;
		
		board = new int[9][9];
		
		for (int i = 0; i < 9; ++i) {
			st = new StringTokenizer(br.readLine(), " ");
			for (int j = 0; j < 9; ++j) {
				board[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		go(0, 0);
	}
	
	public static void go(int y, int x) {
		if (y == 9) {
			// 여러가지의 경우가 나올 수 있기때문에 처음 발견하면 출력하고 바로 정지한다.
			StringBuilder sb = new StringBuilder("");
			
			for (int i = 0; i < 9; ++i) {
				for (int j = 0; j < 9; ++j) {
					sb.append(board[i][j]).append(" ");
				}
				sb.append("\n");
			}
			
			System.out.println(sb);
			
			System.exit(0);
		}
		
		if (x == 9) {
			go(y + 1, 0);
			return;
		}
		
		if (board[y][x] == 0) {
			for (int i = 1; i <= 9; ++i) {
				if (!row(y, i) || !col(x, i) || !sqaure(y, x, i)) {
					continue;
				}
				
				board[y][x] = i;
				go(y, x + 1);
			}
			
			// 만약 모든 숫자를 다 넣었어도 안되는 경우가 있기때문에
			// 다시 이전 상태로 돌아가서 다음 검사를 하기 위해 다시 초기화
			board[y][x] = 0;
		}
		else {
			go(y, x + 1);
		}
	}
	
	// 가로 검사
	public static boolean row(int y, int num) {
		for (int i = 0; i < 9; ++i) {
			if (board[y][i] == num) {
				return false;				
			}
		}
		
		return true;
	}
	
	// 세로 검사
	public static boolean col(int x, int num) {
		for (int i = 0; i < 9; ++i) {
			if (board[i][x] == num) {
				return false;
			}
		}
		
		return true;
	}
	
	// 사각형 검사
	public static boolean sqaure(int y, int x, int num) {
		int ny = (y / 3) * 3;
		int nx = (x / 3) * 3;
		
		for (int i = ny; i < ny + 3; ++i) {
			for (int j = nx; j < nx + 3; ++j) {
				if (board[i][j] == num) {
					return false;
				}
			}
		}
		
		return true;
	}
}

---

pyo7410/Algorithm