태그 보관물: algorithm

algorithm

스도쿠 퍼즐을 생성하려면 어떻게해야합니까? 된) 스도쿠 퍼즐을 생성하십시오. 풀기 쉬울

스도쿠 퍼즐 생성기를 만들려고합니다. 그것은 내가 예상했던 것보다 훨씬 더 어렵고 더 많이 들어 갈수록 더 어려워집니다!

내 현재 접근 방식은 문제를 두 단계로 나누는 것입니다.

  1. 완전한 (해결 된) 스도쿠 퍼즐을 생성하십시오.
  2. 풀기 쉬울 때까지 숫자를 제거하고 하나의 솔루션 만 갖습니다.

1 단계에서 무차별 강제 방법을 사용하고 있기 때문에 런타임 문제가 있습니다. 완벽한 스도쿠 퍼즐을 채우는 최적의 방법이 있습니까?

2 단계에서 해결 된 스도쿠를 “퍼즐 링”하기 위해 어떤 알고리즘을 사용해야합니까?



답변

iOS 앱 스토어에서 최고 판매 스도쿠 게임이 있습니다. 퍼즐을 생성 한 방법은 다음과 같습니다.

먼저 퍼즐 생성기 응용 프로그램이 있습니다. 그러나 이것은 게임 코드의 일부가 아닙니다. 퍼즐을 만드는 데 사용하는 독립형 앱입니다. 고도로 수정되어 다양한 패턴 유형, 난이도 등급, 주어진 수 등을 생성하도록 설정할 수 있습니다. 퍼즐을 생성하고 일관된 난이도를 얻는 것은 즉시 수행하기가 어렵고 플레이어가 기다릴 때보 다 더 많은 시간이 걸립니다. 그래서 저는 “시드 퍼즐”이라고하는 것을 생성합니다. 이것이 사람들이하는 퍼즐을 생성하기 위해 게임 코드에서 사용하는 것입니다.

여기에서 생성기를 코딩하는 방법에 대답하지 않습니다. Google에서 수많은 퍼즐 생성기 코드를 온라인으로 찾을 수 있습니다. 거기서 시작하십시오. 그러나 좋은 게임을 만들려면 좋은 게임을 만들어야합니다. 내 게임은 즉시 퍼즐을 생성하지 않습니다.

내 퍼즐 생성기 앱이 작동하는 방식은 분당 수천 개의 퍼즐을 생성하지만 모두 우수하지는 않으며 특정 난이도와 모두 일치하지는 않습니다. 생성기는 퍼즐을 만든 다음 퍼즐을 풀고 난이도를 파악하고 퍼즐을 해결하는 데 필요한 기술을 기반으로 퍼즐의 점수를 매기고 퍼즐을 풀기 위해 추측이 필요한지 여부를 결정합니다 (일반적으로 나쁜 경우). 기준에 맞지 않는 퍼즐을 던져 버립니다. 단단하지만 불가능하지 않은 퍼즐의 경우 빠른 기계에서 내 정확한 사양에 맞는 100 개의 퍼즐을 생성하는 데 1 시간이 걸릴 수 있습니다. 이것이 내가 앱에서 이것을하지 않는 이유입니다. 어려운 사양으로 즉시 퍼즐을 생성하는 것은 앱에있는 퍼즐의 품질에는 맞지 않습니다.

퍼즐은 문자열, 길이 162 자, 숫자와 대시 또는 점이있는 81 자, 여백이있는 81 자입니다. 그런 다음 싱글, 더블 등의 수와 같이 각 통계에 대한 열

모든 생성 세션에서 얻은 결과는 통계가 열로 쉼표로 구분 된 줄입니다. 10,000 개의 퍼즐을 가져 와서 엑셀로 가져 와서 난이도별로 정렬 해 보겠습니다. 그런 다음 게임 보드에서 볼 수 있도록 앱으로 가져옵니다. 또한 시각적 호소력과 퍼즐의 시각적 패턴을 살펴 봅니다. 그런 다음 그 중에서 손을 선택합니다.

나는 그들을 씨앗 퍼즐이라고 부르며 여기에 내가 의미하는 바가 있습니다. 스도쿠 게임의 숫자는 실제로 토큰입니다. 숫자 1-9 대신 색상이나 기호 또는 문자가 될 수 있습니다. 내 씨앗 퍼즐은 숫자가 아니고 문자 ai입니다. 각 시드 퍼즐은 즉시 변경되어 재생 가능한 퍼즐을 만듭니다.

  1. 숫자 / 토큰을 랜덤 화하십시오. 문자 ai를 숫자 1-9로 다시 돌리면 조회 테이블이 무작위로 지정됩니다. 그 의미는 항상 1이 아닙니다. 그 자체만으로도 각 퍼즐마다 약 300,000 개의 변형이 만들어집니다.
  2. 퍼즐을 90도, 180도 또는 270도 회전시킵니다. 4 가지 변형이 더 추가됩니다.
  3. 퍼즐을 수평, 수직 또는 둘 다 퍼트십시오. 4 가지 변형이 더 추가됩니다.

따라서 각 시드 퍼즐은 5,806,080 개의 변형을 만들 수 있습니다. 나는 실제 플레이어와 함께 현장에서 이것을 테스트했습니다. 사람들은 자신들이 본질적으로 같은 퍼즐을하고 있다는 것을 모른다. 실제로 불가능합니다. 그들이 주어진 패턴이 매번 동일하다는 것을 알게 될 경우에만. 그러나 100 가지의 다른 씨앗조차도 아무도 알아 채지 못할 것입니다. 내 게임의 백만 명의 사용자가하지 않았습니다. 또한 솔버 앱으로 테스트했습니다. 솔버 앱은 퍼즐이 회전하거나 퍼 졌을 때와 같은 방식으로 퍼즐을 풀지 않습니다. 기술적으로 동일한 퍼즐이지만 때로는 다른 난이도로 평가하기도합니다.

그러나 Big Bad Sudoku Book에는 5 가지 난이도 레벨에서 1000 개의 시드 퍼즐 10 개와 여러 퍼즐 패턴 유형이 있습니다. 이것은 내 게임에 수십억 개의 퍼즐이 있음을 의미합니다. 10,000 개의 시드 퍼즐마다 58,060,800,000 개의 서로 다른 퍼즐이 있습니다.

Sudoku Book 버전 4 (2016으로 인해)에서 나는 580 억 개의 퍼즐 중에서 정확한 퍼즐을 지정하고 각 플레이어의 장치에서 동일한 퍼즐을 얻을 수있는 방법을 알아 냈습니다.


답변

1 단계에서 완전한 (해결 된) 스도쿠 퍼즐을 생성합니다. 무차별 대입 방법을 사용하고 있기 때문에 런타임 문제가 있습니다. 완벽한 스도쿠 퍼즐을 채우는 최적의 방법이 있습니까?

완벽한 스도쿠 퍼즐을 채우는 쉬운 방법이 있습니다-그룹 채우기와 원형 이동.

  1. 첫 번째 행을 9 개의 다른 숫자로 채 웁니다.
  2. 첫 번째 줄을 세 칸씩 이동하는 두 번째 줄을 채 웁니다.
  3. 두 번째 줄을 세 칸씩 이동하는 세 번째 줄을 채 웁니다.
  4. 세 번째 행을 한 슬롯 씩 이동하는 네 번째 행을 채우십시오.

line 1: 8 9 3  2 7 6  4 5 1
line 2: 2 7 6  4 5 1  8 9 3 (shift 3)
line 3: 4 5 1  8 9 3  2 7 6 (shift 3)

line 4: 5 1 8  9 3 2  7 6 4 (shift 1)
line 5: 9 3 2  7 6 4  5 1 8 (shift 3)
line 6: 7 6 4  5 1 8  9 3 2 (shift 3)

line 7: 6 4 5  1 8 9  3 2 7 (shift 1)
line 8: 1 8 9  3 2 7  6 4 5 (shift 3)
line 9: 3 2 7  6 4 5  1 8 9 (shift 3)

사용자가 명백한 패턴을 인식하지 못하게하려면 더 이상 패턴이 없도록 행과 열의 순서를 무작위로 지정하는 것이 좋습니다. 각 행 / 열의 9 개 숫자가 모두 하나의 원자 단위로 함께 이동하는 한 스도쿠 보드는 항상 유효합니다.

채워진 스도쿠 퍼즐이 완성되었습니다. 자세한 내용은 “make Sudoku”를 검색하십시오.


답변

스도쿠 솔버가 있다면 어렵지 않습니다.

스도쿠 솔버를 만드는 것은 어렵고 흥미로운 문제이므로 다른 질문으로 저장하는 것이 가장 좋습니다. 아니면 이것을 읽고 어떻게 가는지 볼 수 있습니다.

  1. 해결 된 퍼즐을 생성하려면 빈 보드에서 솔버를 실행하십시오. 유일한주의 사항은 솔버가 사용하는 “추측”을 무작위로 만들어야한다는 것입니다. 그렇지 않으면 매번 같은 퍼즐로 끝날 수 있습니다. 즉, 어떤 시점에서 솔버는 셀의 숫자를 시도합니다. 다음 순서로 시도해보십시오 1, 2, 3, 4, .... 작동하는 첫 번째 항목을 선택하십시오. 시도하려면 순서를 섞어 야합니다.4, 7, 2, 9, ... . 이 프로세스는 솔버만큼 빠릅니다.
  2. 숫자를 제거하려면이 알고리즘을 사용하십시오.
    • 이전에 제거하지 않은 난수를 선택하십시오.
    • 숫자를 제거하고 여기에서 제거 된 숫자를 사용할 수 없다는 추가 조건으로 솔버를 실행하십시오.
    • 솔버가 해를 구하면 숫자를 제거 할 수 없습니다
    • 숫자를 충분히 제거 할 때까지 (또는 더 이상 제거 할 수 없을 때까지) 반복하십시오.

이것은 매우 간단하고 순진한 방법이므로 누락 된 숫자의 수를 제외하고 또는 원하는 숫자의 양을 제거 할 수있는 경우를 제외하고 특정 어려움에 대한 퍼즐을 얻지 못할 수도 있습니다. 어쨌든 이것이 도움이되기를 바랍니다.


답변

웹 페이지 가 우리의 proyect 개발에 많은 도움 이 되었기 때문에 흥미 롭다고 생각합니다 . 독특한 솔루션으로 스도쿠를 만드는 것은 간단한 작업과는 거리가 멀습니다. 링크에서 당신은 저자 (그가 정말로 훌륭한 일을 해냈고, 그 누구도 아니었다!)가 몇 가지 다른 전략을 찾은 방법을 찾을 수 있습니다. 자신 만의 스도쿠 솔버를 생성하는 아이디어를 가질 수 있습니다.

이제 주제와 관련하여 비슷한 스도쿠를 생성하는 방법도 있습니다.

  1. 행의 순열입니다.
  2. 다른 간단한 해결책은 미니 문 17 자리 채우기의 스도쿠를 채우는 것으로 시작하고 (독특한 솔루션을 찾기 위해 입증 된 미니 문), 다른 전략을 따르십시오 (예 : 이전 링크에서 전략은 어려움으로 나뉘어 있습니다. 고유 한 솔루션에 도달 할 때까지 비슷한 것을 할 수 있습니다.
  3. 16 개의 시작 자리 고유 솔루션 스도쿠를 찾으려고하는 수학자 목록이 있었고 HUGEEEEEE 목록에는 17 자리의 스도쿠가 있습니다. 나는 그가 어떤 종류의 사본 쓰기를 가지고 있는지 기억할 수 없지만, 당신이 그에게 다른 17 가지 독특한 솔루션을 제공 할 수 있다면 스도쿠가 그의 데이터를 사용할 수있게 해 줄 것입니다.

알고리즘으로 건배와 행운을 빕니다 : D


답변

내 솔버가 무차별 대입을 사용하고 있으며 20 밀리 초 내에 솔루션을 찾을 수 있습니다. 위에서 설명한 삭제 방법을 사용하면 제 생성기가 200 밀리 초 내에 퍼즐을 생성합니다.

일반적으로 24-34 자리가 남아있는 퍼즐을 생성하는데, 여전히 세상에서 17 자리 퍼즐을 어떻게 만드는지 모르겠습니다.


답변