다음과 같은 기능을 한번의 로그인으로 사용 할 수 있습니다.
NTIS 바로가기
The journal of the institute of internet, broadcasting and communication : JIIBC, v.15 no.1, 2015년, pp.207 - 215
AI-Helper
This paper proposes a solution-yielding linear time algorithm to NP-complete Sudoku, to which no polynomial time algorithm has been proposed. The proposed algorithm is performed on blocks in the descending order of the number of clues they contain. It firstly determines all numbers that could possib...
* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.
| 핵심어 | 질문 | 논문에서 추출한 답변 |
|---|---|---|
| 본 논문에서 완전 피복 문제의 해를 구하는 알고리즘을 고찰해보는 이유는 무엇인가? | 본 논문은 n×n 스도쿠 문제를 블록 수 k에 대해 O(kn)의 다항시간 복잡도로 구할 수 있는 알고리즘을 제안한다. 스도쿠 문제를 다항시간으로 해결하는 알고리즘이 존재하지 않기 때문에 2장에서는 완전 피복 문제의 해를 구하는 알고리즘을 고찰해 본다. 3장에서는 스도쿠 문제를 다항시간 복잡도로 정확한 해를 구하는 알고리즘을 제안한다. | |
| 스도쿠 문제는 무엇인가? | 스도쿠 (숫자 넣기, Sudoku) 문제는 완전 피복 (exactcover) 문제의 대표적인 사례들 중 하나이다.[1] 일본에서 유래되어 2002년에 NP-완전 (NP-complete) 문제로 등재되었고, 2005년부터 본격적으로 연구되기 시작하여 백트래킹 (backtracking), 완전 피복, 열거법 (brute-force,exhaustive search), 통계적 탐색/최적화 방법들을 적용하여 해를 구하려고 시도되고 있다. | |
| 행과 열의 교집합을 구하면 특정 셀에 들어 갈 수 있는 숫자가 결정되는 이유는 무엇인가? | 먼저, 각 블록들 중에서 해당 블록에 들어 있는 고정된 숫자 (clue) 수가 가장 큰 블록부터 숫자를 넣는 방법을 택하였다. 특정 셀의 행에는 전체 숫자 1, 2, ···, 9중에서 기 존에 행과 블록에 존재하는 숫자를 제외한 숫자가 들어 갈 수 있다. 열에도 동일한 기준으로 숫자가 들어갈 수 있다. 따라서 행과 열의 교집합을 구하면 특정 셀에 들어 갈 수 있는 숫자가 결정된다. |
Wikipedia, "Exact Cover," http://en.wikipedia.org/wiki/Exact_cover, Wikipedia Foundation Inc., 2014.
Wikipedia, "Sudoku," http://en.wikipedia.org/wiki/Sudoku, Wikipedia Foundation Inc., 2014.
Wikipedia, "Mathematics of Sudoku," http://en.wikipedia.org/wiki/Mathematics_of_Sudoku, Wikipedia Foundation Inc., 2014.
Wikipedia, "Algorithmics of Sudoku," http://en.wikipedia.org/wiki/Algorithmics_of_Sudoku, Wikipedia Foundation Inc., 2014.
F. Jarvis and F. Jarvis, "Enumerating Possible Sudoku Grids," http://www.afjarvis.staff.shef.ac.uk/sudoku.pdf, 2005.
C. Lass, "Minimal Number of Clues for Sudokus," Central European Journal of Computer Science, Vol. 2, No. 2, pp. 143-151, Jun. 2012.
G. McGuire, B. Tugemann, and G. Civario, "There is no 16-Clue Sudoku: Solving the Sudoku Minimum Number of Clues Problem," pp. 1-36, Cornell University Library, Aug. 2013.
Wikipedia, "Knuth's Algorithm X," http://en.wikipedia.org/wiki/Knuth's_algorithm, Wikipedia Foundation Inc., 2014.
K. Y. Yun, "ECE 30: Introduction to Computer Engineering," Dept. of Electrical and Computer Eng., University of California, San Diago, http://paradise.ucsd.edu/ project.pdf, 2007.
J. M. Tjensvold, "Genetic Distributed Exact Cover Solver," http://decs.googlecode.com/decs/downloads/list/decs-report.pdf, 2007.
*원문 PDF 파일 및 링크정보가 존재하지 않을 경우 KISTI DDS 시스템에서 제공하는 원문복사서비스를 사용할 수 있습니다.
출판사/학술단체 등이 한시적으로 특별한 프로모션 또는 일정기간 경과 후 접근을 허용하여, 출판사/학술단체 등의 사이트에서 이용 가능한 논문
Copyright KISTI. All Rights Reserved.
※ AI-Helper는 부적절한 답변을 할 수 있습니다.