스도쿠 솔루션 생성 CHECKER
여기 스도쿠 솔버 (Sudoku SOLVERS)가 있지만 인간적으로 가능한 작은 코드 체커 (code-golf) 솔루션을 만들고 싶습니다.
-
유효한 항목은 9×9 배열을 인수로 사용하거나 (참조에 의해 전달되고, 명령 행에 직렬화되거나 취하려고 함) 최종 그리드에 9 개의 9 행인 입력 파일을 승인 할 수 있습니다. . 아래 입력 예를 참조하십시오.
-
유효한 입력은 10 진수 (1-9) 여야합니다.
-
0이 아닌 결과를 반환하거나, 오류를 인쇄하거나, 또는 둘 다를 사용하여 누락되거나 비어 있거나 추가로 숫자가 아닌 위치 또는 숫자가 1-9가 아닌 위치는 유효하지 않은 입력으로 거부되어야합니다.
-
프로그램은 각 숫자가 열당 한 번, 줄당 한 번, 3×3 하위 표당 한 번 나타나는지 테스트해야합니다. 통과하면 “0”을 반환하고, 그렇지 않으면 0이 아닌 결과를 반환합니다.
-
외부 자원 (웹 사이트 등)의 사용은 피해야합니다.
-
솔루션이 독립형 프로그램 인 경우, “Pass”또는 “Fail”에 대해 각각 “0”또는 0이 아닌 종료 상태로 종료하거나 인쇄하는 것이 정상입니다.
가장 작은 답변이 이길 수 있습니다!
입력 예 :
c 배열 :
int input[9][9]={{1,2,3,4,5,6,7,8,9},
{4,5,6,7,8,9,1,2,3},
{7,8,9,1,2,3,4,5,6},
{2,3,1,5,6,4,8,9,7},
{5,6,4,8,9,7,2,3,1},
{8,9,7,2,3,1,5,6,4},
{3,1,2,6,4,5,9,7,8},
{6,4,5,9,7,8,3,1,2},
{9,7,8,3,1,2,6,4,5}
};
파일:
123456789
456789123
789123456
231564897
564897231
897231564
312645978
645978312
978312645
9 개의 하위 그리드 :
+---+---+---+
|123|456|789|
|456|789|123|
|789|123|456|
+---+---+---+
|231|564|897|
|564|897|231|
|897|231|564|
+---+---+---+
|312|645|978|
|645|978|312|
|978|312|645|
+---+---+---+
답변
GolfScript, 39 자
.zip.{3/}%zip{~}%3/{[]*}%++{$10,1>=!},,
배열 배열을 입력으로 사용하고 ( 온라인 예제 참조 ) 0
유효한 그리드 인 경우 출력 합니다.
코드에 대한 간단한 설명
.zip # Copy the input array and transpose it
.{3/}% # Split each line into 3 blocks
zip{~}% # Transpose these blocks
3/{[]*}% # Do the same for the lines themselves and join again
++ # Make one large list of 27 9-element arrays
# (9 for rows, 9 for columns, 9 for blocks)
{$10,1>=!}, # From those 27 select the ones which are not a permutation of [1 2 3 ... 9]
# $ -> sort
# 10,1> -> [1 2 3 ... 9]
# =! -> not equal
, # Count after filtering
답변
파이썬, 103
나는 스도쿠가 싫어.
b = [[1,2,3,4,5,6,7,8,9],
[4,5,6,7,8,9,1,2,3],
[7,8,9,1,2,3,4,5,6],
[2,3,1,5,6,4,8,9,7],
[5,6,4,8,9,7,2,3,1],
[8,9,7,2,3,1,5,6,4],
[3,1,2,6,4,5,9,7,8],
[6,4,5,9,7,8,3,1,2],
[9,7,8,3,1,2,6,4,5]]
e=enumerate;print 243-len(set((a,t)for(i,r)in e(b)for(j,t)in e(r)for a in e([i,j,i/3*3+j/3]*(0<t<10))))
작동 방식 : 각 행, 열 및 블록은 1에서 9까지의 각 숫자를 가져야합니다. 따라서 각 0 <= i, j < 9
셀 i,j
은 block에 3*floor(i/3) + floor(j/3)
있습니다. 따라서 충족해야 할 요구 사항은 243 개입니다. 각 요구 사항 을 0에서 8 사이의 숫자 이며, 행, 열 또는 블록을 나타내는 0, 1 또는 2 의 튜플 ((item index,item type number),symbol)
로 각각 항목 입니다.item index
item type number
symbol
b[i][j]
편집 : 실수로 유효한 항목을 확인하지 않았습니다. 이제 해
답변
APL (46)
{∧/,↑∊∘Z¨(/∘(,⍵)¨↓Z∘.=,3/3⌿3 3⍴Z←⍳9),(↓⍵),↓⍉⍵}
이것은 9×9 행렬을 취합니다. 예제는 다음과 같이 TryAPL에 입력 할 수 있습니다.
sudoku ← ↑(1 2 3 4 5 6 7 8 9)(4 5 6 7 8 9 1 2 3)(7 8 9 1 2 3 4 5 6)(2 3 1 5 6 4 8 9 7)(5 6 4 8 9 7 2 3 1)(8 9 7 2 3 1 5 6 4)(3 1 2 6 4 5 9 7 8)(6 4 5 9 7 8 3 1 2)(9 7 8 3 1 2 6 4 5)
{∧/,↑∊∘Z¨(/∘(,⍵)¨↓Z∘.=,3/3⌿3 3⍴Z←⍳9),(↓⍵),↓⍉⍵} sudoku
1
설명:
↓⍉⍵
:의 열을 얻을⍵
,↓⍵
:의 행을 얻을⍵
,3/3⌿3 3⍴Z←⍳9
: 숫자를 포함하는 3×3 행렬을 만듭니다.1
가9
3×3 만든 다음 각 숫자를 양방향으로 3 번 반복1
하여9
각 그룹 을 나타내는 숫자 가 포함 된 9×9 행렬을 제공합니다 .Z∘.=
: 각 번호1
에9
주어진 그룹에 대한 비트 마스크를 만들어,/∘(,⍵)¨
: 마스크⍵
와 각각 하여의 그룹을 제공합니다⍵
.∊∘Z¨
: 각 하위 배열에 대해 숫자가 포함되어 있는지 확인하십시오.1
가9
.∧/,↑
:이and
모든 숫자 의 논리 를 함께 취하십시오 .
답변
Java / C # -183 / 180181 / 178 173/170 바이트
boolean s(int[][]a){int x=0,y,j;int[]u=new int[27];for(;x<(y=9);x++)while(y>0){j=1<<a[x][--y];u[x]|=j;u[y+9]|=j;u[x/3+y/3*3+18]|=j;}for(x=0;x<27;)y+=u[x++];return y==27603;}
(변경 boolean
에bool
C 번호)
형식화 :
boolean s(int[][] a){
int x=0, y, j;
int[] u=new int[27];
for(;x<(y=9);x++)
while(y>0){
j=1<<a[x][--y];
u[x]|=j;
u[y+9]|=j;
u[x/3+y/3*3+18]|=j;
}
for(x=0;x<27;)
y+=u[x++];
return y==27603;
}
이 방법은 배열을 만듭니다 u
는 9 개의 행, 열 및 사각형에있는 숫자를 나타내는 27 비트 마스크 을 .
그런 다음 모든 셀을 반복하여 작업을 수행합니다. 1 << a[x][y]
하여 숫자를 나타내는 비트 마스크를 만들고 해당 열, 행 및 사각형 비트 마스크를 OR하는 비트 마스크를 만드는 을 합니다.
그런 다음 27 비트 마스크를 모두 반복하여 최대 27594까지 추가합니다 (1022 * 9, 1022는 모든 숫자 1-9의 비트 마스크 임). (참고y
이중 루프 다음에 이미 9가 포함되어 있기 때문에 27603으로 끝납니다.)
편집 : 실수로 %3
더 이상 필요하지 않습니다.
편집 2 : Bryce Wagner의 의견에서 영감을 받아 코드가 약간 압축되었습니다.
답변
파이썬 = 196
가장 골프는 아니지만 아이디어가 있습니다. 세트는 매우 유용합니다.
판:
b = [[1,2,3,4,5,6,7,8,9],
[4,5,6,7,8,9,1,2,3],
[7,8,9,1,2,3,4,5,6],
[2,3,1,5,6,4,8,9,7],
[5,6,4,8,9,7,2,3,1],
[8,9,7,2,3,1,5,6,4],
[3,1,2,6,4,5,9,7,8],
[6,4,5,9,7,8,3,1,2],
[9,7,8,3,1,2,6,4,5]]
프로그램:
n={1,2,3,4,5,6,7,8,9};z=0
for r in b:
if set(r)!=n:z=1
for i in zip(*b):
if set(i)!=n:z=1
for i in (0,3,6):
for j in (0,3,6):
k=j+3
if set(b[i][j:k]+b[i+1][j:k]+b[i+2][j:k])!=n:z=1
print(z)
답변
Java- 385306328260 문자
편집 :
나는 대답 이 완전한 프로그램이어야 한다는 지시를 어리석게 잘못 읽었습니다 . 그것은 유효한 함수 일 수 있기 때문에 함수로 다시 작성하고 최소화했으며 솔루션 소개를 염두에두고 다시 작성했습니다.
따라서 나 자신에게 도전으로 가장 작은 Java 솔루션 검사기를 만들려고한다고 생각했습니다.
이것을 달성하기 위해 스도쿠 퍼즐이 자바 다차원 배열로 전달 될 것이라고 가정합니다.
s(new int[][] {
{1,2,3,4,5,6,7,8,9},
{4,5,6,7,8,9,1,2,3},
{7,8,9,1,2,3,4,5,6},
{2,3,1,5,6,4,8,9,7},
{5,6,4,8,9,7,2,3,1},
{8,9,7,2,3,1,5,6,4},
{3,1,2,6,4,5,9,7,8},
{6,4,5,9,7,8,3,1,2},
{9,7,8,3,1,2,6,4,5}});
그런 다음 유효한 솔버가 있는데, 유효한 솔루션이면 “0”, 그렇지 않으면 “1”을 반환합니다.
완전 골프 :
int s(int[][] s){int i=0,j,k=1;long[] f=new long[9];long r=0L,c=r,g=r,z=45L,q=r;for(f[0]=1L;k<9;){f[k]=f[k-1]*49;z+=f[k++]*45;}for(;i<9;i++){for(j=0;j<9;){k=s[i][j];r+=k*f[i];c+=k*f[j];g+=k*f[j++/3+3*(i/3)];q+=5*f[k-1];}}return (r==z&&c==z&&g==z&&q==z)?0:1;}
읽을 수있는 :
int s(int[][] s) {
int i=0,j,k=1;
long[] f=new long[9];
long r=0L,c=r,g=r,z=45L,q=r;
for(f[0]=1L;k<9;){f[k]=f[k-1]*49;z+=f[k++]*45;}
for(;i<9;i++) {
for (j=0;j<9;) {
k=s[i][j];
r+=k*f[i];
c+=k*f[j];
g+=k*f[j++/3+3*(i/3)];
q+=5*f[k-1];
}
}
return (r==z&&c==z&&g==z&&q==z)?0:1;
}
어떻게 작동합니까? 나는 기본적으로 각 숫자에서 충분한 해상도로 내 자신의 숫자를 작성합니다. 단지 퍼즐을 한 번 통과 한 후 세 개의 숫자 비교 만하면됩니다. 이 문제에 대해베이스 49를 선택했지만 45보다 큰베이스이면 충분합니다.
(희망스럽게) 분명한 예 : 스도쿠 퍼즐의 모든 “행”은 기본 -49 숫자의 한 자릿수라고 상상해보십시오. 우리는 단순화를 위해 기본 49 숫자의 각 숫자를 벡터에서 기본 10 숫자로 표시합니다. 따라서 모든 행이 “정확한”경우 다음과 같은 base-49 숫자 (base-10 벡터)가 필요합니다.
(45,45,45,45,45,45,45,45,45)
또는 단일 10 진수로 변환 : 1526637748041045
모든 열에 대해 유사한 논리를 따르고 “하위 그리드”에 대해 동일한 논리를 따르십시오. 최종 분석에서이 “이상적인 숫자”와 다른 값은 퍼즐 솔루션이 유효하지 않음을 의미합니다.
모든 5 취약점 및 기타 관련 문제를 해결하기 위해 편집 : 모든 퍼즐에 각 숫자 중 9 개가 있어야한다는 아이디어를 기반으로 네 번째 기본 49 숫자를 추가합니다. 따라서, 나는 숫자의 색인을 나타내는 10 진수의 숫자가 나타날 때마다 49 자리 숫자의 각 숫자에 5를 추가합니다. 예를 들어, 10 9 및 9 8, 9 7, 8 6 및 9가있는 경우 오버플로를 처리하기 위해 10을 기준으로하는 10의 10 벡터로 기본 49 숫자를 얻습니다.
(1, 1, 45, 45, 40, 45, 45, 45, 45, 45)
“이상적인”base-49 숫자와 비교할 때 실패합니다.
내 솔루션은 가능한 한 반복 및 비교를 피하기 위해이 수학 솔루션을 활용합니다. 나는 단순히 long
값을 사용하여 각 기수 49 숫자를 기수 10 숫자로 저장하고 조회 배열을 사용하여 열 / 행 / 서브 그리드 체크 값 계산 중에 각 기수 49 자리의 “인자”를 얻습니다.
Java가 간결하게 설계되지 않았기 때문에 수학적 구성에주의를 기울이는 것이 간결한 검사기를 구성 할 수있는 유일한 방법이었습니다.
당신이 무슨 생각을하는지 제게 알려주세요.
답변
R 145
function(x)colSums(do.call(rbind,lapply(list(R<-row(b<-matrix(1,9,9)),C<-col(b),(R-1)%/%3+1+3*(C-1)%/%3),sapply,`==`,1:9))%*%c(2^(x-1))==511)==27
디 골프 된 코드 (더 많거나 적은)는 /programming//a/21691541/1201032 에서 찾을 수 있습니다 .