오셀로 비슷한데 어려운 게임 -.-

우후후...
8x8 성공입니다. 6x6 과 동일한 원리군요.
7x7 남았습니다.!

몇 시간 동안 헤맨 끝에, 답 찾는 프로그램을 만들었습니다. 8)

소스코드의 MATRIX_SIZE를 원하는 크기로 하여, 컴파일 실행하면, 3x3의 경우, X . X 라고 출력됩니다. 첫줄에서 1,3번 셀을 클릭하라는 뜻입니다. 두번째 줄부터 계속해서, 바로 윗 셀이 흰색인 아랫 셀을 클릭하여 마지막 줄까지 계속합니다. 그러면 그게 답입니다. :wink:

#include <stdio.h>
#include <string.h>

#define MATRIX_SIZE 5 // 원하는 크기로 변경하세요!
#define WHITE 1

char c[MATRIX_SIZE][MATRIX_SIZE]; // THE BOARD; white = 1, black = 0

void click(int row, int col) // 상하좌우 및 자신을 색깔 전환
{
        c[row][col] = !c[row][col];
        if(row>0) c[row-1][col] = !c[row-1][col];
        if(row<MATRIX_SIZE-1) c[row+1][col] = !c[row+1][col];
        if(col>0) c[row][col-1] = !c[row][col-1];
        if(col<MATRIX_SIZE-1) c[row][col+1] = !c[row][col+1];
}

void expand_matrix() // 한 줄씩 아래로, 바로 윗칸이 흰색이면 클릭한다.
{
        int row, col;
        for(row=1; row<MATRIX_SIZE; row++)
        {
                for(col=0; col<MATRIX_SIZE; col++)
                {
                        if(c[row-1][col]==WHITE) click(row,col);
                }
        }
}

int is_solution() // 맨 마지막줄이 모두 검정이면 성공
{
        int col;

        for(col=0; col<MATRIX_SIZE; col++)
        {
                if(c[MATRIX_SIZE-1][col] == WHITE) return 0;
        }

        return 1; // 해답
}

void make_first_row(unsigned bits) // 첫줄을 배열한다.
{
        int col;
        unsigned b;

        for(col=0; col<MATRIX_SIZE; col++)
        {
                if( ( 1 << col ) & bits )
                {
                        click(0,col);
                }
        }
}

void print_bits(unsigned long long bits) // 첫줄에서 클릭한 위치 표시
{
        int col;

        for(col=0; col<MATRIX_SIZE; col++)
        {
                if( ( 1 << col ) & bits ) printf("X ");
                else printf(". ");
        }
        printf("\n");
}

void reset() // 모두 흰색으로 리셋
{
        int row, col;
        for(row=0; row<MATRIX_SIZE; row++)
        for(col=0; col<MATRIX_SIZE; col++)
                c[row][col] = WHITE;
}

int main()
{
        unsigned bits;
        unsigned num;

        num = 1 << MATRIX_SIZE;

        for(bits=0; bits<num; bits++) // 첫 줄에서 가능한 모든 경우의 수
        {
                reset();
                make_first_row(bits);
                expand_matrix();
                if(is_solution())
                {
                        printf("Clicks of the first row of a solution: ");
                        print_bits(bits);
                }
        }

        return 0;
}

int clicked; //전역 변수로 하나 두고,

void click(int row, int col) // 상하좌우 및 자신을 색깔 전환 
{ 
        clicked++; // 클릭 될 때마다 증가시키고,

...

void reset() // 모두 흰색으로 리셋 
{ 
        int row, col; 
        clicked = 0; // reset 에서 0으로 만들고

...

//main 에서 클릭회수를 표시하면...
          printf("Clicks of the first row of a solution (%d clicks): ", clicked); 

최적 솔루션을 볼 수 있겠네요.

컴으로 구현하기 위한 가장 쉬운 알고리즘으로는 gang 님께서 찾으신게 정답이 아닌가 합니다.

재밌는 건 이 문제는 순서에 무관하다는 것입니다. 즉 click 해야할 위치가 중요하지, 그것을 어떠한 순서로 클릭했는가는 전혀 무관하기 때문에, 제가 한 것처럼 다른 솔루션이 나올 수 있었던 거죠. 결과적으로 누른 위치들은 같을 겁니다.