이 게임의 수학적 / 계산 원칙은 무엇입니까?
내 아이들은 Spot It 이라는 재미있는 게임을 가지고 있습니다 ! 게임 제약은 (내가 가장 잘 설명 할 수있는) :
- 55 장의 덱
- 각 카드에는 8 개의 고유 한 사진이 있습니다 (예 : 카드에 동일한 사진 중 2 개를 가질 수 없음)
- 갑판에서 2 장의 카드를 선택하면 1 장의 일치하는 그림 만 있습니다.
- 일치하는 그림은 다른 카드에서 다르게 크기가 조절 될 수 있지만 게임을 더 어렵게 만드는 것입니다 (예 : 작은 나무는 여전히 큰 나무와 일치합니다)
게임의 원칙은 2 장의 카드를 뒤집어 놓고 먼저 일치하는 그림을 선택하는 사람이 점수를 얻는 것입니다.
다음은 설명을위한 그림입니다.
(예 : 위 2 장의 카드에서 일치하는 그림이 녹색 공룡임을 알 수 있습니다. 오른쪽 아래 그림과 오른쪽 가운데 그림 사이에는 광대 머리입니다.)
다음을 이해하려고합니다.
이러한 기준을 충족시키는 데 필요한 최소 그림 수는 얼마이며 어떻게 결정합니까?
의사 코드 (또는 Ruby)를 사용하여 N 개의 그림 배열에서 55 개의 게임 카드를 어떻게 생성 할 수 있습니까 (N은 질문 1의 최소 숫자)?
최신 정보:
사진은 덱당 두 번 이상 발생합니다 (일부는 예상 한 것과 반대). 각각 번개 모양의 3 장의 카드 그림을보십시오.
유한 한 투영 기하학
공리 의 투영 (평면) 기하학은 유클리드 기하학보다 약간 다릅니다 :
- 두 점마다 정확하게 하나의 선이 있습니다 (이것은 동일합니다).
- 두 줄은 모두 정확히 한 지점에서 만나게됩니다 (유클리드와는 조금 다릅니다).
이제 수프 에 "finite" 를 추가 하면 질문이 있습니다.
우리는 단지 2 점을 가진 기하학을 가질 수 있습니까? 3 점? 4로? 7로?
이 문제와 관련하여 여전히 공개적인 질문이 있지만 우리는 이것을 알고 있습니다 :
- 와 형상이있는 경우
Q포인트는 다음Q = n^2 + n + 1과n호출되는order형상의합니다. n+1모든 라인에 포인트 가 있습니다 .- 모든 지점에서 정확하게
n+1선을 전달하십시오 . 총 줄 수는 또한
Q입니다.그리고 마지막으로
n소수라면 order의 지오메트리가 존재합니다n.
그것이 퍼즐과 어떤 관련이 있는지 묻습니다.
넣어 card대신 point과 picture대신 line과 공리가 될 :
- 두 장의 카드마다 정확히 하나의 공통점이 있습니다.
- 두 장의 사진마다 두 장의 카드가 정확히 하나 있습니다.
이제을 사용 n=7하여 order-7유한 형상을 갖습니다 Q = 7^2 + 7 + 1. 그러면 Q=57선 (그림)과 Q=57점 (카드)이 만들어집니다. 퍼즐 제작자들은 55가 57보다 둥근 숫자이고 2 장의 카드를 남겼다고 결정한 것 같습니다.
우리는 또한 n+1 = 8모든 포인트 (카드), 8 라인 패스 (8 그림이 나타남) 및 모든 라인 (사진)에 8 포인트가 있습니다 (8 카드에 나타남).
다음 은 Noelle Evans-Finite Geometry Problem Page 에서 복사 한 Fano Plane 이라는 7 개의 점이있는 가장 유명한 유한 투영법 (order-2) 평면 (형상)의 표현입니다.
위의 order-2 평면이 7 장의 카드와 7 장의 그림으로 비슷한 퍼즐을 만드는 방법을 설명하는 이미지를 만들려고 생각했지만 math.exchange 쌍둥이 질문의 링크에는 정확히 같은 다이어그램이 있습니다 .Dobble-et- 라 기하학 피니
따라서 총 n 장의 사진 에서 m = 8 장의 사진이 포함 된 k = 55 장의 카드가 있습니다. 우리는 '얼마나 많은 사진 문제를 다시 언급 할 수 없음 우리는 세트 구성 할 수 있도록, 우리가 필요로 할 k 개의 카드의 쌍 사이에 하나 개의 공유 사진과 함께 카드를?' 다음과 같이 질문하여 동등하게
감안할 때 N 차원 벡터 공간 정확하게 포함 된 모든 벡터, 세트 해요 요소가 하나의 다른 모든 제로인를 큰이 얼마나 N 우리가 세트 찾을 수 있도록 할 수 케이 누구의 페어 점 제품입니다 벡터를, 모두 1 과 같 습니까?
쌍을 만들 수 있는 정확히 ( n choose m ) 가능한 벡터가 있습니다. 따라서 ( n은 m을 선택 )> = k가 되도록 충분히 큰 n이 필요합니다 . 이것은 하한에 불과하므로 쌍별 호환성 제약 조건을 충족하려면 훨씬 높은 n 이 필요할 수 있습니다 .
약간의 실험을 위해 유효한 카드 세트를 계산하는 작은 Haskell 프로그램을 작성했습니다.
편집 : 나는 Neil과 Gajet의 솔루션을 본 후에 내가 사용하는 알고리즘이 항상 최상의 솔루션을 찾지 못한다는 것을 깨달았으므로 아래의 모든 것이 반드시 유효한 것은 아닙니다. 곧 코드를 업데이트하려고합니다.
module Main where
cardCandidates n m = cardCandidates' [] (n-m) m
cardCandidates' buildup 0 0 = [buildup]
cardCandidates' buildup zc oc
| zc>0 && oc>0 = zerorec ++ onerec
| zc>0 = zerorec
| otherwise = onerec
where zerorec = cardCandidates' (0:buildup) (zc-1) oc
onerec = cardCandidates' (1:buildup) zc (oc-1)
dot x y = sum $ zipWith (*) x y
compatible x y = dot x y == 1
compatibleCards = compatibleCards' []
compatibleCards' valid [] = valid
compatibleCards' valid (c:cs)
| all (compatible c) valid = compatibleCards' (c:valid) cs
| otherwise = compatibleCards' valid cs
legalCardSet n m = compatibleCards $ cardCandidates n m
main = mapM_ print [(n, length $ legalCardSet n m) | n<-[m..]]
where m = 8
처음 몇 개의 n에 대해 n 에서 선택할 수있는 다른 사진 수에 대해 m = 8 장의 카드 당 최대 호환 가능한 카드 수는 다음과 같습니다.
이 무차별 강제 방법은 조합 폭발로 인해 멀지 않습니다. 그러나 나는 그것이 여전히 흥미로울 것이라고 생각했다.
흥미롭게도 주어진 m 에 대해 k 는 n 을 특정 n 까지만 증가 시킨 후 일정하게 유지되는 것으로 보입니다 .
즉, 카드 당 모든 사진 수에 대해 선택할 수있는 특정 수의 사진이 있으므로 가능한 최대 수의 법적 카드가됩니다. 최적의 수를 초과하여 선택하기 위해 더 많은 사진을 추가해도 더 이상 유효한 카드 수는 증가하지 않습니다.
처음 몇 최적 k 는 다음과 같습니다.
57 포인트로 투영 평면 지오메트리를 파악하는 데 어려움이있는 사람들을 위해 57 개의 카드와 57 개의 심볼로 게임을 구성하는 정말 훌륭하고 직관적 인 방법 이 있습니다 (이 질문에 대한 Yuval Filmus 의 답변을 기반으로 함 ).
- 8 개의 심볼이있는 카드의 경우 고유 한 심볼의 7x7 격자를 만듭니다.
- 0에서 6까지의 "기울기"에 대해 8 개의 기호를 추가하고 무한대 기울기에 대한 기호를 추가하십시오.
- 각 카드는 그리드의 선 (7 기호)에 선의 경사에 대해 설정된 경사에서 하나의 기호를 더한 것입니다. 선은 오프셋 (즉, 왼쪽의 시작점)과 기울기 (즉, 각 단계 오른쪽에 올릴 심볼 수)가 있습니다. 선이 맨 위에 그리드를 떠나면 맨 아래에 다시 입력하십시오. 이러한 두 가지 카드에 대해서는이 예제 그림 ( boardgamegeek의 그림)을 참조하십시오 .
이 예에서는 기울기 0 (빨간색)이있는 선과 기울기 1 (녹색)이있는 선을 하나 사용합니다. 그들은 정확히 하나의 공통점 (올빼미)에서 교차합니다.
이 방법을 사용하면 두 카드에 정확히 하나의 공통 기호가 있어야합니다.
- 경사가 다른 경우 선은 항상 정확히 한 지점에서 교차합니다.
- 경사가 동일하면 선이 교차하지 않고 그리드에서 공통 기호가 없습니다. 이 경우 경사 기호는 동일합니다.
이런 식으로, 우리는 7x7 카드 (7 개의 오프셋과 7 개의 슬로프)를 구성 할 수 있습니다.
또한 수직선에서 그리드를 통해 7 개의 추가 카드를 구성 할 수도 있습니다 (즉, 각 열을 가져가는 경우). 이를 위해 무한대 기울기 아이콘이 사용됩니다.
각 카드는 그리드의 7 개 심볼과 정확히 하나의 "슬로프"심볼로 구성되므로 8 개의 슬로프 심볼 모두로 구성된 하나의 추가 카드를 만들 수 있습니다.
이것은 우리에게 7x8 + 1 = 57 가능한 카드와 7 x 7 + 8 = 57 필요한 기호를 남깁니다.
(기본적으로 이것은 소수 크기의 그리드에서만 작동합니다 (예 : n = 7). 그렇지 않으면 경사가 그리드 크기의 제수 인 경우 경사가 다른 선의 교차점이 0 개 이상일 수 있습니다.
다른 사람들은 디자인의 일반적인 프레임 워크 (유한 투영 평면)를 설명하고 소수의 유한 투영 평면을 생성하는 방법을 보여주었습니다. 나는 약간의 차이를 채우고 싶습니다.
유한 투영면은 여러 가지 다른 순서로 생성 될 수 있지만, 소수의 경우 가장 간단합니다 p. 그런 다음 정수 모듈러스 p는 유한 필드를 형성하여 평면의 점과 선에 대한 좌표를 설명하는 데 사용할 수 있습니다. 이 점에 대한 좌표의 3 가지 종류가 있습니다 (1,x,y), (0,1,x)그리고 (0,0,1)여기서 x과 y에서 값을 취할 수 0에 p-1. 3 가지 종류의 포인트는 p^2+p+1시스템의 포인트 수에 대한 공식 을 설명합니다 . : 우리는 또한 좌표의 같은 3 가지 종류의 라인을 설명 할 수 있습니다 [1,x,y], [0,1,x]하고 [0,0,1].
좌표의 내적이 0 mod인지에 따라 점과 선의 입사 여부를 계산합니다 p. 예를 들어 그 이후 에는 점 (1,2,5)과 선 [0,1,1]이 입사 하지만 그 p=7이후 1*0+2*1+5*1 = 7 == 0 mod 7에는 점 (1,3,3)과 선 [1,2,6]이 입사되지 않습니다 1*1+3*2+3*6 = 25 != 0 mod 7.
카드와 그림의 언어로 번역하면 좌표 (1,2,5)가있는 카드에는 좌표 가있는 그림이 포함 [0,1,1]되지만 좌표 (1,3,3)가 있는 카드에는 좌표 가있는 그림이 포함되지 않습니다 [1,2,6]. 이 절차를 사용하여 전체 카드 목록과 그 안에 들어있는 그림을 개발할 수 있습니다.
그건 그렇고, 그림을 점과 카드로 선으로 생각하는 것이 더 쉽다고 생각하지만 점과 선 사이의 투영 지오메트리에는 이중성이 있으므로 실제로 중요하지 않습니다. 그러나 다음에 나는 그림에 포인트를 사용하고 카드에 라인을 사용할 것입니다.
유한 필드에도 동일한 구성이 적용됩니다. 우리는 q단지 q=p^k주된 힘 이라면 유한 한 순서의 필드가 있다는 것을 알고 있습니다. 필드가 호출됩니다 GF(p^k)"갈루아 필드"를 의미한다. 필드는 프라임 케이스에서와 같이 프라임 전원 케이스에서 구성하기가 쉽지 않습니다.
다행스럽게도이 노력은 이미 자유 소프트웨어 인 Sage 에서 수행되고 구현되었습니다 . 예를 들어, 순서 4의 투영 평면 설계를 얻으려면
print designs.ProjectiveGeometryDesign(2,1,GF(4,'z'))
그리고 당신은 다음과 같은 출력을 얻을 것입니다
ProjectiveGeometryDesign<points=[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10,
11, 12, 13, 14, 15, 16, 17, 18, 19, 20], blocks=[[0, 1, 2, 3, 20], [0,
4, 8, 12, 16], [0, 5, 10, 15, 19], [0, 6, 11, 13, 17], [0, 7, 9, 14,
18], [1, 4, 11, 14, 19], [1, 5, 9, 13, 16], [1, 6, 8, 15, 18], [1, 7,
10, 12, 17], [2, 4, 9, 15, 17], [2, 5, 11, 12, 18], [2, 6, 10, 14, 16],
[2, 7, 8, 13, 19], [3, 4, 10, 13, 18], [3, 5, 8, 14, 17], [3, 6, 9, 12,
19], [3, 7, 11, 15, 16], [4, 5, 6, 7, 20], [8, 9, 10, 11, 20], [12, 13,
14, 15, 20], [16, 17, 18, 19, 20]]>
위의 내용을 다음과 같이 해석합니다. 0에서 20까지 레이블이 지정된 21 개의 그림이 있습니다. 각 블록 (투영 형상의 선)은 카드에 어떤 그림이 나타나는지 알려줍니다. 예를 들어, 첫 번째 카드에는 사진 0, 1, 2, 3 및 20이 있습니다. 두 번째 카드에는 사진 0, 4, 8, 12 및 16이 있습니다. 등등.
주문 7의 시스템은
print designs.ProjectiveGeometryDesign(2,1,GF(7))
출력을 생성하는
ProjectiveGeometryDesign<points=[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10,
11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28,
29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46,
47, 48, 49, 50, 51, 52, 53, 54, 55, 56], blocks=[[0, 1, 2, 3, 4, 5, 6,
56], [0, 7, 14, 21, 28, 35, 42, 49], [0, 8, 16, 24, 32, 40, 48, 50], [0,
9, 18, 27, 29, 38, 47, 51], [0, 10, 20, 23, 33, 36, 46, 52], [0, 11, 15,
26, 30, 41, 45, 53], [0, 12, 17, 22, 34, 39, 44, 54], [0, 13, 19, 25,
31, 37, 43, 55], [1, 7, 20, 26, 32, 38, 44, 55], [1, 8, 15, 22, 29, 36,
43, 49], [1, 9, 17, 25, 33, 41, 42, 50], [1, 10, 19, 21, 30, 39, 48,
51], [1, 11, 14, 24, 34, 37, 47, 52], [1, 12, 16, 27, 31, 35, 46, 53],
[1, 13, 18, 23, 28, 40, 45, 54], [2, 7, 19, 24, 29, 41, 46, 54], [2, 8,
14, 27, 33, 39, 45, 55], [2, 9, 16, 23, 30, 37, 44, 49], [2, 10, 18, 26,
34, 35, 43, 50], [2, 11, 20, 22, 31, 40, 42, 51], [2, 12, 15, 25, 28,
38, 48, 52], [2, 13, 17, 21, 32, 36, 47, 53], [3, 7, 18, 22, 33, 37, 48,
53], [3, 8, 20, 25, 30, 35, 47, 54], [3, 9, 15, 21, 34, 40, 46, 55], [3,
10, 17, 24, 31, 38, 45, 49], [3, 11, 19, 27, 28, 36, 44, 50], [3, 12,
14, 23, 32, 41, 43, 51], [3, 13, 16, 26, 29, 39, 42, 52], [4, 7, 17, 27,
30, 40, 43, 52], [4, 8, 19, 23, 34, 38, 42, 53], [4, 9, 14, 26, 31, 36,
48, 54], [4, 10, 16, 22, 28, 41, 47, 55], [4, 11, 18, 25, 32, 39, 46,
49], [4, 12, 20, 21, 29, 37, 45, 50], [4, 13, 15, 24, 33, 35, 44, 51],
[5, 7, 16, 25, 34, 36, 45, 51], [5, 8, 18, 21, 31, 41, 44, 52], [5, 9,
20, 24, 28, 39, 43, 53], [5, 10, 15, 27, 32, 37, 42, 54], [5, 11, 17,
23, 29, 35, 48, 55], [5, 12, 19, 26, 33, 40, 47, 49], [5, 13, 14, 22,
30, 38, 46, 50], [6, 7, 15, 23, 31, 39, 47, 50], [6, 8, 17, 26, 28, 37,
46, 51], [6, 9, 19, 22, 32, 35, 45, 52], [6, 10, 14, 25, 29, 40, 44,
53], [6, 11, 16, 21, 33, 38, 43, 54], [6, 12, 18, 24, 30, 36, 42, 55],
[6, 13, 20, 27, 34, 41, 48, 49], [7, 8, 9, 10, 11, 12, 13, 56], [14, 15,
16, 17, 18, 19, 20, 56], [21, 22, 23, 24, 25, 26, 27, 56], [28, 29, 30,
31, 32, 33, 34, 56], [35, 36, 37, 38, 39, 40, 41, 56], [42, 43, 44, 45,
46, 47, 48, 56], [49, 50, 51, 52, 53, 54, 55, 56]]>
방금 57 또는 58 장의 사진으로 할 수있는 방법을 찾았지만 지금은 두통이 심합니다. 잘 잤다면 8-10 시간 후에 루비 코드를 게시 할 것입니다! 내 힌트는 7 카드마다 동일한 마크를 공유하며 내 솔루션을 사용하여 총 56 개의 카드를 구성 할 수 있습니다.
다음은 ypercube가 말한 57 개의 카드를 모두 생성하는 코드입니다. 그것은 정확히 57 장의 그림을 사용하며, 죄송합니다. 실제 C ++ 코드를 작성했지만 이것이 vector <something>유형 값을 포함하는 배열 임을 알면 something이 코드의 기능을 이해하기 쉽습니다. 이 코드는 각각의 그림이 포함 된 그림을 사용하고 모든 소수 P 값에 대해 하나의 그림 만 공유 하는 P^2+P+1카드를 생성 합니다. 즉, 3 장의 사진 (p = 2의 경우), 13 장의 사진 (p = 3의 경우), 13 장의 31 장 (p = 5의 경우), 31 장의 57 장 (57 장의 57 장)의 7 장의 사진을 7 장 사용할 수 있습니다. (p = 7) 등등 ...P^2+P+1P+1
#include <iostream>
#include <vector>
using namespace std;
vector <vector<int> > cards;
void createcards(int p)
{
cards.resize(0);
for (int i=0;i<p;i++)
{
cards.resize(cards.size()+1);
for(int j=0;j<p;j++)
{
cards.back().push_back(i*p+j);
}
cards.back().push_back(p*p+1);
}
for (int i=0;i<p;i++)
{
for(int j=0;j<p;j++)
{
cards.resize(cards.size()+1);
for(int k=0;k<p;k++)
{
cards.back().push_back(k*p+(j+i*k)%p);
}
cards.back().push_back(p*p+2+i);
}
}
cards.resize(cards.size()+1);
for (int i=0;i<p+1;i++)
cards.back().push_back(p*p+1+i);
}
void checkCards()
{
cout << "---------------------\n";
for(unsigned i=0;i<cards.size();i++)
{
for(unsigned j=0;j<cards[i].size();j++)
{
printf("%3d",cards[i][j]);
}
cout << "\n";
}
cout << "---------------------\n";
for(unsigned i=0;i<cards.size();i++)
{
for(unsigned j=i+1;j<cards.size();j++)
{
int sim = 0;
for(unsigned k=0;k<cards[i].size();k++)
for(unsigned l=0;l<cards[j].size();l++)
if (cards[i][k] == cards[j][l])
sim ++;
if (sim != 1)
cout << "there is a problem between cards : " << i << " " << j << "\n";
}
}
}
int main()
{
int p;
for(cin >> p; p!=0;cin>> p)
{
createcards(p);
checkCards();
}
}
지연된 코드에 대해 다시 한 번 죄송합니다.
파이썬이 더 읽기 쉽기 때문에 파이썬에서 Gajet의 솔루션이 있습니다. 프라임이 아닌 숫자와도 작동하도록 수정했습니다. Thies 통찰력을 사용하여 좀 더 이해하기 쉬운 디스플레이 코드를 생성했습니다.
from __future__ import print_function
from itertools import *
def create_cards(p):
for min_factor in range(2, 1 + int(p ** 0.5)):
if p % min_factor == 0:
break
else:
min_factor = p
cards = []
for i in range(p):
cards.append(set([i * p + j for j in range(p)] + [p * p]))
for i in range(min_factor):
for j in range(p):
cards.append(set([k * p + (j + i * k) % p
for k in range(p)] + [p * p + 1 + i]))
cards.append(set([p * p + i for i in range(min_factor + 1)]))
return cards, p * p + p + 1
def display_using_stars(cards, num_pictures):
for pictures_for_card in cards:
print("".join('*' if picture in pictures_for_card else ' '
for picture in range(num_pictures)))
def check_cards(cards):
for card, other_card in combinations(cards, 2):
if len(card & other_card) != 1:
print("Cards", sorted(card), "and", sorted(other_card),
"have intersection", sorted(card & other_card))
cards, num_pictures = create_cards(7)
display_using_stars(cards, num_pictures)
check_cards(cards)
출력 :
*** *
*** *
****
* * * *
* * * *
* * * *
* * * *
* ** *
** * *
* * * *
* * * *
* * * *
****
나는이 실을 매우 좋아한다. 이 코드의 일부로이 github python 프로젝트를 빌드하여 사용자 정의 카드를 png로 그릴 수 있습니다 (인터넷에서 사용자 정의 카드 게임을 주문할 수 있음).
https://github.com/plagtag/ProjectiveGeometry-Game
z3정리 증명 자 사용하기
P카드 당 기호 수를 보자 . 이 기사 와 ypercubeᵀᴹ답변 에 따르면 N = P**2 - P + 1각각 카드와 기호가 있습니다. 카드 덱은 각 카드에 대한 행과 각 가능한 기호에 대한 열을 갖는 입사 매트릭스로 표현 될 수 있습니다. 그 (i,j)요소는 1카드 i에 기호 j가있는 경우입니다. 이 행렬을 다음과 같은 제약 조건으로 채울 필요가 있습니다.
- 모든 요소는 0 또는 1입니다
- 각 행의 합은 정확히
P - 각 열의 합은 정확히
P - 두 행은 공통으로 정확히 하나의 기호를 가져야합니다.
그것은 N**2변수와 N**2 + 2*N + (N choose 2)제약을 의미 합니다 . z3작은 입력에 대해서는 그리 오래 걸리지 않는 것처럼 보입니다 .
편집 : 불행히도 P = 8 은이 방법에 비해 너무 큰 것 같습니다. 14 시간의 계산 시간 후에 프로세스를 종료했습니다.
from z3 import *
from itertools import combinations
def is_prime_exponent(K):
return K > 1 and K not in 6 # next non-prime exponent is 10,
# but that is too big anyway
def transposed(rows):
return zip(*rows)
def spotit_z3(symbols_per_card):
K = symbols_per_card - 1
N = symbols_per_card ** 2 - symbols_per_card + 1
if not is_prime_exponent(K):
raise TypeError("Symbols per card must be a prime exponent plus one.")
constraints = []
# the rows of the incidence matrix
s = N.bit_length()
rows = [[BitVec("r%dc%d" % (r, c), s) for c in range(N)] for r in range(N)]
# every element must be either 1 or 0
constraints += [Or([elem == 1, elem == 0]) for row in rows for elem in row]
# sum of rows and cols must be exactly symbols_per_card
constraints += [Sum(row) == symbols_per_card for row in rows]
constraints += [Sum(col) == symbols_per_card for col in transposed(rows)]
# Any two rows must have exactly one symbol in common, in other words they
# differ in (symbols_per_card - 1) symbols, so their element-wise XOR will
# have 2 * (symbols_per_card - 1) ones.
D = 2 * (symbols_per_card - 1)
for row_a, row_b in combinations(rows, 2):
constraints += [Sum([a ^ b for a, b in zip(row_a, row_b)]) == D]
solver = Solver()
solver.add(constraints)
if solver.check() == unsat:
raise RuntimeError("Could not solve it :(")
# create the incidence matrix
model = solver.model()
return [[model[elem].as_long() for elem in row] for row in rows]
if __name__ == "__main__":
import sys
symbols_per_card = int(sys.argv[1])
incidence_matrix = spotit_z3(symbols_per_card)
for row in incidence_matrix:
print(row)
결과
$python spotit_z3.py 3
[0, 0, 1, 1, 0, 1, 0]
[0, 0, 0, 0, 1, 1, 1]
[0, 1, 0, 1, 0, 0, 1]
[1, 1, 0, 0, 0, 1, 0]
[0, 1, 1, 0, 1, 0, 0]
[1, 0, 0, 1, 1, 0, 0]
[1, 0, 1, 0, 0, 0, 1]
python spotit_z3.py 3 1.12s user 0.06s system 96% cpu 1.225 total
$ time python3 spotit_z3.py 4
[0, 0, 0, 0, 0, 0, 1, 0, 1, 1, 0, 1, 0]
[0, 0, 0, 0, 0, 1, 0, 1, 1, 0, 1, 0, 0]
[0, 0, 0, 1, 0, 1, 1, 0, 0, 0, 0, 0, 1]
[0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 1, 1, 0]
[0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 1, 1]
[0, 0, 1, 0, 1, 1, 0, 0, 0, 1, 0, 0, 0]
[0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 1]
[0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 0, 0, 0]
[0, 1, 1, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0]
[1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1]
[1, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0]
[1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0]
[1, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0]
python spotit_z3.py 4 664.62s user 0.15s system 99% cpu 11:04.88 total
$ time python3 spotit_z3.py 5
[1, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0]
[0, 0, 0, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0]
[0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 1, 1, 0, 1, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 1, 0]
[0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 1, 0, 1]
[0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0]
[0, 1, 1, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0]
[0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 1]
[1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0]
[0, 1, 0, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0]
[0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 1, 1, 0]
[0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 1]
[1, 1, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1]
[1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0]
[0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 1, 0, 1, 0, 0, 0, 0]
[0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 1]
[1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0]
python spotit_z3.py 5 1162.72s user 20.34s system 99% cpu 19:43.39 total
$ time python3 spotit_z3.py 8
<I killed it after 14 hours of run time.>
Perl의 코드로 이러한 종류의 데크를 생성하는 방법에 대한 기사 를 작성했습니다 . 코드는 최적화되지 않았지만 최소한 "합리적인"주문의 데크를 생성 할 수 있습니다.
8은 소수의 기초 수학을 고려해야하는 예제입니다. 8은 소수의 데크를 생성하기위한 유효한 순서이지만 소수는 아닙니다. 약간 더 어려운 Spot-It을 생성하려면 아래 또는 더 자세한 설명은 기사를 참조하십시오 :-)
$ time pg2 8
elements in field: 8
0. (1, 9, 17, 25, 33, 41, 49, 57, 65)
1. (0, 9, 10, 11, 12, 13, 14, 15, 16)
2. (2, 9, 18, 27, 36, 45, 54, 63, 72)
3. (6, 9, 22, 26, 37, 43, 56, 60, 71)
4. (7, 9, 23, 32, 34, 46, 52, 59, 69)
5. (8, 9, 24, 30, 35, 42, 55, 61, 68)
6. (3, 9, 19, 29, 39, 44, 50, 64, 70)
7. (4, 9, 20, 31, 38, 48, 53, 58, 67)
8. (5, 9, 21, 28, 40, 47, 51, 62, 66)
9. (0, 1, 2, 3, 4, 5, 6, 7, 8)
10. (1, 10, 18, 26, 34, 42, 50, 58, 66)
11. (1, 14, 22, 30, 38, 46, 54, 62, 70)
12. (1, 15, 23, 31, 39, 47, 55, 63, 71)
13. (1, 16, 24, 32, 40, 48, 56, 64, 72)
14. (1, 11, 19, 27, 35, 43, 51, 59, 67)
15. (1, 12, 20, 28, 36, 44, 52, 60, 68)
16. (1, 13, 21, 29, 37, 45, 53, 61, 69)
17. (0, 17, 18, 19, 20, 21, 22, 23, 24)
18. (2, 10, 17, 28, 35, 46, 53, 64, 71)
19. (6, 14, 17, 29, 34, 48, 51, 63, 68)
20. (7, 15, 17, 26, 40, 44, 54, 61, 67)
21. (8, 16, 17, 27, 38, 47, 50, 60, 69)
22. (3, 11, 17, 31, 37, 42, 52, 62, 72)
23. (4, 12, 17, 30, 39, 45, 56, 59, 66)
24. (5, 13, 17, 32, 36, 43, 55, 58, 70)
25. (0, 49, 50, 51, 52, 53, 54, 55, 56)
26. (3, 10, 20, 30, 40, 43, 49, 63, 69)
27. (2, 14, 21, 32, 39, 42, 49, 60, 67)
28. (8, 15, 18, 28, 37, 48, 49, 59, 70)
29. (6, 16, 19, 31, 36, 46, 49, 61, 66)
30. (5, 11, 23, 26, 38, 45, 49, 64, 68)
31. (7, 12, 22, 29, 35, 47, 49, 58, 72)
32. (4, 13, 24, 27, 34, 44, 49, 62, 71)
33. (0, 57, 58, 59, 60, 61, 62, 63, 64)
34. (4, 10, 19, 32, 37, 47, 54, 57, 68)
35. (5, 14, 18, 31, 35, 44, 56, 57, 69)
36. (2, 15, 24, 29, 38, 43, 52, 57, 66)
37. (3, 16, 22, 28, 34, 45, 55, 57, 67)
38. (7, 11, 21, 30, 36, 48, 50, 57, 71)
39. (6, 12, 23, 27, 40, 42, 53, 57, 70)
40. (8, 13, 20, 26, 39, 46, 51, 57, 72)
41. (0, 65, 66, 67, 68, 69, 70, 71, 72)
42. (5, 10, 22, 27, 39, 48, 52, 61, 65)
43. (3, 14, 24, 26, 36, 47, 53, 59, 65)
44. (6, 15, 20, 32, 35, 45, 50, 62, 65)
45. (2, 16, 23, 30, 37, 44, 51, 58, 65)
46. (4, 11, 18, 29, 40, 46, 55, 60, 65)
47. (8, 12, 21, 31, 34, 43, 54, 64, 65)
48. (7, 13, 19, 28, 38, 42, 56, 63, 65)
49. (0, 25, 26, 27, 28, 29, 30, 31, 32)
50. (6, 10, 21, 25, 38, 44, 55, 59, 72)
51. (8, 14, 19, 25, 40, 45, 52, 58, 71)
52. (4, 15, 22, 25, 36, 42, 51, 64, 69)
53. (7, 16, 18, 25, 39, 43, 53, 62, 68)
54. (2, 11, 20, 25, 34, 47, 56, 61, 70)
55. (5, 12, 24, 25, 37, 46, 50, 63, 67)
56. (3, 13, 23, 25, 35, 48, 54, 60, 66)
57. (0, 33, 34, 35, 36, 37, 38, 39, 40)
58. (7, 10, 24, 31, 33, 45, 51, 60, 70)
59. (4, 14, 23, 28, 33, 43, 50, 61, 72)
60. (3, 15, 21, 27, 33, 46, 56, 58, 68)
61. (5, 16, 20, 29, 33, 42, 54, 59, 71)
62. (8, 11, 22, 32, 33, 44, 53, 63, 66)
63. (2, 12, 19, 26, 33, 48, 55, 62, 69)
64. (6, 13, 18, 30, 33, 47, 52, 64, 67)
65. (0, 41, 42, 43, 44, 45, 46, 47, 48)
66. (8, 10, 23, 29, 36, 41, 56, 62, 67)
67. (7, 14, 20, 27, 37, 41, 55, 64, 66)
68. (5, 15, 19, 30, 34, 41, 53, 60, 72)
69. (4, 16, 21, 26, 35, 41, 52, 63, 70)
70. (6, 11, 24, 28, 39, 41, 54, 58, 69)
71. (3, 12, 18, 32, 38, 41, 51, 61, 71)
72. (2, 13, 22, 31, 40, 41, 50, 59, 68)
errors in check: 0
real 0m0.303s
user 0m0.200s
sys 0m0.016s
에서 0까지의 각각의 식별자 72는 카드 식별자 및 화상 식별자로서 판독 될 수있다. 예를 들어 마지막 행은 다음을 의미합니다.
- 카드가
72포함 사진2,13,22, ...,59,68, 및 - 사진을
72카드에 나타납니다2,13,22, ...,59하고68.
'IT story' 카테고리의 다른 글
| package-lock.json의 역할은 무엇입니까? (0) | 2020.05.12 |
|---|---|
| osx에서 .so와 .dylib의 차이점은 무엇입니까? (0) | 2020.05.12 |
| instanceof와 동등한 C ++ (0) | 2020.05.12 |
| 문자열에“”를 추가하면 왜 메모리가 절약됩니까? (0) | 2020.05.12 |
| 언제 Task.Yield ()를 사용합니까? (0) | 2020.05.12 |