간단한 방법

Question

체스 한 플레이어는, 예를 들어 상이한 재료의 조합을 가질 수

가

"퀸 2 루크, 2- 나이트 2 개 감독 8 졸이 + 왕이" 하나 개의 조합

플레이어가 한 감독 잃으면

:

"퀸 2 루크, 2- 나이트 1 개 감독 8 졸 + 왕"폰이 경우 다른 조합을

..afterwards 인 다음 기사로 승격됩니다.

"퀸 2 루크 3 나이트 1 개 감독 7 졸 + 왕"다른 조합

OK이고, 다음의 조합은 유효하지 :

"5 개 즈 5 루크 5 기사, 주교 5 명, 심복 2 명 + 왕 "

홍보 할 폰이 부족하기 때문에. (5 퀸 = 4 개 폰 필요) (5 룩 = 3 개 폰 필요) 등 4 + 3 + 3 + 3 = 13 마리의 폰이 필요합니다. 보드에 2 개의 폰이 있기 때문에 최대 6 개의 폰이 승격 될 수 있습니다. 유효하지.

몇 가지 유효한 재료 조합이 있습니까? 다음 C 코드를 사용하여 8694 개의 조합을 계산했습니다. 질문은 :

계산하기에 더 간단하고 효율적인 알고리즘을 찾으십니까? (적은 사이클, 적은 계산, 더 명확한 코드 등) ... 또는 심지어 수학 공식?

total = 0; 
for (queens=0;queens<=9;queens++) 
for (rooks=0;rooks<=10;rooks++) 
for (bishops=0;bishops<=10;bishops++) 
for (knights=0;knights<=10;knights++) 
for (pawns=0;pawns<=8;pawns++) 
{ 
    pawnsRequested = 0; 
    if (queens>1) pawnsRequested += queens - 1; 
    if (rooks>2) pawnsRequested += rooks - 2; 
    if (bishops>2) pawnsRequested += bishops - 2; 
    if (knights>2) pawnsRequested += knights - 2; 
    if (8-pawns < pawnsRequested) continue; 
    total++; 
} 
printf("%i\n",total); 

Answer 1

조각 유형은 독립적 인 경우에, 우리 수 단지 곱셈 : 여왕 시간 10 가능성 우리는하지만, 폰 사용을 추적하는 데 필요한 루크 시간 등 11 가능성. 이

x의 힘을 사용 졸의 수이다

3 + x + x^2 + x^3 + x^4 + x^5 + x^6 + x^7 + x^8, 

같은 수학적 우리가 예를 들어,에 대한 가능성을 인코딩 할 수 generating functions라는 트릭, 루크는, 그리고 계수는 가능성의 수를 나타낸다. 여기서는 프로모션 폰 (0, 1, 2)을 필요로하지 않는 3 가지 가능성, 1 개의 프로모션 폰 (3)을 필요로하는 3 가지 가능성, 2 개의 프로모션 폰 (4)을 필요로하는 가능성 등이 있습니다. 이제는 각 요소를 함께 곱할 수 있습니다 (각각, 여왕, 루크, 주교, 기사, 졸).

(2 + x + x^2 + x^3 + x^4 + x^5 + x^6 + x^7 + x^8) 
* (3 + x + x^2 + x^3 + x^4 + x^5 + x^6 + x^7 + x^8) 
* (3 + x + x^2 + x^3 + x^4 + x^5 + x^6 + x^7 + x^8) 
* (3 + x + x^2 + x^3 + x^4 + x^5 + x^6 + x^7 + x^8) 
* (1 + x + x^2 + x^3 + x^4 + x^5 + x^6 + x^7 + x^8) 

여기는 Wolfram Alpha입니다. 필요한 08에 졸 가능성 수있다 x^8 통해 1의

계수는, 54, 135, 261, 443, 693, 1,024, 1,450, 1,986, 2,648, 아르에 합산 8694.