Nothing is Impossible ::

[Backtracking] 자바로 푼 스도쿠 퍼즐

Program/Algorithm 2012/04/16 16:57

Applet을 사용하여 시각적으로 어떻게 해를 찾아가는지 답을 보여준다.

solve 함수를 재귀호출(recursive)하여 답을 구하며 전체 모든 답이 구해지면 Exception을 발생하여 프로세스를 끝낸다.

1초(1000)단위로 셀값이 변하는데 답답해 보인다면 Thread.sleep() 수치를 낮춰서 테스트 하면 된다.

SimplifiedSudoku^[각주:1]

import java.applet.* ;
import java.awt.* ;

/**
 * Solves a sudoku puzzle by recursion and backtracking
 */
public class SimplifiedSudoku extends Applet implements Runnable {
	/** The model */
	protected int model[][] ;

/** The view */
	protected Button view[][] ;

/** Creates the model and sets up the initial situation */
	protected void createModel() {
		model = new int[9][9] ;

// Clear all cells
		for( int row = 0; row < 9; row++ )
			for( int col = 0; col < 9; col++ )
				model[row][col] = 0 ;

// Create the initial situation
		model[0][0] = 9 ;
		model[0][4] = 2 ;
		model[0][6] = 7 ;
		model[0][7] = 5 ;

model[1][0] = 6 ;
		model[1][4] = 5 ;
		model[1][7] = 4 ;

model[2][1] = 2 ;
		model[2][3] = 4 ;
		model[2][7] = 1 ;

model[3][0] = 2 ;
		model[3][2] = 8 ;

model[4][1] = 7 ;
		model[4][3] = 5 ;
		model[4][5] = 9 ;
		model[4][7] = 6 ;

model[5][6] = 4 ;
		model[5][8] = 1 ;

model[6][1] = 1 ;
		model[6][5] = 5 ;
		model[6][7] = 8 ;

model[7][1] = 9 ;
		model[7][4] = 7 ;
		model[7][8] = 4 ;

model[8][1] = 8 ;
		model[8][2] = 2 ;
		model[8][4] = 4 ;
		model[8][8] = 6 ;
	}

/** Creates an empty view */
	protected void createView() {
		setLayout( new GridLayout(9,9) ) ;

view = new Button[9][9] ;

// Create an empty view
		for( int row = 0; row < 9; row++ )
			for( int col = 0; col < 9; col++ ) {
				view[row][col]  = new Button() ;
				add( view[row][col] ) ;
			}
	}

/** Updates the view from the model */
	protected void updateView() {
		for( int row = 0; row < 9; row++ )
			for( int col = 0; col < 9; col++ )
				if( model[row][col] != 0 )
					view[row][col].setLabel( String.valueOf(model[row][col]) ) ;
				else
					view[row][col].setLabel( "" ) ;
	}

/** This method is called by the browser when the applet is loaded */
	@Override
	public void init() {
		createModel() ;
		createView() ;
		updateView() ;
	}

/** Checks if num is an acceptable value for the given row */
	protected boolean checkRow( int row, int num ) {
		for( int col = 0; col < 9; col++ )
			if( model[row][col] == num )
				return false ;

return true ;
	}

/** Checks if num is an acceptable value for the given column */
	protected boolean checkCol( int col, int num ) {
		for( int row = 0; row < 9; row++ )
			if( model[row][col] == num )
				return false ;

return true ;
	}

/** Checks if num is an acceptable value for the box around row and col */
	protected boolean checkBox( int row, int col, int num ) {
		row = (row / 3) * 3 ;
		col = (col / 3) * 3 ;

for( int r = 0; r < 3; r++ )
			for( int c = 0; c < 3; c++ )
			if( model[row+r][col+c] == num )
				return false ;

return true ;
	}

/** This method is called by the browser to start the applet */
	@Override
	public void start() {
		// This statement will start the method 'run' to in a new thread
		(new Thread(this)).start() ;
	}

/** The active part begins here */
	public void run() {
		try {
			// Let the observers see the initial position
			Thread.sleep( 1000 ) ;

// Start to solve the puzzle in the left upper corner
			solve( 0, 0 ) ;
		} catch( Exception e ) {
		}
	}

/** Recursive function to find a valid number for one single cell */
	public void solve( int row, int col ) throws Exception {
		// Throw an exception to stop the process if the puzzle is solved
		if( row > 8 )
			throw new Exception( "Solution found" ) ;

// If the cell is not empty, continue with the next cell
		if( model[row][col] != 0 )
			next( row, col ) ;
		else 	{
			// Find a valid number for the empty cell
			for( int num = 1; num < 10; num++ ) {
				if( checkRow(row,num) && checkCol(col,num) && checkBox(row,col,num) ) {
					model[row][col] = num ;
					updateView() ;

// Let the observer see it
					Thread.sleep( 1000 ) ;

// Delegate work on the next cell to a recursive call
					next( row, col ) ;
				}
			}

// No valid number was found, clean up and return to caller
			model[row][col] = 0 ;
			updateView() ;
		}
	}

/** Calls solve for the next cell */
	public void next( int row, int col ) throws Exception {
		if( col < 8 )
			solve( row, col + 1 ) ;
		else
			solve( row + 1, 0 ) ;
	}
}

http://www.heimetli.ch/ffh/simplifiedsudoku.html [본문으로]

'Program > Algorithm' 카테고리의 다른 글

[Backtracking] 자바로 푼 스도쿠 퍼즐 (0)	2012/04/16
[Backtracking] 자바로 푼 Queens 문제 (0)	2012/04/16

Posted by Lee SeongUk

트랙백 0개, 댓글 0개가 달렸습니다

[Backtracking] 자바로 푼 Queens 문제

Program/Algorithm 2012/04/16 16:47

Backtracking 방식으로 Queens 문제를 푼 자바소스.

placeQueen(int column) 함수를 재귀호출하여 해를 구하는 클래스이다.

Queens Class^[각주:1]

import java.util.Scanner;

/* 
* The Queens class. 
* Places a number of chess queens on a board of a 
* specified size so that no queen can attack another. 
*/ 
public class Queens { 
	protected int boardSize; 
	protected boolean[][] board;

public Queens (int boardSize) { 
		this.boardSize = boardSize; 
		board = new boolean[boardSize][boardSize];

for (int row = 0; row < boardSize; row++) 
			for (int column = 0; column < boardSize; column++) 
				board[row][column] = false; 
	} // Queens constructor

/* 
	* pre: There are queens in columns 0 to (column - 1). 
	* post: Queens have been placed in all the columns 
	*       of board and PlaceQueens will return true, or 
	*       PlaceQueens will return false. 
	*/ 
	protected boolean placeQueen (int column) { 
		int row;

if (column == boardSize) { 
			return true; 
		} else 	{ 
			boolean successful = false; 
			row = 0; 
			
			while ((row < boardSize) && !successful) { 
				if (threat (row, column)) { 
					row++; 
				} else 	{ 
					// Place queen and try to place queen in next column. 
					board[row][column] = true; 
					successful = placeQueen (column + 1);

if (!successful) { 
						// Remove the queen placed in the column. 
						board[row][column] = false; 
						row++; 
					} 
				} 
			} 
			return successful; 
		} 
	} // placeQueen method

protected boolean threat (int row, int column) { 
		// Test for a queen on the same row. 
		for (int c = 0; c < column; c++) { 
			if (board[row][c]) { 
				return true; 
			} 
		}

// Test for queen on up diagonal. 
		for (int c = 1; c <= column; c++) { 
			if (row < c) { 
				break; 
			}

if (board[row - c][column - c]) { 
				return true; 
			} 
		}

// Test for queen on down diagonal 
		for (int c = 1; c <= column; c++) { 
			if (row + c >= boardSize) { 
				break; 
			}

if (board[row + c][column - c]) { 
				return true; 
			} 
		}

return false; 
	} // threat method

protected void outputBoard() { 
		System.out.println("Solution for board of size " + boardSize + ":");

for (int row = 0; row < boardSize; row++) { 
			for (int column = 0; column < boardSize; column++) { 
				if (board[row][column]) { 
					System.out.print("Q "); 
				} else 	{ 
					System.out.print(". "); 
				} 
			}

System.out.println(); 
		}

System.out.println(); 
	} // outputBoard method

public void solve() { 
		if (placeQueen(0)) { 
			outputBoard(); 
		} else { 
			System.out.println("There is no solution possible"); 
		} 
	} // solve method

public static void main (String[] args) { 
		Queens board;

Scanner input = new Scanner (System.in); 
		System.out.print("Enter the board Size: "); //Gain Size of board from user 
		int boardSize = input.nextInt(); 
		input.close();

board = new Queens(boardSize); 
		board.solve(); 
	} // main method 
}