현재 위치

홈 ›› Forums ›› 재미 ›› 자유 게시판

자바로 만든 스도쿠 풀이기

c-clef의 이미지
글쓴이: c-clef / 작성시간: 일, 2007/09/02 - 10:21오후

25×25 스도쿠를 처음 보고 만들 생각을 했는데, 아직 그 문제는 풀지 못했습니다. 9×9는 여기에 나온 문제가 1.7초 정도 걸리고, 보통은 누르자 마자 답이 나옵니다. 16×16은 빠르면 수 초 정도 걸리지만... 15분 걸리는 것도 있습니다. 그리고 25×25는 아무것도 입력하지 않아도 엄청 오래 걸립니다.

알고리즘: 모든 빈 칸을 검색해서 가능한 문자 후보의 수가 가장 적은 곳을 찾아(가능한 문자 후보의 수가 1인 빈 칸을 만나면 바로 채웁니다) 문자를 채워 나가다 후보의 수가 0인 빈 칸이 존재하면 뒤로 돌리는 방식으로 답을 찾습니다.

실행 파일(.jar)은 http://lemonedo.springnote.com/pages/412666 에서 받으실 수 있습니다.

목표: 25×25를 평균 1분 이내에 풀 수 있을 때까지 알고리즘 개선은 계속됩니다 :)

Forums: 
자유 게시판
정태영의 이미지

글쓴이: 정태영 / 작성시간: 월, 2007/09/03 - 3:18오전

제가 잘못받은건지 모르겠는데 소스는 없고 jar 파일과 readme 만 있네요 :) 예전에 인공지능 과제 하던 기억이 나서 받아봤는데 -_ㅜ

--
오랫동안 꿈을 그리는 사람은 그 꿈을 닮아간다...

http://mytears.org ~(~_~)~
나 한줄기 바람처럼..

오랫동안 꿈을 그리는 사람은 그 꿈을 닮아간다...

http://mytears.org ~(~_~)~
나 한줄기 바람처럼..

c-clef의 이미지

글쓴이: c-clef / 작성시간: 일, 2007/09/09 - 9:07오후

소스 파일은 jar 파일 안에 있습니다 :)
버전 1.1.0부터 그냥 zip 파일 안에 넣었습니다.

kkb110a의 이미지

글쓴이: kkb110a / 작성시간: 월, 2007/09/03 - 4:58오전

근데 아래의 내용도 포함되어 있나요?
http://www.gwerdy.com/products/sudoku_solver/

혹시 이 문자후보제거 기법이 적용되지 않았다면 성능향상에 꽤 도움이 될 것 같네요~

kkb110a의 이미지

글쓴이: kkb110a / 작성시간: 월, 2007/09/03 - 4:59오전

근데 아래의 내용도 포함되어 있나요?
http://www.gwerdy.com/products/sudoku_solver/

혹시 이 문자후보제거 기법이 적용되지 않았다면 성능향상에 꽤 도움이 될 것 같네요~

익명 사용자의 이미지

글쓴이: 익명 사용자 / 작성시간: 월, 2007/09/03 - 9:49오후

제가 만든것은 그냥 아무생각없이 백트래킹을 적용해서 만들었는데 그닥 느릴것 같지는 않네요
방법은 빈칸을 만나면 가능한 숫자중 가장 작은 수를 만들고 이것을 위치정보와 함께 제가 만든 스택에 넣어둡니다.
그렇게 가다가 빈칸에 넣을 숫자가 없다면 지금까지 푼게 잘못된 것이므로
저 위 스택에서 하나빼서 위치정보를 보고 그 위치로 옮긴다음 이미 넣은 숫자보다 큰 것이 가능하면 다시 그 큰 숫자를 넣고
쭉 갑니다.

이런식으로 하다보면 풀리죠

몇가지 고칠점은 중복답안체크 문제와 해가 없는 경우 처리인데 머 그냥 토이니까요.. ㅎㅎ

제가 만든 프로그램은 수도쿠로 해서 검색하면 있을꺼에요 버그가 있어서 여기에 올린적이 있습니다

ixevexi의 이미지

글쓴이: ixevexi / 작성시간: 월, 2007/09/03 - 9:53오후

보니까 원글 쓰신분이 이 알고리즘을 개선한 거였네요

ㅎㅎ 별 도움이 안되서 죄송합니다
25x25는 굉장히 느려지는군요

C++, 그리고 C++....
죽어도 C++

c-clef의 이미지

글쓴이: c-clef / 작성시간: 월, 2007/09/10 - 8:00오전

이번에는 좀 더 사람이 푸는 방식에 가깝게 알고리즘을 개선했습니다. 매번 새로 candidates를 검색하던 것을, 문자를 대입할 때 그와 관련된 cell의 candidates만 업데이트를 하도록 하여(대입이 실패하면 마찬가지로 관련된 cell의 candidates만 복구) 약 2배 정도 성능이 향상되었고(1), 어떤 cell의 한 candidate가 그 cell이 속한 row 또는 column 또는 box에서 유일할 때 해당 candidate를 바로 대입하도록하여 100배 이상 빨라졌습니다(2). 이 정도로 human-like solving이라고 부르기는 좀 그렇지만... 조금 나아졌습니다.

사랑천사의 이미지

글쓴이: 사랑천사 / 작성시간: 월, 2007/09/10 - 1:08오전

그 거.. 오델로 개임하고 비슷한 건가요?(???) 오델로는 8x8인데 흠흠.(뭔 소리지..)

오델로 개임을 한번 만들어 볼까.. 하다가 셀을 일일히 체크 하다가 다운되지 않을까 싶어 한 번도 해 보지 않앗습니다.
----
Lee Yeosong(이여송 사도요한)
E-Mail: yeosong@gmail.com
HomePage: http://lys.lecl.net:88/
Wiki(Read-Only): http://lys.lecl.net:88/wiki/
Blog: http://lys.lecl.net:88/blog
MSN: ysnglee2000@hotmail.com
----
절이 싫으면 중이 떠나는 것이 아니라, 절이 싫으면 중이 절을 부숴야 한다.
때때

사람천사

둘러보기