[백준(Baekjoon)][자바(java)] 2580 : 스도쿠 / 백트래킹

 

www.acmicpc.net/problem/2580

2580번: 스도쿠

 

입력

아홉 줄에 걸쳐 한 줄에 9개씩 게임 시작 전 스도쿠판 각 줄에 쓰여 있는 숫자가 한 칸씩 띄워서 차례로 주어진다.

스도쿠 판의 빈 칸의 경우에는 0이 주어진다. 스도쿠 판을 규칙대로 채울 수 없는 경우의 입력은 주어지지 않는다.

 

출력

모든 빈 칸이 채워진 스도쿠 판의 최종 모습을 아홉 줄에 걸쳐 한 줄에 9개씩 한 칸씩 띄워서 출력한다.

스도쿠 판을 채우는 방법이 여럿인 경우는 그 중 하나만을 출력한다.

 

 

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

public class Main {
	
	static final int n = 9;
	static int board[][], blanks;
	static List<Cell> blankCells;
	
	static class Cell {
		int x, y;
		public Cell( int x, int y ) {
			 this.x = x;
			 this.y = y;
		}
	}
	
	public static void sudoku( int cnt ) {
		if( cnt == blanks ) {
			StringBuilder sb = new StringBuilder();
			int i, j;
			for( i = 0; i < n; i++ ) {
				for( j = 0; j < n; j++ )
					sb.append( board[i][j] + " " );
				sb.append("\n");
			}
			System.out.println( sb.toString() );  // print board
			System.exit(0);  // return; => all case
		}
		Cell c = blankCells.get( cnt );  // current cell
		int c_x = c.x, c_y = c.y;
		for( int num = 1; num <= n; num++ ) {
			if( isCorrect( c_x, c_y, num ) ) {
				board[c_x][c_y] = num;
				sudoku( cnt + 1 );
				board[c_x][c_y] = 0;
			}
		}
	}

	public static boolean isCorrect( int x, int y, int val ) {
		int i, j, nx = x < 3 ? 0 : x < 6 ? 3 : 6, ny = y < 3 ? 0 : y < 6 ? 3 : 6;
		for( i = 0; i < n; i++ )
			if( board[x][i] == val )
				return false;
		for( i = 0; i < n; i++ )
			if( board[i][y] == val )
				return false;
		for( i = nx; i < nx+3; i++ )
			for( j = ny; j < ny+3; j++ )
				if( board[i][j] == val )
					return false;
		return true;
	}
	
	public static void main(String[] args) throws IOException {
    
		BufferedReader br = new BufferedReader( new InputStreamReader(System.in) );
		StringTokenizer st;
		board = new int[n][n];			// board arr
		blankCells = new ArrayList<>();	// blank cells list
		int i, j, c;
		for( i = 0; i < n; i++ ) {
			st = new StringTokenizer( br.readLine() );
			for( j = 0; j < n; j++ ) {
				c = Integer.parseInt( st.nextToken() );
				board[i][j] = c;
				if( c == 0 ) 
					blankCells.add( new Cell( i, j ) );  // add blank cells in the list
			}
		}
		blanks = blankCells.size();  // the number of blank cells
		
		sudoku( 0 );
	}
}

 

보드판의 값들을 입력받을 때 빈 칸( 값이 0인 칸 )들은 리스트에 넣어놓고

그 안에서 백트래킹 하며 값이 될 수 있는 숫자를 찾아 나간다.

재귀 호출 종료 시 retrun 하면 가능한 모든 경우의 수가 구해지므로 System.exit(0) 하여 프로그램을 종료시킴