동전 이동 게임 의 풀이 알고리즘

이 게임 은 영 광 스 러 운 대항 해 시대 4 위력 강화 판 (오래된 단기 판 PC 게임) 에서 처음 봤 습 니 다. 게임 이 라 기보 다 는 지적 인 문제 입 니 다. 이 문 제 는 이 렇 습 니 다.
동전 5 개, 정면 3 개, 뒷면 2 개가 있 는데 처음에는 간격 으로 배열 되 어 있 었 다. 그림 1 참조.
그림. 1 다섯 개의 동전 의 원시 배열
이동 할 때마다 서로 다른 동전 2 개 만 이동 할 수 있 습 니 다. 즉, 이동 하 는 동전 두 개 는 반드시 하 나 는 정면 이 고 하 나 는 뒷면 이 며 두 개의 동전 은 서로 인접 해 있 습 니 다. 왼쪽 이나 오른쪽으로 이동 할 수 있 지만 이동 하 는 방향 에는 반드시 인접 한 동전 이 있어 야 합 니 다. 이동 할 때 는 인접 한 동전 을 건 너 야 합 니 다. 예 를 들 어 1, 2 개의 동전 은 오른쪽으로 이동 할 수 있 습 니 다.그러나 왼쪽으로 이동 하면 안 됩 니 다. 왼쪽 에 인접 한 동전 이 없 기 때 문 입 니 다. 오른쪽으로 이동 할 때 오른쪽 에 서로 붙 어 있 는 모든 동전 을 건 너 야 합 니 다. 그림 2 참조.
그림. 2 앞의 두 동전 을 이동 합 니 다.
이동 방향 에서 동전 이 연속 되 지 않 으 면 동전 을 넣 을 수 있 는 첫 번 째 곳 으로 만 이동 할 수 있다. 예 를 들 어 아래 의 예 를 들 어 왼쪽 에서 세 번 째, 네 번 째 동전 을 왼쪽으로 이동 하려 면 중간 빈자리 로 만 이동 할 수 있 고 빈 자 리 를 건 너 뛰 어 맨 왼쪽으로 이동 할 수 없다. 그림 3 참조.
그림. 3 또 다른 이동 예
최종 목 표 는 바로 한쪽 으로 이동 하고 반대 쪽 으로 이동 하 는 것 이다.
그림. 4 최종 목표
이 문 제 는 보기 에는 매우 간단 한 것 같 지만, 실제로 해 보 니 여전히 매우 어렵 다 는 것 을 알 게 되 었 다. 나 는 오랫동안 시험 해 보고 나 서 야 답 을 찾 았 다.
그러나 이 문 제 는 컴퓨터 로 계산 하 는 것 이 어렵 지 않 고 재 귀 알고리즘 으로 계산 하기에 매우 적합 합 니 다. 다음은 제 가 작성 한 프로그램 입 니 다. 이 프로그램의 계 산 량 이 많 지 않 기 때문에 계산 효율 문 제 를 고려 하지 않 고 프로그램 을 가능 한 한 간단 하고 직 설 적 으로 만 듭 니 다.
프로그램 에서 이 동전 들 의 정 보 를 문자열 로 저장 합 니 다. "A" 긍정 적 반면, 빈 칸 은 빈 자 리 를 표시 합 니 다. 따라서 문자열 은 다음 과 같이 초기 화 됩 니 다.        ABABA          "。동전 을 옮 기 는 데 대응 하 는 것 은 문자열 의 AB 위 치 를 바 꾸 는 것 입 니 다. 동전 을 옮 기 는 동작 은 move 에 있 습 니 다. 함수 함수 에 정형 매개 변수 가 들 어 옵 니 다. i. 현재 움 직 이 는 동전 이 어느 두 개 인지, 왼쪽으로 움 직 이 는 지, 오른쪽으로 움 직 이 는 지 표시 합 니 다. 구체 적 인 방법 은 i 의 가장 낮은 bit 입 니 다. 옮기다 짝수 일 때 는 왼쪽으로 움 직 이 는 것 을 나타 내 고, i 는 홀수 일 때 는 오른쪽으로 동전 을 움 직 이 는 것 을 나타 낸다. 나머지 비트 현재 이동 하고 있 는 동전 이 두 개 인지 표시 합 니 다. Move 함수 의 반환 값 은 이번 이동 이 성 공 했 는 지 여 부 를 표시 합 니 다.
구체 적 인 코드 는 다음 과 같다.

static bool move(string &coins, int i)
{
    int dir = i % 2; // 0     ，1     
    i = i / 2;
    if(coins[i] == ' ' || coins[i + 1] == ' ' || coins[i] == coins[i + 1])
    {
        return false; //        
    }
    if( dir == 0 ) //   
    {
        if( coins[ i - 1] == ' ') //     ，    
        {
            return false;
        }
        else
        {
            string::size_type j = i - 2;
            while( coins[j] != ' ' && j > 1) {j --;}
            coins[j - 1] = coins[i];
            coins[j] = coins[i + 1];
            coins[i] = ' ';
            coins[i + 1] = ' ';
        }
    }
    else
    {
        if( coins[i + 2] == ' ') //     ，    
        {
            return false;
        }
        else
        {
            string::size_type j = i + 3;
            while(coins[j] != ' ' && j < coins.size() - 1) {j ++;}
            coins[j] = coins[i];
            coins[j + 1] = coins[i + 1];
            coins[i] = ' ';
            coins[i + 1] = ' ';
        }
    }
    return true;
}

isSeperated 함수 가 동전 을 분리 하 는 지 여 부 를 판단 합 니 다. 알고리즘 은 간단 합 니 다. 분명 더 효율 적 인 알고리즘 이 있 을 것 입 니 다. 저 는 이 위 에 신경 을 많이 쓰 지 않 았 습 니 다. 이 작은 프로그램 에 있어 서 프로그램 을 쓰 는 데 걸 리 는 시간 이 프로그램 이 실행 하 는 시간 보다 훨씬 많 을 것 입 니 다. 그래서 제 가 추구 하 는 것 은 이 프로그램 을 어떻게 빨리 쓰 느 냐 가 아니 라 어떻게 빨리 달 릴 수 있 느 냐 입 니 다. 다음은 세대 입 니 다.코드:

static bool isSeperated(string coins)
{
    int first = 0, last = coins.size() - 1;
    while(coins[first] == ' ') {first ++;} //           
    while(coins[last] == ' ') {last --;} //           
    if(coins[first] == coins[last] ) return false;//          ，       
    int i = first + 1, j = last - 1;
    while(coins[i] == coins[first] || coins[i] == ' '){i ++;} //              
    while(coins[j] == coins[last] || coins[j] == ' '){j --;}  //               
    if( i != j + 1) return false;
    return true; //            
}

Solve 함수 가 계산 을 책임 지고 알고리즘 은 간단 합 니 다. 쉽게 말 하면 궁 거 법 입 니 다. 가능 한 이동 방법 을 모두 시험 해 보면 반드시 정확 한 절 차 를 얻 을 수 있 습 니 다. 유일 하 게 설명 해 야 할 것 은 이 문제 에 대해 이동 할 수 있 는 걸음 수 는 무한 합 니 다. 따라서 검색 깊이 를 제한 하 는 것 입 니 다. 즉, 최대 몇 걸음 을 이동 해 야 궁 거 가 끝 날 수 있 습 니 다. 층수 에 따라(걸음 수) 검색 은 당연히 재 귀 알고리즘 으로 쓰 는 것 이 가장 편리 합 니 다. 다음은 코드 입 니 다.

bool solve(string coins, int depth)
{
    string coins2 = coins;
    int first = 0;
    int last = coins.size() - 1;
    while(coins[first] == ' ') {first ++;}
    while(coins[last] == ' ') {last --;}

    for( int i = 2 * first; i < 2 * (last - 1); i++ )
    {
        if( move(coins, i) )
        {//         
            depth --; //        
            if( isSeperated(coins) )
            {
                //    ，    
                cout << coins << endl;
                return true;
            }
            else if( depth != 0 && solve(coins, depth) )//              
            {
                cout << coins << endl;
                return true;
            }
            else
            {
                //               
                coins = coins2;
                depth ++;
                continue; //        
            }
        }
    }
    //                 ，    
    return false;
}

마지막 으로 메 인 프로그램 입 니 다. 몇 줄 입 니 다. 더 이상 설명 할 필요 가 없습니다.

int main()
{
    string coins("        ABABA          ");
    if(solve(coins, 5))
    {
        cout << coins << endl;
    }
    return 0;
}

프로그램 출력 결 과 는 다음 과 같 습 니 다.
              AAABB             ABAA  B             A  ABAB             AABAB           ABAAB         ABABA
설명 이 필요 한 것 은 재 귀 이기 때문에 수출 결 과 는 아래 에서 위로 봐 야 한 다 는 것 이다.