스도쿠 로직

0. 참고

http://blog.naver.com/ddaidock?Redirect=Log&logNo=40089636891

 

1. 룰

 - 3 * 3 안에 중복되는 숫자가 있으면 안됨

 - 가로9칸 세로9칸에 중복되는 숫자가 있으면 안됨

 

2. 로직

 2-1. 배치

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

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

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

 

2-1. 룰을 만족하기위해 위치변경(열 이동)

 - 파란색 3열로 이동 , 주황색 1열로 이동 , 빈공간 시프트

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

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

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

 

2-2. 룰을 만족하기위해 위치변경(행 이동)

 - 파란색 1행으로 이동 , 주황색 9행으로 이동 , 빈공간 시프트

 - 2-2의 과정을 거치면 스도쿠 룰을 만족한다.

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

 

3. randomize

 3-1. 묶음 단위로 이동

  - 조건 : 3 * 3 의 열단위(파란색 단위) 로 랜덤하게 위치 변경

  - 위치변경 대상의 조건은, 9 * 9 기준 같은 열로만 이동가능하고, 이동되는열의 합이 같은 것만 교체가능

  - 예. 9 * 9기준 1번째 열에서 파란색의 교체가능한 열은 주황색

  - 위의 조건으로 다른열과 행도 랜덤하게 섞음

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

 

3-2. 숫자변경

 - 9 * 9 기준 일정횟수만큼 숫자를 교환(랜덤으로 얻어진 값)

 

4. 정리

3까지의 과정을 거쳐도 값은 달라지겠지만, 3 * 3기준 열의 패턴은 바뀌지 않기때문에,

추가적인 보완 수단이 필요함.