고유 한 솔루션으로 스도쿠 보드를 생성하는 방법

고유 한 솔루션으로 스도쿠 보드를 생성하는 방법

---

고유 한 솔루션으로 스도쿠 보드를 어떻게 생성합니까? 내가 생각한 것은 임의의 보드를 초기화하고 일부 번호를 제거하는 것입니다. 하지만 내 질문은 솔루션의 고유성을 어떻게 유지합니까?

---

쉬운:

1. 효율적인 역 추적 알고리즘으로 모든 솔루션을 찾으십시오.
2. 솔루션이 하나만 있으면 완료된 것입니다. 그렇지 않으면 솔루션이 둘 이상인 경우 대부분의 솔루션이 다른 위치를 찾으십시오. 이 위치에 숫자를 추가하십시오.
3. 1로 이동합니다.

이것보다 훨씬 더 빠른 해결책을 찾을 수 있을지 의문입니다.

---

내 자신의 SuDoKu 프로그램이 수행하는 방식은 다음과 같습니다.

---

1. 완전하고 유효한 보드 (81 개의 숫자로 채워짐)로 시작하십시오.

2. 모든 81 개의 셀 위치 목록을 만들고 무작위로 섞습니다.

3. 목록이 비어 있지 않은 한 목록에서 다음 위치를 가져와 관련 셀에서 번호를 제거하십시오.

4. 빠른 역 추적 솔버를 사용하여 고유성을 테스트합니다. 내 솔버는 이론상 모든 솔루션을 계산할 수 있지만 고유성을 테스트하기 위해 둘 이상의 솔루션을 찾으면 즉시 중지됩니다.

5. 현재 보드에 여전히 솔루션이 하나만있는 경우 3) 단계로 이동하여 반복합니다.

6. 현재 보드에 솔루션이 두 개 이상있는 경우 마지막 제거 (3 단계)를 실행 취소하고 목록에서 다음 위치로 3 단계를 계속합니다.

7. 81 개 위치를 모두 테스트하면 중지하십시오.

---

이를 통해 고유 한 보드뿐만 아니라 솔루션의 고유성을 파괴하지 않고는 더 이상 번호를 제거 할 수없는 보드를 제공합니다.

물론 이것은 알고리즘의 후반에 불과합니다. 전반부는 먼저 완전한 유효한 보드를 찾는 것입니다 (무작위로 채워짐!) 매우 유사하지만 "다른 방향으로"작동합니다.

---

1. 빈 보드로 시작하십시오.

2. 자유 셀 중 하나에 임의의 숫자를 추가합니다 (셀은 임의로 선택되고 숫자는 SuDoKu 규칙에 따라이 셀에 유효한 숫자 목록에서 임의로 선택됨).

3. 역 추적 솔버를 사용하여 현재 보드에 유효한 솔루션이 하나 이상 있는지 확인합니다. 그렇지 않은 경우 2 단계를 실행 취소하고 다른 번호와 셀로 반복합니다. 이 단계는 자체적으로 완전한 유효한 보드를 생성 할 수 있지만 무작위가 아닙니다.

4. 보드가 숫자로 완전히 채워질 때까지 반복합니다.

---

속일 수 있습니다. 해결할 수있는 기존 스도쿠 보드로 시작한 다음 조작 해보세요.

3x3 블록의 행을 다른 행과 교환 할 수 있습니다. 3x3 블록 3 개의 열을 다른 열로 바꿀 수 있습니다. 각 블록 행 또는 블록 열 내에서 단일 행과 단일 열을 바꿀 수 있습니다. 마지막으로 순열이 전체 보드에서 일관되는 ​​한 채워진 위치에 다른 숫자가 있도록 숫자를 순열 할 수 있습니다.

이러한 변경으로 인해 해결 가능한 보드를 해결할 수 없습니다.

---

P = NP가 아니면 정확히 하나의 솔루션으로 일반적인 스도쿠 문제를 생성하기위한 다항식 시간 알고리즘이 없습니다.

그의 석사 논문에서 Takayuki Yato 는 문제에 대한 다른 해결책을 찾거나 존재하지 않음을 보여주는 것이 목표 인 또 다른 해결책 문제 (ASP)를 정의했습니다 . Yato는 다른 솔루션을 찾기 어려운 문제인 ASP- 완전성을 정의하고 Sudoku가 ASP- 완전임을 보여주었습니다. 그는 또한 ASP- 완전성이 NP- 경도를 의미한다는 것을 증명하기 때문에 임의의 크기의 스도쿠 보드를 허용한다면 생성 한 퍼즐에 고유 한 솔루션이 있는지 확인하는 다항식 시간 알고리즘이 없습니다 (P = NP).

빠른 알고리즘에 대한 희망을 망쳐 서 죄송합니다!

---

솔루션은 두 부분으로 나뉩니다.
A. 숫자 패턴 6,000 억
생성 B. 마스킹 패턴 생성 ~ 7e23 조합

번호 패턴으로 독특한 조합을 생성 할 수있는 가장 빠른 방법에 대한 A) NO의 역 추적이나 테스트에 소요되는 시간을

1 단계. 이미 종료 된 매트릭스를 선택합니다. 컴퓨팅 장치 나 솔버의 도움없이 사람이 쉽게 만들 수있는 아래 매트릭스를 선택했습니다.

첫 번째 행은 오름차순 숫자입니다.
두 번째 행도 오름차순이지만 4에서 시작하여 주위를 굴립니다.
세 번째 행도 오름차순이지만 7에서 시작하여
4,5,6 행을 굴 립니다 : 세 셀 열을 맨 위로 바꿉니다. 오른쪽 열-2 5 8 및 마지막 열
7,8,9 행 의 3x3 셀 내에서 롤 : 3 셀 열을 오른쪽 상단 열-3 6 9로 교체하고 마지막 열의 3x3 셀 내에서 롤

12 34 5678 9
4 5678 9 12
34 5 6
2 3 1 5678 9 7
5678 9 7 2 3 1
8 9 7 2 3 1 5 6 4
3 1 2 6 4 597 8
6 4 597 8 3 1 2
9 7 8 3 1 2 6 4 5

Step 2. Shuffle the the digits and replace in all other cells
Step 3. Randomly rearrange columns 1,2 and 3 within themselves
Step 4. Randomly rearrange columns 4,5 and 6 within themselves
Step 5. Randomly rearrange columns 7,8 and 9 within themselves
Step 6. Randomly rearrange rows 1,2 and 3 within themselves
Step 7. Randomly rearrange rows 4,5 and 6 within themselves
Step 8. Randomly rearrange rows 7,8 and 9 within themselves
Step 9. Randomly rearrange in 3 column groups of size 9x3
Step 10. Randomly rearrange in 3 row groups of size 3x9

voila...

5 8 3 1 6 4 9 7 2
7 2 9 3 5 8 1 4 6
1 4 6 2 7 9 3 8 5
8 5 2 6 9 1 4 3 7
3 1 7 4 2 5 8 6 9
6 9 4 8 3 7 2 5 1
4 6 5 9 1 3 7 2 8
2 3 1 7 8 6 5 9 4
9 7 8 5 4 2 6 1 3

B ) For Masking Pattern we need to have a solver algorithm. As we already have a quite unique number grid (which is also solved!) this gives us faster performance for using solver

Step 1: Start with selecting 15 random locations out of the 81.
Step 2: Check with solver whether it has unique solution
Step 3: If solution not unique select additional location. iterate Steps 2 and 3 until unique solution found

This should give you the very unique and fast Sudoku board.

---

It's not easy to give a generic solution. You need to know a few things to generate a specific kind of Sudoku... for example, you cannot build a Sudoku with more than nine empty 9-number groups (rows, 3x3 blocks or columns). Minimum given numbers (i.e. "clues") in a single-solution Sudoku is believed to be 17, but number positions for this Sudoku are very specific if I'm not wrong. The average number of clues for a Sudoku is about 26, and I'm not sure but if you quit numbers of a completed grid until having 26 and leave those in a symmetric way, you may have a valid Sudoku. On the other hand, you can just randomly quit numbers from completed grids and testing them with CHECKER or other tools until it comes up with an OK.

---

Here is a way to make a classic sudoku puzzle (sudoku puzzle with one and only solution; pre-filled squares are symmetrical around the center square R5C5).

1) start with a complete grid (using group filling plus circular shift to get it easily)

2) remove number(s) from two symmetrical squares if the cleared squares can be inferred using the remaining clues.

3) repeat (2) until all the numbers are checked.

Using this method you can create a very easy sudoku puzzle with or without programming. You can also use this method to craft harder Sudoku puzzles. You may want to search "create classic sudoku" on YouTube to have a step by step example.

---

I also think that you will have to explicitly check uniqueness. If you have less than 17 givens, a unique solution is very unlikely, though: None has yet been found, although it is not clear yet whether it might exist.)

But you can also use a SAT-solver, as opposed to writing an own backtracking algorithm. That way, you can to some extent regulate how difficult it will be to find a solution: If you restrict the inference rules that the SAT-solver uses, you can check whether you can solve the puzzle easily. Just google for "SAT solving sudoku".

---

One way to generate sudoku faster.

1. find an exist sudoku.
2. exchange the value with a random group.
3. exchange the cell or the column or the row-grid or the column-grid.

You exchange the value will make the value different, if not exchange the rows or the column, the sudoku isn't changed in the essential.

You can flag the sudoku with 9 grids, the rows and column exchanged must do in the same grid. Like you can exchange row1-3, row4-6, row7-9, don't exchange row1-4 or row1-7. You can also exchange the row-grid(exchange row1~3 with the row4~6 or row7~9).

Solve the sudoku: record the empty with all the possible value, then check the value from 1 to 9. If one value is unique, remove it from the loop.

참고URL : https://stackoverflow.com/questions/6924216/how-to-generate-sudoku-boards-with-unique-solutions