네모네모 로직(nonogram) 풀기 - 3

네모네모로직을 사람이 하는 방법을 채택해서 풀어보면 어떨까요?

 

이미 무식한 방법(Brute force)으로 네모네모 로직을 풀어보았습니다.  이 방법을 이용하면, 모든 경우를 다 탐색하기 때문에 풀지 못 하는 로직은 없습니다.  시간은 많이 걸릴 수가 있습니다.

 

사람이 푸는 방식을 채택해서 풀어보면, 보다 합리적인 시간안에 문제를 풀 수 있고, 이것을 이용하면, 합리적인 네모네모로직 문제를 만들 수도 있습니다.  (네모네모 로직 중 답이 여러개인 경우도 꽤 있고 여러 경우의 수를 생각해서 풀어야 하는 것들도 있습니다.)

 

새로운 방법을 기존의 NemoLogic 클래스에 적용해서 클래스 설계를 해보았습니다.

 

[NemoLogic class]

class NemoLogic
{
public:
	NemoLogic();
	~NemoLogic();

	bool Load(const char *filename);
	void InitSolve();
	bool Solve();
	bool SolveN();
	void PrintResult();
	void Print(int row);
	void PrintRow(int row);
	void PrintCol(int col);

	int GetColNum() const { return colnum; }
	int GetRowNum() const { return rownum; }
	char *GetResult() const { return board; }

protected:
	int GetNumbers(FILE *fi, char numbers[]);
	void SetFirstPattern(char *s, const char *p);
	bool SetNextPattern(char *s, const char *p);
	bool CheckPattern(int row);
	int CheckCol(int col);
	int CheckRow(int row);

private:
	int colnum, rownum;
	char **cols, **rows;
	int phase;
	char *board;
	int totalCheck;
};

 

 

이 중에 SolveN() 멤버 함수가 새로 작성한 풀이방법입니다.

 

[SolveN()]

bool NemoLogic::SolveN()
{
	int lastcheck = 0;
	int rowcheck[100];
	int colcheck[100];
	memset(rowcheck, 0, sizeof(rowcheck));
	memset(colcheck, 0, sizeof(colcheck));
	while( lastcheck < totalCheck )
	{
		int checked = 0;
		for( int i = 0 ; i < rownum ; i++ )
		{
			int c = CheckRow(i);
			if( c != rowcheck[i] ) { PrintRow(i); rowcheck[i] = c; }
		}
		for( int i = 0 ; i < colnum ; i++ )
		{
			int c = CheckCol(i);
			if( c != colcheck[i] ) { PrintCol(i); colcheck[i] = c; }
			checked += c;
		}
		if( lastcheck == checked ) return false;
//		PrintResult();
//		Sleep(500);
		lastcheck = checked;
	}

	return true;
}

 

여기서 중요한 함수는 바로 CheckRow() 함수와 CheckCol() 함수입니다.  여기서 좀 더 논리적으로 프로그램을 할 수 있겠지만, 일단은 가능한 모든 패턴 중, 기존의 데이터를 검사해서 맞는 패턴인 경우, 반드시 칠해지는 곳, 반드시 칠해지지 않는 곳, 그리고 아직 정해지지 않은 곳 세가지 경우를 생각했습니다.  비트 연산자를 이용해서 보다 빨리 연산하기 위해서 각각의 값을 1, 2, 3 으로 설정했습니다.

 

 

[CheckRow(), CheckCol()]

int NemoLogic::CheckRow(int row)
{
	char t[128], r[128], u[64];
	memset(r, 0, sizeof(r));
	memset(u, 0, sizeof(u));
	int c = 0, i;
	for( i = 0 ; rows[row][i] ; i++ )
	{
		c += rows[row][i];
	}
	int s = colnum - c - i + 1;
	int p = 0;
	c = 0;
	while( true )
	{
		if( rows[row][c] == 0 )
		{
			while( p < colnum ) t[p++] = 2;
			u[c] = s;
			s = 0;
			for( i = 0 ; i < colnum ; i++ )
			{
				if( !(t[i] & board[row*colnum+i]) ) break;
			}
			if( i == colnum )
			{
				for( i = 0 ; i < colnum ; i++ )
				{
					r[i] |= t[i];
				}
			}
			do
			{
				s += u[c];
				p -= u[c];
				u[c] = 0;
				c--;
				if( c < 0 ) break;
				p -= rows[row][c]+(c!=0);
			}
			while( s == 0 );
			if( c < 0 )
			{
				c = 0;
				for( i = 0 ; i < colnum ; i++ )
				{
					board[row*colnum+i] = r[i];
					if( r[i] == 1 ) c++;
				}
				return c;
			}
			p -= u[c];
			u[c]++;
			s--;
		}
		for( i = 0 ; i < u[c]+(c != 0) ; i++ ) t[p++] = 2;
		for( i = 0 ; i < rows[row][c] ; i++ ) t[p++] = 1;
		c++;
	}
	return 0;
}

int NemoLogic::CheckCol(int col)
{
	char t[128], r[128], u[64];
	memset(r, 0, sizeof(r));
	memset(u, 0, sizeof(u));
	int c = 0, i;
	for( i = 0 ; cols[col][i] ; i++ )
	{
		c += cols[col][i];
	}
	int s = rownum - c - i + 1;
	int p = 0;
	c = 0;
	while( true )
	{
		if( cols[col][c] == 0 )
		{
			while( p < rownum ) t[p++] = 2;
			u[c] = s;
			s = 0;
			for( i = 0 ; i < rownum ; i++ )
			{
				if( !(t[i] & board[i*colnum+col]) ) break;
			}
			if( i == rownum )
			{
				for( i = 0 ; i < rownum ; i++ )
				{
					r[i] |= t[i];
				}
			}
			do
			{
				s += u[c];
				p -= u[c];
				u[c] = 0;
				c--;
				if( c < 0 ) break;
				p -= cols[col][c]+(c!=0);
			}
			while( s == 0 );
			if( c < 0 )
			{
				c = 0;
				for( i = 0 ; i < rownum ; i++ )
				{
					board[i*colnum+col] = r[i];
					if( r[i] == 1 ) c++;
				}
				return c;
			}
			p -= u[c];
			u[c]++;
			s--;
		}
		for( i = 0 ; i < u[c]+(c != 0) ; i++ ) t[p++] = 2;
		for( i = 0 ; i < cols[col][c] ; i++ ) t[p++] = 1;
		c++;
	}
	return 0;
}

 

 

인터넷에서 어렵다고 하는 네모네모 로직 문제를 가져와서 대입을 해보았습니다.

일단 문제는 다음과 같습니다.

 

출처 : Nonograms online page (http://en.japonskie.ru/)

 

평균 풀이 시간이 사람이 푼 기준으로 1시간 30분정도 되는 복잡한 문제입니다.

해당 출처 사이트에 가면, 풀어진 결과도 나옵니다만, 한번 도전의식을 가지고 도전해보시는 것도 나쁘지 않겠네요.  (사실 이것 풀면 뿌듯할 듯)

 

소스 요청하시는 분들이 많으셔서, github에 소스를 올려놓았습니다.

https://github.com/lakshimi/nonograms.git

 

위 링크를 접속하시면 github에서 다운로드 받으실 수 있습니다.

 

제가 작성한 프로그램이 푸는 모습을 동영상으로 올려봅니다.