$\require{mediawiki-texvc}$
  • 검색어에 아래의 연산자를 사용하시면 더 정확한 검색결과를 얻을 수 있습니다.
  • 검색연산자
검색연산자 기능 검색시 예
() 우선순위가 가장 높은 연산자 예1) (나노 (기계 | machine))
공백 두 개의 검색어(식)을 모두 포함하고 있는 문서 검색 예1) (나노 기계)
예2) 나노 장영실
| 두 개의 검색어(식) 중 하나 이상 포함하고 있는 문서 검색 예1) (줄기세포 | 면역)
예2) 줄기세포 | 장영실
! NOT 이후에 있는 검색어가 포함된 문서는 제외 예1) (황금 !백금)
예2) !image
* 검색어의 *란에 0개 이상의 임의의 문자가 포함된 문서 검색 예) semi*
"" 따옴표 내의 구문과 완전히 일치하는 문서만 검색 예) "Transform and Quantization"

논문 상세정보

유전 알고리즘을 이용한 스도쿠 퍼즐 생성 및 풀이 방법

Applying Genetic Algorithm To Randomly Creating And Solving A Sudoku Puzzle

제4회(2015년) 2015 Mar. 19 , 2015년, pp.521 - 526  
Abstract

A Sudoku puzzle is a kind of magic square puzzle which requires a non-repeated series of numbers from 1 to 9 in each 9 rows and 9 columns. Furthermore it contains total of 9 small three-by-three matrices, which need non-repeated numbers from 1 to 9 as well. Therefore the total number of possible cases of Sudoku puzzle is finite, even though that of creating nine-by-nine square is exponentially great. Accordingly a certain set of way is need not only for solving the puzzle, but also creating a new one. In this study, the method for creating a Sudoku puzzle applying genetic algorithm is suggested and will be demonstrated. Also, it will be shown that a Sudoku puzzle can be solved by genetic algorithm.

본문요약 

문제 정의
  • 본 연구는 미래창조과학부가 주최하는 제 4 회 EDISON SW 경진대회 전산설계분야 참가를 목적으로 계획수립, 진행하였다.

    본 연구는 미래창조과학부가 주최하는 제 4 회 EDISON SW 경진대회 전산설계분야 참가를 목적으로 계획수립, 진행하였다. 개인적으로 컴퓨터 프로그래밍은 항상 어렵고 난해한 분야이기 때문에 프로젝트를 시작하면서 주제 선정부터 매우 난감하고 힘겨웠으며, 코딩 작업하는 내내 여러 번 막다른 길을 맞아 수 차례 연구 기획부터 다시 시작하는 등 벅찬 위기가 많았다.

  • 본 연구에서는 스도쿠 생성 및 풀이에 대한 유전 알고리즘의 적용 실례를 보이는 것을 목적으로 하므로, 변형 규칙을 제외한 스도쿠 기본 규칙을 만족하는 퍼즐을 구성하도록 하였다.

    본 연구에서는 스도쿠 생성 및 풀이에 대한 유전 알고리즘의 적용 실례를 보이는 것을 목적으로 하므로, 변형 규칙을 제외한 스도쿠 기본 규칙을 만족하는 퍼즐을 구성하도록 하였다.

  • 본 연구에서는 스도쿠 퍼즐의 기본 규칙에 부합하는 새로운 게임 생성 및 실제 문제 풀이 방법에 유전 알고리즘을 적용하는 방법에 대해 논의하였다.

    본 연구에서는 스도쿠 퍼즐의 기본 규칙에 부합하는 새로운 게임 생성 및 실제 문제 풀이 방법에 유전 알고리즘을 적용하는 방법에 대해 논의하였다. C++ 프로그램을 통하여 작성된 실례와 문제 풀이에의 적용 결과를 제시하였고 다음과 같은 결론을 도출하였다.

  • 본 연구에서는 전통적인 스도쿠 퍼즐의 규칙에 대해 고찰하고 조건에 만족하는 새로운 게임 작성 방법을 고안하기 위하여 MS Visual Studio 6.0 을 기반으로 KAIST 플랫폼에서 제공하는 유전 알고리즘인 Simple GA solver 를 사용하여 다양한 형태의 스도쿠 퍼즐을 생성하는 방법을 제시한다.

    본 연구에서는 전통적인 스도쿠 퍼즐의 규칙에 대해 고찰하고 조건에 만족하는 새로운 게임 작성 방법을 고안하기 위하여 MS Visual Studio 6.0 을 기반으로 KAIST 플랫폼에서 제공하는 유전 알고리즘인 Simple GA solver 를 사용하여 다양한 형태의 스도쿠 퍼즐을 생성하는 방법을 제시한다. 또한 존재하는 실제 문제에 대해 유전 알고리즘을 적용하여 풀이하는 방법 또한 논의한다.

본문요약 정보가 도움이 되었나요?

질의응답 

키워드에 따른 질의응답 제공
핵심어 질문 논문에서 추출한 답변
스도쿠 퍼즐
스도쿠 퍼즐의 구성 및 구분은 어떻게 되는가?
일반적으로 가로 9 칸, 세로 9 칸 총 81 칸의 정방형 배열로 구성되어 있으며, 이는 다시 가로 3 칸, 세로 3 칸 총 9 칸의 작은 배열 9 개로 다시 구분된다

스도쿠 퍼즐은 전통적인 마방진의 형태에 스도쿠만의 특별한 규칙을 적용해 만들어진 배열의 임의의 칸을 여러 개 비움으로써 난이도를 조절하며, 처음에 보여지는 숫자들과 해당 게임의 규칙에 따라 빈칸을 모두 채우게 되면 그 퍼즐을 푼 것이 된다. 일반적으로 가로 9 칸, 세로 9 칸 총 81 칸의 정방형 배열로 구성되어 있으며, 이는 다시 가로 3 칸, 세로 3 칸 총 9 칸의 작은 배열 9 개로 다시 구분된다. 스도쿠 퍼즐을 푸는 근본적인 규칙은 일정한 구역에 대해 1 부터 9 까지 9 개의 숫자가 중복되지 않고 나열되어야 한다는 것이다.

유전 알고리즘
유전 알고리즘은 어떤 방법이라 할 수 있는가?
생물학의 진화 이론을 응용한 연산 방법으로, 임의적으로 생성된 최초의 해집합을 하나의 인구 집단으로 간주하고 적합 선택, 교배, 돌연변이 등 실제 생태계에서 일어나는 현상과 유사한 적응 단계를 거쳐 최종적으로 환경에 가장 잘 적응한, 즉 가장 적합한 해를 구하는 방법이다

유전 알고리즘은 생물학의 진화 이론을 응용한 연산 방법으로, 임의적으로 생성된 최초의 해집합을 하나의 인구 집단으로 간주하고 적합 선택, 교배, 돌연변이 등 실제 생태계에서 일어나는 현상과 유사한 적응 단계를 거쳐 최종적으로 환경에 가장 잘 적응한, 즉 가장 적합한 해를 구하는 방법이다. 단순히 무작위적인 입력을 제공하는 표준 난수 함 수와는 달리 적합도(Fitness)라는 개념을 적용하여 계산이 거듭될수록 효율적으로 유용한 해에 접근할 수 있다는 것이 가장 큰 장점이다.

스도쿠 판을 만드는 것
스도쿠 판을 만드는 것이 다항 함수적 해결이 불가능한 NP 문제로 취급받는 이유는?
단순히 81 개의 칸에 9 가지 숫자를 채우는 경우의 수만 고려해도 약 981 = 1.966 × 1077 가지 경우가 존재하는데, 이 중에서 스도쿠의 기본 규칙을 만족하는 경우만 추려내는 것은 인력으로는 불가능하며, 컴퓨터를 사용하여 한 경우의 규칙 위반 여부 검사를 1 초에 1 천만번 수행하더라도 약 6×1068년이 걸려야 모든 경우를 검사할 수 있다

새로운 스도쿠 판을 만드는 것은 결코 간단하지 않은 작업이다. 단순히 81 개의 칸에 9 가지 숫자를 채우는 경우의 수만 고려해도 약 981 = 1.966 × 1077 가지 경우가 존재하는데, 이 중에서 스도쿠의 기본 규칙을 만족하는 경우만 추려내는 것은 인력으로는 불가능하며, 컴퓨터를 사용하여 한 경우의 규칙 위반 여부 검사를 1 초에 1 천만번 수행하더라도 약 6×1068년이 걸려야 모든 경우를 검사할 수 있다. 따라서 다항함수적 해결이 불가능한 NP 문제로 취급되고는 한다.

질의응답 정보가 도움이 되었나요?

문의하기 

궁금한 사항이나 기타 의견이 있으시면 남겨주세요.

Q&A 등록

원문보기

원문 PDF 다운로드

  • ScienceON :

원문 URL 링크

  • 원문 URL 링크 정보가 존재하지 않습니다.

원문 PDF 파일 및 링크정보가 존재하지 않을 경우 KISTI DDS 시스템에서 제공하는 원문복사서비스를 사용할 수 있습니다. (원문복사서비스 안내 바로 가기)

DOI 인용 스타일

"" 핵심어 질의응답