Klondike-Solitaire의 모든 게임을 해결할 수 있습니까?

아니요. 예 : 보드에 앞면이 표시된 카드가 모두 빨간색이고 세 번째 카드마다 나오는 카드도 빨간색이고 그중 어느 것도 에이스가 아닌 경우. 당신은집니다. 추월하지 말고 $ 200을 모으지 마십시오.

댓글

• 사실 컴퓨터 버전에서 거의 이와 같은 설정을 생각해 냈습니다. 카드 한 장은 검은 색이어서 어디에도 놓을 수 없습니다.
• 나에게 일어난 또 다른 예 : 표시된 모든 카드가 균등합니다.
• en.wikipedia.org/wiki/Klondike_%28solitaire%29#Odds_of_winning
• 더 간단하게 : 모든 에이스는 같은 열에 있고 2는 그 위에 있습니다.
• @Oltarus Aces가 같은 열에 있고 그 위에 2 개는 여전히 우승 할 수 있습니다. 성 가시고 아마도 손실이지만 가능합니다.

위키 백과에서 매우 흥미로운 읽기 .

Klondike의 “표준”게임 (형식 : Draw 3, Re-Deal Infinite, Win 52)의 경우 해결 가능한 게임 수 (가정 모든 카드가 알려져 있음) 82-91.5 % 사이입니다.

댓글

• 실제로 80 %에 가까운 훌륭한 작업을 수행하고 있습니다.

말 그대로 스택 (4 장의 카드를 포함하는 것)은 다이아몬드 9 개로 이어졌고, 그 안에있는 카드는 스페이드 킹, 다이아몬드 5 개, 스페이드 10 개, 클럽 10 개였습니다. 이 스택을 제외하고 전체 필드를 해결하고 제거 프로세스를 사용했습니다.) 내가 볼 수있는 한 이것은 게임을 불가능하게 만든다. 나는 절대 움직일 수없는 9 개의 다이아몬드를 가지고 있는데, 그 안에 놓을 수있는 두 개의 10이 아래를 향한 스택의 밑에 갇혀 있기 때문입니다. 다이아몬드 스택으로 9 개를 이동하여 제거하려고하면 또한 5 개의 다이아몬드가 그 아래에 붙어 있기 때문에 결실이 없습니다. 누군가이 문제를 해결할 수있는 방법을 알려주지 않는 한 스택을 이끄는 카드가 스택을 포함하는 스택을 덮고 있다면 두 장의 카드를 얹고 자신의 수트 수가 적 으면 처음부터 게임이 불가능 해집니다.

솔리테어는 컴퓨터 버전 이전의 게임입니다. 즉, 컴퓨터가 게임을 풀 수 있는지 확인하기 위해 들여다 보지 않고도 모든 카드가 실제로 섞여 있음을 의미합니다.

그리고 McKay가 언급했듯이 무작위 셔플을 사용하면 확실히 해결할 수없는 게임으로 끝날 수 있습니다.

각 게임이 포함 된 Solitaire 변형을 디자인하는 것이 가능하다고 확신합니다. 그래도 해결 가능합니다.

댓글

• 많은 계산이 필요합니다. 기본적으로 컴퓨터가 전체 게임을 플레이해야합니다. ' 해결책입니다. ' 어떤 종류의 알고리즘 I '가 누락되지 않는 한.
• @Arda, 쉽게 테스트 할 수있는 몇 가지 조건이 있습니다. 예를 들어, 킹이 아닌 카드는 덱에있는 다른 3 장의 카드에서만 플레이 할 수 있습니다 (수트에서 다음으로 낮은 카드 또는 에이스의 기초 및 반대 색상의 다음 상위 카드). 이 세 카드가 모두 더미에있는 해당 카드 아래에 뒤집혀 있으면 게임에서 승리 할 수 없습니다. ' 안타깝게도 ' 적은 비율이며 다른 조건을 테스트하려면 많은 재귀가 필요할 수 있습니다.
• @DaveDuPlantis True,하지만 테스트를해야합니다. 존재하는 모든 조건. ' 우리가 모두 알고 있는지도 잘 모르겠습니다.
• @Arda-' 사실입니다. ' 재귀와 관련하여 제가 생각했던 것입니다. 주어진 위치가 이길 수 없음을 입증 할 방법이 없다면, ' 기본적으로 차단 될 때까지 특정 일련의 카드를 플레이하고 마지막 결정 지점으로 백업 한 다음 반복해야합니다. …이것은 ' 흥미로운 개념이지만 ' 솔리테어 프로그램이 그렇게하는 것을 본 적이 없습니다.
• @Arda 단순히 솔루션에서 거꾸로 작업 할 수 있으며, 항상 합법적 인 플레이의 반대를 사용하여 카드를 덱과 4 개의 슈트 더미에서 보드로 무작위로 이동할 수 있습니다. 아마도 이겼을 것입니다 ' 셔플 링 및 승리 가능성을 확인하는 것과 동일한 확률 분포를 갖지는 않지만 대부분의 플레이어에게 중요하지 않습니다.

하지만 목록을 시작하고 초기 조건을 열거 한 경우-Linux 버전의 Solitare에서 본 것 같습니다. 덱 번호 매기기 즉, 특정 항목이 이길 수 없다고 결정하면 노드 (친구와 공유)와 VOILA (승리 불가능한 시작 덱 스택 목록)간에 메모를 비교할 수 있습니다.

저는 Windows 7 버전에서 우승 할 수없는 데크가 제거되었다고 생각하기 시작했습니다. … 모르겠습니다. 통계에 대해 조금 무겁고 잘난 체합니다.

댓글

• 52 명! 셔플을 시작하려면 ' 좋은 목록을 만들려면 불편하게 긴 … 시간이 필요합니다. 무승부를 결정하는 문제를 확실하게 해결 한 후에도.
• 52 factorial = 대략 8 다음에 67 개의 0. '는 많은 조합입니다. 1TB 하드 드라이브에는 약 1 조 개의 저장 용량이 있으며, ' 상당한 부분도 저장하려면 수조 테라 바이트가 필요합니다. 불행히도 천문학적으로 많은 확률 때문에 실용적이지 않습니다. 분명히 승리 할 수있는 특정 게임 수를 저장하는 것이 더 쉬울 것입니다.
• @JonathanHobbs 계산을 위해 모든 게임을 저장해야하는 것은 아닙니다. for 1 to 52! getdeck, try solving game, add to statistics 각 지점에서 하나의 덱만 저장하면되며 통계는 매우 작을 수 있습니다.
• @McKay 괜찮은 제품을 개발하려면 꽤 많이 저장해야합니다. 그래도 목록. (나는 ' 당신이 어떤 계산에 대해 말하고 있는지 잘 모르겠습니다.) 대답과 관련하여 제쳐두고, Windows 7 버전은 실제로 수십만 개의 데크를 저장하고 있습니다. ' 게임마다 무작위로 하나씩 지급됩니다. 우승 할 수있는 것으로 알려진 수십만 개의 덱을 방금 골 랐을 수도 있습니다.
• @JonathanHobbs 아니요, 저장해야하는 덱은 '입니다. (52까지 올라 가야합니다. 즉, ' 약 226 비트가 필요함을 의미합니다.) ' 그 중 얼마나 많은 것을 해결할 수 있었는지 (다른 226 비트 이하), 솔리테어 게임 (윈도우 3.1이 잘 저장할 수 있었던 것임)과 실제로 게임을 해결하는 알고리즘을 저장합니다. 해결 가능성에 대한 전체 통계 세트를 수행하기 위해 데이터 저장 메커니즘이 그다지 많을 필요는 없습니다. ' 저장 용량이 1K 미만입니다. 물론 이러한 모든 계산을 수행하는 데 오랜 시간이 걸립니다. 하지만 저장 용량은 아닙니다.

아니요. Eric Sink 는 항상 우승 할 수있는 솔리테어 버전을 만들기 위해 마이크로 ISV를 시작하기로 결정했습니다. 이것은 대부분 한 사람과 함께 소프트웨어 회사를 운영하는 것이 어떤 것인지 확인하기위한 실험에 불과했지만 결국 그는 여전히 구매 가능한 제품을 판매 했습니다.

플레이 불가능 인 클론 다이크 솔리테어 게임의 수에 대한 몇 가지 추정치가 있습니다 (동작 없음, 400 분의 1 정도). 이 비율은 30 % ~ 10 %에서 크게 다르지만 승패 불가 게임 수에 대한 몇 가지 추측입니다.

이 문제의 난이도는 초기 거래의 순전히 54에서! 어느 것이 승패인지 결정하기 위해 평가해야합니다.

댓글

• 초기 거래 수는 52!? (조커도 처리되기를 기대하지 않는 한)
• 다행히도 승리 확률을 계산하기 위해 무차별 대입 방법 (가능한 모든 거래 확인)을 사용할 필요가 없습니다. 우주의 나이보다 길다-68 번째 파워 덱에 8×10). 실패 방법에 대한 분석은 분석적인 공격 라인을 제공합니다. 이미 언급했듯이 단일 스택이 실패 할 수있는 명확한 방법이 있습니다. 필요한 카드는 2 개 스택, 3 개 스택 또는 4 개 스택 내에서 도달하지 못할 수도 있습니다. 필요한 카드를 잠그기위한 카드의 형태가 알려지면 개별 확률을 계산하고 결합하여 답을 얻을 수 있습니다.

다른 훌륭한 답변에 추가하기 위해이 링크에는 거래가 어떻게 성사되지 않는지에 대한 멋진 설명이 있습니다.

Klondike Solitaire에 갇힌 이유