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

네모네모로직을 풀기 위한 프로그램입니다.

 

기초적인 것은 앞의 글을 참고하세요.

 

첫번째, 로직프로그램을 담기 위한 클래스를 설계해봐야겠죠.

 

[NemoLogic 클래스 뼈대]

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

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

	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);

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

 

 

Load() 멤버 함수는 로직 프로그램 파일을 읽기 위한 함수입니다.

파일 내용에는,

첫번째 줄에 가로 세로의 크기를 적습니다.

<가로 크기> <세로 크기>

두번째 줄부터는 행에 있는 숫자들을 차례대로 적습니다.  한 줄에 하나의 행에 있는 내용의 숫자를 공백으로 분리해서 적습니다.

그 다음에는 열에 있는 숫자들을 차례대로 적습니다.

5x5 짜리 간단한 예를 적으면 다음과 같습니다.

 

5 5

5

2

2

2

5

2 1

3 1

1 3

1 2

1 1

 

5x5 이므로, 파일의 총 라인수는 5+5+1 = 11 이 됩니다.

 

InitSolve() 멤버 함수는 주어진 로직을 풀기 위해서 초기화를 합니다.

 

Solve() 멤버 함수는 주어진 로직을 풉니다.  원래 이 프로그램은 네모네모로직의 해가 몇개인지 알기 위해서 짠 것이라, 첫번째 해를 풀면, Solve() 멤버 함수는 종료하게 만들었습니다.  다시 Solve() 멤버 함수를 호출하면, 다음번 해를 찾으며, 해가 없으면 false를 반환합니다.

 

PrintResult() 멤버 함수와 Print() 멤버함수는 화면에 표시하기 위한 목적입니다.

 

SetFirstPattern(), SetNextPattern() 멤버 함수는 한 행에 나올 수 있는 모든 패턴을 얻기 위한 함수입니다.  첫번째 패턴부터 시작해서 SetNextPattern() 멤버함수가 false가 될 때까지 반복합니다.

 

CheckPattern() 멤버 함수는 여러 행의 패턴이 올바르게 진행하는지 검사합니다.  그래서 패턴이 올바르게 진행되지 않으면, 백트레이스해서 진행합니다.

 

두번째,

패턴을 얻기 위한 SetFirstPattern(), SetNextPattern() 멤버 함수들을 작성합니다.

 

[SetFirstPattern(), SetNextPattern()]

void NemoLogic::SetFirstPattern(char *s, const char *p)
{
	memset(s, 0, colnum*sizeof(char));
	for( ; *p ; p++ )
	{
		for( int i = 0 ; i < *p ; i++ )
		{
			*s++ = 1;
		}
		s++;
	}
}

bool NemoLogic::SetNextPattern(char *s, const char *p)
{
	char pos[32];
	bool first = true;
	int k = 0;

	for( int i = 0 ; i < colnum ; i++ )
	{
		if( first && s[i] ) { first = false; pos[k++] = i; }
		if( !s[i] ) first = true;
	}

	int c = -1;
	for( int i = 0 ; i < k ; i++ )
	{
		int t = pos[i];
		for( int j = i ; j < k ; j++ )
			t += p[j]+1;
		if( t <= colnum ) c = i;
	}

	if( c == -1 ) return false;

	s += pos[c];

	memset(s, 0, (colnum-pos[c])*sizeof(char));
	for( ; c < k ; c++ )
	{
		s++;
		for( int i = 0 ; i < p[c] ; i++ )
			*s++ = 1;
	}
	
	return true;
}

 

 

패턴을 얻기 위해서는 주어진 숫자 갯수와 동일한 배열을 하나 사용합니다.  여기에 각각의 숫자들이 시작하는 위치를 저장합니다.  여기서도 백트레이스 기법을 이용하여 모든 패턴을 내줍니다.

 

세번째,

패턴을 검증하기 위한 CheckPattern() 멤버 함수를 작성합니다.

 

[CheckPattern()]

bool NemoLogic::CheckPattern(int row)
{
	if( row == rownum ) return false;

	int count;
	int k;
	for( int i = 0 ; i < colnum ; i++ )
	{
		count = 0;
		k = 0;
		for( int j = 0 ; j <= row ; j++ )
		{
			if( board[j*colnum+i] ) count++;
			else if( count > 0 )
			{
				if( count != cols[i][k] ) return false;
				count = 0;
				k++;
			}
		}
		if( row == rownum-1 && count != cols[i][k] ) return false;
		if( count > cols[i][k] ) return false;
		count = row-count;
		for( ; cols[i][k] ; k++ )
		{
			count += cols[i][k]+1;
		}
		if( count > rownum ) return false;
	}
	return true;
}

 

 

여기서는 모든 열에 대한 검사를 진행합니다.  한 열이라도 올바르지 않은 패턴이 발생하면 바로 false를 반환합니다.

 

완성된 프로그램의 실행화면입니다.