스도쿠 문제 풀기
스도쿠 문제 모두 풀기
이 글은 구종만 씨의 스도쿠 문제 전부 풀기 게시글을 인용하여 작성한 것임
스도쿠란 ?
9 * 9 칸에서 아래의 규칙에 따라서 1 ~ 9 까지 숫자를 채우는 게임
스도쿠 규칙
- 1.같은 행 에는 1 ~ 9 까지 숫자가 1개씩 존재
- 2.같은 열 에는 1 ~ 9 까지 숫자가 1개씩 존재
- 3.3 * 3 에는 1 ~ 9 까지 숫자가 1개씩 존재
ex) 좌표 A 에 대한 3가지 규칙
- 1.같은 행 규칙
- 2.같은 열 규칙
- 3.3 * 3 사각형 규칙
위키 에 따르면 스도쿠는 여러 변형 문제가 있지만, 여기서는 가장 기본적인 스도쿠에 대해서만 다룸
스도쿠 알고리즘
스도쿠를 푸는 알고리즘은 제약조건전파 와 탐색 이라는 2가지 핵심 알고리즘으로 구현한다.
- 초기화 : 9 * 9 형태의 스도쿠 사각형을 정의
- 값 설정 : 입력 값을 이용하여 각 좌표들에 값을 설정
- 검색 : 아직 미완성인 좌표들에 값을 1개씩 넣어보며 스도쿠를 완성한다.
초기화
- 9 * 9 = 81 개의 1개의 칸에 사용할 값을 정의
- 1개의 칸을 일반적으로 숫자로 표현할 수 있지만, 값을 문자열로 표현한다.
- 특정 숫자로 표현하지 않고 문자열로 표현하는 이유는 해당 칸에 가능한 모든 후보 값들을 모두 표현하기 위함이다.
- 스도쿠 문제를 풀때, 1개의 칸에 가능한 모든 후보 값을 나열 해놓고 위 3가지 규칙을 이용하여 후보자들을 줄여 나가며 풀 생각이다. (여기서 제약조건전파를 이용함)
class SudokuValue {
private static final char EMPTY = '_';
// 길이
private int length = 9;
// 후보 숫자들
private String values = "123456789";
public SudokuValue() {
}
public SudokuValue(SudokuValue sudokuValue) {
this.length = sudokuValue.getLength();
this.values = sudokuValue.toString();
}
// 후보에서 값을 제거
public boolean delete(char value) {
if (contains(value)) {
values = values.replace(value, EMPTY);
length--;
return true;
}
return false;
}
// 포함되었는지 ..
public boolean contains(char value) {
return values.indexOf(value) > -1;
}
// 현재 가능한 모든 후보자들 return
public char[] getValues() {
char[] retValues = new char[this.getLength()];
int index = 0;
for(char value : values.toCharArray()) {
if(value == EMPTY) {
continue;
}
retValues[index++] = value;
}
return retValues;
}
// 후보들의 길이 반환
public int getLength() {
return length;
}
@Override
public String toString() {
return values;
}
}
- 9 * 9 형태의 스도쿠 게임 판을 정의
- 먼저 1개의 칸이 위치정보를 표현하는 방법을 정의해보자. 일반적으로 2차원 배열을 먼저 떠올릴 수 있지만, 여기서는 문자열을 이용하여 좌표를 표현한다.
- 스도쿠 각 행이름 (A ~ I), 열이름 (1 ~ 9) 를 조합하여 표현한다.
- 스도쿠 사각형 초기화
static final String ROWS = "ABCDEFGHI";
static final String COLS = "123456789";
/** 스도쿠 해시맵 초기화
* @return A1 ~ I9 까지의 key 를 갖는 스도쿠 게임 판
* ex) "A1": "123456789"
*/
public static HashMap<String, SudokuValue> getValueMap(){
HashMap<String, SudokuValue> valueMap = new LinkedHashMap<String, SudokuValue>();
for(char row : ROWS.toCharArray()) {
for(char col : COLS.toCharArray()) {
String key = createKey(row, col); // row + "" + col
valueMap.put(key, new SudokuValue());
}
}
return valueMap;
}
public static main(String[] args){
HashMap<String, SudokuValue> valueMap = getValueMap();
System.out.println(valueMap.get("A3"));
// output: 123456789
}
- 특정 좌표의 단위(unit)와 동료(peer)들을 표현
- 먼저 용어부터 정리해보자.
- 단위(unit) : 특정 좌표는 위에서 언급했던 3가지 규칙 에 따라 해당 좌표에 값이 변경될 때 영향을 받는 좌표들이 존재한다. 같은 행, 같은 열, 같은 사각형은 각각 1개의 단위라고 하자
- 동료(peer) : 특정 좌표에 연관된 단위는 쉽게 생각해서 9(1개의 단위) * 3 = 27 개 일 것 같지만, 사실 중복된 좌표가 생기는데 peer 는 단순히 단위에서 중복을 제거하여 21개 만을 저장한 것들이다.
- ex) 좌표 B3 에 대한 단위들
- 그렇다면 단위, 동료 이걸 왜 계산할까?
- 추후에 다시 설명하겠지만, 제약조건전파라는 방법을 이용하여 특정 좌표에 값을 적을때, 그 좌표와 연관된 단위에 해당 하는 모든 좌표에서 해당 값을 후보자에서 제거할 수 있기 때문이다.
- 물론 매번 같은 행, 같은 열, 같은 사각형을 검사할 수도 있지만, 여기서는 메모제이션을 이용하여 미리 계산해 놓는 방법을 택했다.
- 단위(unit) 구하기
/** 현재 col 과 같은 행들 추출
* @param col : 컬럼 이름
* @return 같은 행을 같는 list (A1 ~ I1)
*/
private static List<String> getRowUnitList(char col){
List<String> rowUnitList = new ArrayList<String>();
for(char row : ROWS.toCharArray()) {
rowUnitList.add(createKey(row, col));
}
return rowUnitList;
}
/** 현재 row 와 같은 열들 추출
* @param row : 행 이름
* @return 같은 열을 같는 list (A1 ~ A9)
*/
private static List<String> getColUnitList(char row){
List<String> colUnitList = new ArrayList<String>();
for(char col : COLS.toCharArray()) {
colUnitList.add(createKey(row, col));
}
return colUnitList;
}
private static final String[] SQUARE_ROWS = { "ABC", "DEF", "GHI" };
private static final String[] SQUARE_COLS = { "123", "456", "789" };
/** 현재 row, col 이 포함되는 사각형 추출
* @param row : 행 이름
* @param col : 컬럼 이름
* @return 현 좌표가 해당하는 3*3 영역 (A1 ~ A3, B1 ~ B3, C1 ~ C3)
*/
private static List<String> getSquareUnitList(char row, char col){
// 현재 좌표가 해당하는 3 * 3 영역 찾기
String targetRows = null, targetCols = null;
for(String squareRow : SQUARE_ROWS) {
if(squareRow.contains(row + "")) {
targetRows = squareRow;
break;
}
}
for(String squareCol : SQUARE_COLS) {
if(squareCol.contains(col + "")) {
targetCols = squareCol;
break;
}
}
List<String> squareUnitList = new ArrayList<String>();
for(char targetRow : targetRows.toCharArray()) {
for(char targetCol : targetCols.toCharArray()) {
squareUnitList.add(createKey(targetRow, targetCol));
}
}
return squareUnitList;
}
/** 현재 좌표에 해당하는 unit 반환 -> 스도쿠 게임 3가지 규칙에 해당
* @param row : 행 이름
* @param col : 열 이름
* @return 현 좌표에 해당하는 unit들 반환
* ex) C2
* UnitType: ROW, COL, SQUARE
* - ROW : A2 ~ I2
* - COL : C1 ~ C9
* - SQUARE : A1 ~ A3, B1 ~ B3, C1 ~ C3
*/
public static EnumMap<UnitType, List<String>> getUnitListMap(char row, char col){
EnumMap<UnitType, List<String>> unitListMap = new EnumMap<UnitType, List<String>>(UnitType.class);
unitListMap.put(UnitType.ROW, getRowUnitList(col));
unitListMap.put(UnitType.COL, getColUnitList(row));
unitListMap.put(UnitType.SQUARE, getSquareUnitList(row, col));
return unitListMap;
}
private static void testUnitListMap() {
EnumMap<UnitType, List<String>> unitListMap = SudokuUtil.getUnitListMap('A', '3');
System.out.println("A3");
System.out.println(unitListMap.get(UnitType.ROW));
// [A3, B3, C3, D3, E3, F3, G3, H3, I3]
System.out.println(unitListMap.get(UnitType.COL));
// [A1, A2, A3, A4, A5, A6, A7, A8, A9]
System.out.println(unitListMap.get(UnitType.SQUARE));
// [A1, A2, A3, B1, B2, B3, C1, C2, C3]
}
- 동료(peer) 구하기
/** 현재 key 에 해당하는 중복을 제거해서 추출 : 1차원 set
* @param unitListMap : 모든 unit 들을 담은 map
* @param key : 현재 좌표
* @return 모든 단위 에서 중복을 제거하여 저장
* - 같은 행 9 + 같은 열 9 + 같은 사각형 9 = 27
* - 중복 제거 = 9 + 6 + 6 = 21
*/
public static Set<String> getPeerSet(EnumMap<UnitType, List<String>> unitListMap, String key){
Set<String> peerSet = new HashSet<String>();
// 단위들에서 모두 추출
for(UnitType unitType : unitListMap.keySet()) {
for(String targetKey : unitListMap.get(unitType)) {
// 현재 좌표 제거
if(key.equals(targetKey)) {
continue;
}
peerSet.add(targetKey);
}
}
return peerSet;
}
private static void testPeerSet() {
EnumMap<UnitType, List<String>> unitListMap = SudokuUtil.getUnitListMap('A', '3');
Set<String> peerSet = SudokuUtil.getPeerSet(unitListMap, "A3");
System.out.println("A3");
System.out.println(unitListMap.get(UnitType.ROW));
// [A3, B3, C3, D3, E3, F3, G3, H3, I3]
System.out.println(unitListMap.get(UnitType.COL));
// [A1, A2, A3, A4, A5, A6, A7, A8, A9]
System.out.println(unitListMap.get(UnitType.SQUARE));
// [A1, A2, A3, B1, B2, B3, C1, C2, C3]
System.out.println(peerSet);
// [I3, H3, G3, F3, E3, C1, D3, B1, C2, C3, A1, B2, B3, A2, A4, A5, A6, A7, A8, A9]
}
값 설정
- 임의의 좌표에 입력 값을 설정 - setValue(key, value, valueMap)
- 위에서 설명했지만, 우리는 1개의 칸에 모든 후보자를 표현함 (“123456789”)
- 따라서 우리는 특정 좌표에 후보 값들중 입력 값을 제외한 값을 모두 제거한다. - deleteValue(key, value, valueMap)
- 특정 좌표에서 값을 제거하면서 제약조건전파 전략을 적용할 수 있다.
- 제약조건전파 는 아래의 2개의 전략을 이용한다.
-
1번 전략: 빈칸에 들어갈 수 있는 숫자가 1개라면 그곳에 숫자를 기입
위 그림에서 붉은색으로 칠해진 단위에서 1이 들어갈 수 있는 장소는 A - 2번 전략: 위 스도쿠 규칙에 따라서 어느 단위에서 특정 숫자가 들어갈 칸이 1개라면 그곳에 숫자를 기입
위 그림에서 B가 가능한 숫자들을 보자 - 가로 : 2, 4, 6, 7, 9
- 세로 : 4, 5, 9
- 3 * 3 : 4, 5, 7
-
위 3개의 조건을 모두 만족하는 값은 4
- setValue(key, value, valueMap) 메소드
/** 특정 좌표에 값을 지정
* - 값을 지정하는 것은 모든 후보들 중 value 를 제외한 값을 제거하는 것
* @param key : 키 (좌표)
* @param value : 값 (지정하려는 값)
* @param valueMap : 실제 스도쿠 값이 있는 해시맵
* @return 성공여부 (false : 스도쿠를 만들수 없는 경우)
*/
public boolean setValue(String key, char value, HashMap<String, SudokuValue> valueMap) {
SudokuValue innerValue = valueMap.get(key);
// 현재 좌표에서 value 제외하고 모두 제거
for(char candidate : innerValue.getValues()) {
if(candidate == value) { // 현재 값 제외
continue;
}
// 다른 후보 값들 제거
if(!deleteValue(key, candidate, valueMap)) {
return false;
}
}
return true;
}
- deleteValue(key, value, valueMap) 메소드
/** 특정 좌표에 값을 제거
* - 1번 전략 : 값을 지운후, 특정 좌표에 값이 1개만 들어갈 수 있다면, peer 들에서 해당 값을 제거함
* - 2번 전략 : 현재 지운 값(value) 는 3가지 단위에서 1개씩은 존재해야함
* @param key : 키 (좌표)
* @param value : 값 (지우려고 하는 값)
* @param valueMap : 실제 스도쿠 값이 있는 해시맵
* @return 성공여부 (false : 스도쿠를 만들수 없는 경우)
*/
public boolean deleteValue(String key, char value, HashMap<String, SudokuValue> valueMap) {
SudokuValue innerValue = valueMap.get(key);
// 후보들 중에서 값이 없음 - 이미 지움
if(!innerValue.contains(value)) {
return true;
}
// 후보자가 1개 -> 지울수 있는 값이 없음
if(innerValue.getLength() == 1) {
return false;
}else { // 값을 후보에서 제거
if(!innerValue.delete(value)) {
return false;
}
}
// 1번 전략 : 값을 지운후, 특정 좌표에 값이 1개만 들어갈 수 있다면
if(!propagation(key, valueMap)) {
return false;
}
// 2번 전략 : 현재 지운 값(value) 는 3가지 단위에서 1개씩은 존재해야함
if(!checkUnitList(key, value, valueMap)) {
return false;
}
return true;
}
- 1번 전략 : propagation(key, valueMap)
/** 1번 전략
* - 값을 지운후, 특정 좌표에 값이 1개만 들어갈 수 있다면, peer 들에서 해당 값을 제거함
* @param key : 키 값 (좌표)
* @param valueMap : 실제 스도쿠 값이 있는 해시맵
* @return 성공여부 (false : 스도쿠를 만들수 없는 경우)
*/
private boolean propagation(String key, HashMap<String, SudokuValue> valueMap) {
SudokuValue deleteTarget = valueMap.get(key);
// 실행 조건 : 좌표에 값이 1개일 때만 수행
if(deleteTarget.getLength() != 1) {
return true;
}
// 값이 1개
char deleteValue = deleteTarget.getValues()[0];
// 제약 조건 전파 : 나와 같은 단위를 사용하는 모든 좌표들에서 값을 제거
Set<String> peerSet = peerSetMap.get(key);
for(String peerKey : peerSet) {
// A4
if(!deleteValue(peerKey, deleteValue, valueMap)) {
return false;
}
}
return true;
}
- 2번 전략 : checkUnitList(key, value, valueMap)
/** 2번 전략
* - 현재 지운 값(value) 는 3가지 단위에서 1개씩은 존재해야함
* @param key : 키 (좌표)
* @param value : 값 (단위 별로 1개씩은 무조건 존재해야하는 값)
* @param valueMap : 실제 스도쿠 값이 있는 해시맵
* @return 성공여부 (false : 스도쿠를 만들수 없는 경우)
*/
private boolean checkUnitList(String key, char value, HashMap<String, SudokuValue> valueMap) {
EnumMap<UnitType, List<String>> unitListMap = unitMap.get(key);
for(UnitType unitType : unitListMap.keySet()) {
// 단위 별로 value 가 가능한 좌표 리스트
List<String> possibleKeyList = new ArrayList<String>();
for(String possibleKey : unitListMap.get(unitType)) {
SudokuValue possibleValue = valueMap.get(possibleKey);
if(possibleValue.contains(value)) {
possibleKeyList.add(possibleKey);
}
}
// value 가 가능한 좌표가 없음 -> 규칙에 어긋남
if(possibleKeyList.isEmpty()) {
return false;
} // value 가 가능한 좌표가 1개 : 값을 지정함
else if(possibleKeyList.size() == 1) {
String targetKey = possibleKeyList.get(0);
return setValue(targetKey, value, valueMap);
}
}
return true;
}
- 사실 여기까지만 구현하더라도 간단한 스도쿠 문제는 해결이 가능하다.
- 실제로 쉬운 입력에 대해서 수행해보자
- 입력
003020600900305001001806400008102900700000008006708200002609500800203009005010300
public class Sudoku {
// 스도쿠 3가지 규칙에 해당하는 단위들 - 메모제이션
private HashMap<String, EnumMap<UnitType, List<String>>> unitMap;
// 1개의 좌표에서 제약조건 전파 대상 좌표들
private HashMap<String, Set<String>> peerSetMap;
public Sudoku() {
unitMap = new HashMap<String, EnumMap<UnitType, List<String>>>();
peerSetMap = new HashMap<String, Set<String>>();
for(char row : SudokuUtil.ROWS.toCharArray()) {
for(char col : SudokuUtil.COLS.toCharArray()) {
String key = SudokuUtil.createKey(row, col);
unitMap.put(key, SudokuUtil.getUnitListMap(row, col));
peerSetMap.put(key, SudokuUtil.getPeerSet(unitMap.get(key), key));
}
}
}
public static void main(String[] args) throws IOException {
// unit, peer 초기화
Sudoku sudoku = new Sudoku();
// 스도쿠 판 초기화
HashMap<String, SudokuValue> valueMap = SudokuUtil.getValueMap();
// 입력 데이터
String input = "003020600900305001001806400008102900700000008006708200002609500800203009005010300";
// 입력 데이터 파싱
HashMap<String, Character> inputMap = SudokuUtil.parseInput(input);
// 입력 데이터 각 좌표에 값을 설정
for(String key : inputMap.keySet()) {
sudoku.setValue(key, inputMap.get(key), valueMap);
}
// 결과 출력
for(char row : SudokuUtil.ROWS.toCharArray()){
for(char col : SudokuUtil.COLS.toCharArray()){
String key = row + "" + col;
System.out.print(valueMap.get(key) +"\t");
}
System.out.println();
}
}
}
- 결과
___4_____ _______8_ __3______ ________9 _2_______ 1________ _____6___ ____5____ ______7__
________9 _____6___ ______7__ __3______ ___4_____ ____5____ _______8_ _2_______ 1________
_2_______ ____5____ 1________ _______8_ ______7__ _____6___ ___4_____ ________9 __3______
____5____ ___4_____ _______8_ 1________ __3______ _2_______ ________9 ______7__ _____6___
______7__ _2_______ ________9 ____5____ _____6___ ___4_____ 1________ __3______ _______8_
1________ __3______ _____6___ ______7__ ________9 _______8_ _2_______ ___4_____ ____5____
__3______ ______7__ _2_______ _____6___ _______8_ ________9 ____5____ 1________ ___4_____
_______8_ 1________ ___4_____ _2_______ ____5____ __3______ ______7__ _____6___ ________9
_____6___ ________9 ____5____ ___4_____ 1________ ______7__ __3______ _______8_ _2_______
- 결과를 출력해보는 것도 좋지만, 결과가 맞는지 확인하는 코드를 작성해보자.
/** 행들 유효성 검사 */
private static boolean validateRowUnitList(HashMap<String, SudokuValue> valueMap) {
for(char col : COLS.toCharArray()) {
Set<Character> valueSet = new HashSet<Character>();
for(char row : ROWS.toCharArray()) {
String key = createKey(row, col);
SudokuValue value = valueMap.get(key);
if(value.getLength() != 1) {
return false;
}
char realValue = value.getValues()[0];
valueSet.add(realValue);
}
StringBuilder valueBuilder = new StringBuilder();
for(char value : valueSet) {
valueBuilder.append(value);
}
if(!COLS.equals(valueBuilder.toString())) {
return false;
}
}
return true;
}
/** 열들 유효성 검사 */
private static boolean validateColUnitList(HashMap<String, SudokuValue> valueMap) {
for(char row : ROWS.toCharArray()) {
Set<Character> valueSet = new HashSet<Character>();
for(char col : COLS.toCharArray()) {
String key = createKey(row, col);
SudokuValue value = valueMap.get(key);
if(value.getLength() != 1) {
return false;
}
char realValue = value.getValues()[0];
valueSet.add(realValue);
}
StringBuilder valueBuilder = new StringBuilder();
for(char value : valueSet) {
valueBuilder.append(value);
}
if(!COLS.equals(valueBuilder.toString())) {
return false;
}
}
return true;
}
/** 3*3 사각형들 유효성 검사 */
private static boolean validateSqaureUnitList(HashMap<String, SudokuValue> valueMap) {
for(String squareRow : SQUARE_ROWS) {
for(String squareCol : SQUARE_COLS) {
Set<Character> valueSet = new HashSet<Character>();
for(char row : squareRow.toCharArray()) {
for(char col : squareCol.toCharArray()) {
String key = createKey(row, col);
SudokuValue value = valueMap.get(key);
if(value.getLength() != 1) {
return false;
}
char realValue = value.getValues()[0];
valueSet.add(realValue);
}
}
StringBuilder valueBuilder = new StringBuilder();
for(char value : valueSet) {
valueBuilder.append(value);
}
if(!COLS.equals(valueBuilder.toString())) {
return false;
}
}
}
return true;
}
/** 현재 스도쿠 성공 여부 검사 */
public static boolean validateResult(HashMap<String, SudokuValue> valueMap) {
if(!validateRowUnitList(valueMap)) {
return false;
}
if(!validateColUnitList(valueMap)) {
return false;
}
if(!validateSqaureUnitList(valueMap)) {
return false;
}
return true;
}
- 결과 확인
public static void main(String[] args) throws IOException {
// unit, peer 초기화
Sudoku sudoku = new Sudoku();
// 스도쿠 판 초기화
HashMap<String, SudokuValue> valueMap = SudokuUtil.getValueMap();
// 입력 데이터
String input = "003020600900305001001806400008102900700000008006708200002609500800203009005010300";
// 입력 데이터 파싱
HashMap<String, Character> inputMap = SudokuUtil.parseInput(input);
// 입력 데이터 각 좌표에 값을 설정
for(String key : inputMap.keySet()) {
sudoku.setValue(key, inputMap.get(key), valueMap);
}
System.out.println(SudokuUtil.validateResult(valueMap));
// true
}
검색
- 위에서 제약조건전파 전략을 이용하여 간단한 스도쿠 문제를 해결할 수 있는 것을 확인했다.
- 하지만 모든 문제를 해결 할 수 있는 것은 아니다. 조금 더 어려운 문제를 이용해서 실행해보자.
- 예제 : 4…..8.5.3……….7……2…..6…..8.4……1…….6.3.7.5..2…..1.4……
- 결과
___4_____ 1____67_9 12___67_9 1_3_____9 _23__6__9 _2___6__9 _______8_ 123_____9 ____5____
_2___6789 __3______ 12__56789 1__45__89 _2_456__9 _2_456_89 12___67_9 12_4____9 12_4_67_9
_2___6_89 1___56_89 12__56_89 ______7__ _23456__9 _2_456_89 123__6__9 1234____9 1234_6__9
__3___789 _2_______ 1___5_789 __345___9 __345_7_9 ___45_7_9 1_3_5_7_9 _____6___ 1_3___789
__3__67_9 1___567_9 1___567_9 __3_5___9 _______8_ _2__567_9 ___4_____ 123_5___9 123___7_9
__3__6789 ___4_____ ____56789 __3_5___9 1________ _2__567_9 _23_5_7_9 _23_5__89 _23___789
_2_____89 _______89 _2_____89 _____6___ ___45___9 __3______ 12__5___9 ______7__ 12_4___89
____5____ _____6789 __3______ _2_______ ___4__7_9 1________ _____6__9 ___4___89 ___4_6_89
1________ _____6789 ___4_____ ____5__89 ____5_7_9 ____5_789 _23_56__9 _23_5__89 _23__6_89
- 따라서 우리는 후보 값의 수가 가장 적은 칸들을 선택하여 1개씩 값을 넣어보며 스도쿠를 완성시키자.
/** 검색
* - 아직 답을 못 찾은 칸 중 가장 후보의 수가 적은 칸부터 DFS 로 검색을 수행
* @param valueMap : 실제 스도쿠 값이 있는 해시맵
* @return 결과 해시맵
*/
public HashMap<String, SudokuValue> search(HashMap<String, SudokuValue> valueMap) {
// 이미 완성
if(SudokuUtil.validateResult(valueMap)) {
return valueMap;
}
// 아직 답을 못 찾은 칸 중 가장 후보의 수가 적은 칸 찾기
String targetKey = null;
int targetLength = 10;
for(String key : valueMap.keySet()) {
SudokuValue value = valueMap.get(key);
if(value.getLength() == 1) {
continue;
}
if(targetLength > value.getLength()) {
targetKey = key;
targetLength = value.getLength();
}
}
if(valueMap.get(targetKey) == null) {
System.err.println("not founded target : " + targetKey + "::"+valueMap);
return null;
}
HashMap<String, SudokuValue> resultMap = null;
char[] targetValues = valueMap.get(targetKey).getValues();
for(char targetValue : targetValues) {
HashMap<String, SudokuValue> cloneValueMap = SudokuUtil.deepCopyValueMap(valueMap);
// 현재 값을 설정 후
if(! setValue(targetKey, targetValue, cloneValueMap)) {
continue;
}
// 다른 미완성 값들 검색
resultMap = search(cloneValueMap);
if(resultMap == null) {
continue;
}
// 이미 완성
if(SudokuUtil.validateResult(resultMap)) {
return resultMap;
}
}
return resultMap;
}
- 이제 search 메소드를 이용해서 다시 실행해보자
public static void main(String[] args) throws IOException {
// unit, peer 초기화
Sudoku sudoku = new Sudoku();
// 스도쿠 판 초기화
HashMap<String, SudokuValue> valueMap = SudokuUtil.getValueMap();
// 입력 데이터
String input = "003020600900305001001806400008102900700000008006708200002609500800203009005010300";
// 입력 데이터 파싱
HashMap<String, Character> inputMap = SudokuUtil.parseInput(input);
// 입력 데이터 각 좌표에 값을 설정
for(String key : inputMap.keySet()) {
sudoku.setValue(key, inputMap.get(key), valueMap);
}
HashMap<String, SudokuValue> resultMap = sudoku.search(valueMap);
if(resultMap != null) {
// 결과 출력
for(char row : SudokuUtil.ROWS.toCharArray()){
for(char col : SudokuUtil.COLS.toCharArray()){
String key = row + "" + col;
System.out.print(valueMap.get(key) +"\t");
}
System.out.println();
}
}else {
System.out.println("error ... \n" + input);
}
}
- 결과
___4_____ 1________ ______7__ __3______ _____6___ ________9 _______8_ _2_______ ____5____
_____6___ __3______ _2_______ 1________ ____5____ _______8_ ________9 ___4_____ ______7__
________9 ____5____ _______8_ ______7__ _2_______ ___4_____ __3______ 1________ _____6___
_______8_ _2_______ ____5____ ___4_____ __3______ ______7__ 1________ _____6___ ________9
______7__ ________9 1________ ____5____ _______8_ _____6___ ___4_____ __3______ _2_______
__3______ ___4_____ _____6___ ________9 1________ _2_______ ______7__ ____5____ _______8_
_2_______ _______8_ ________9 _____6___ ___4_____ __3______ ____5____ ______7__ 1________
____5____ ______7__ __3______ _2_______ ________9 1________ _____6___ _______8_ ___4_____
1________ _____6___ ___4_____ _______8_ ______7__ ____5____ _2_______ ________9 __3______