KnightTour/재니

Author's Page

*02 장재니 Genie

Synopsis

• 나이트가 움직일 수 있는 여덟 방향을 일정한 순서에 따라 움직인다.

 (2, -1), (1, -2), (-1, -2), (-2, -1), (-2, 1), (-1, 2), (1, 2), (2, 1)

• 나이트가 체스판의 모든 칸을 한번씩 방문하면 종료된다.
• 시작 지점을 (0, 0) 부터 (7, 7) 까지 64가지로 하여 순서대로 검색한다.
• 시작 지점과 종료 지점을 화면에 출력한다.
• 나이트가 움직인 순서를 화면에 출력한다.

Source

Knight.h

// Knight.h: interface for the CKnight class.
//
//////////////////////////////////////////////////////////////////////

#if !defined(AFX_KNIGHT_H__B5234B12_3582_4CB8_8253_6ADFBE7B5E68__INCLUDED_)
#define AFX_KNIGHT_H__B5234B12_3582_4CB8_8253_6ADFBE7B5E68__INCLUDED_

#if _MSC_VER > 1000
#pragma once
#endif // _MSC_VER > 1000

class CKnight  
{
private:
	int m_ChessBoard[8][8];
	int m_Vertical[8], m_Horizontal[8];
	int m_CurrentRow, m_CurrentColumn;
	int m_Footprint[65];
	unsigned int m_Move;
public:
	void tour();
	void showPosition();
	void showNightTour();
	CKnight(int sr, int sc);
	virtual ~CKnight();
};

#endif // !defined(AFX_KNIGHT_H__B5234B12_3582_4CB8_8253_6ADFBE7B5E68__INCLUDED_)

Knight.cpp

// Knight.cpp: implementation of the CKnight class.
//
//////////////////////////////////////////////////////////////////////

#include "Knight.h"
#include "iostream"
using namespace std;

//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////

CKnight::CKnight(int sr, int sc)
{
	int tempHorizontal[] = {2, 1, -1, -2, -2, -1, 1, 2};
	int tempVertical[] = {-1, -2, -2, -1, 1, 2, 2, 1};
	for (int row = 0 ; row < 8 ; row++){
		for (int col = 0 ; col < 8 ; col++) {
			m_ChessBoard[row][col] = 0;
			m_Footprint[row * 8 + col] = 0;
		}
		m_Horizontal[row] = tempHorizontal[row];
		m_Vertical[row] = tempVertical[row];
	}
	m_Move = 0;
	
	m_CurrentRow = sr, m_CurrentColumn = sc;
}

CKnight::~CKnight()
{

}

void CKnight::showNightTour()
{
	for (int row = 0 ; row < 8 ; row++) {
		printf("\n\n");
		for (int col = 0 ; col < 8 ; col++)
			printf("%d\t", m_ChessBoard[col][row]);
	}

	printf("\n\n경 로 :\n");
	for (int counter = 0 ; counter < 64 ; counter++){
		printf(" %d", m_Footprint[counter]);
		if (counter % 32 == 31)
			printf("\n");
	}
	printf("이동횟수 : %d\n", m_Move);

	system("pause");
	system("cls");
}

void CKnight::showPosition()
{
	printf("(%d, %d)", m_CurrentRow, m_CurrentColumn);
}

void CKnight::tour()
{
	for (int counter = 1 ; counter < 65 ; counter++) {
		m_ChessBoard[m_CurrentRow][m_CurrentColumn] = counter;
		
		int direction = -1;
		while (++direction <= 8 && m_ChessBoard[m_CurrentRow][m_CurrentColumn] < 64) {
			if (direction > 7) {		// BackStep
				direction = m_Footprint[--counter];
				int rewind = (direction + 4) % 8;
				m_ChessBoard[m_CurrentRow][m_CurrentColumn] = 0;
				m_CurrentRow += m_Horizontal[rewind];
				m_CurrentColumn += m_Vertical[rewind];
				continue;
			}

			m_CurrentRow += m_Horizontal[direction];
			m_CurrentColumn += m_Vertical[direction];

			if (m_CurrentRow < 0 || m_CurrentRow > 7
				|| m_CurrentColumn < 0 || m_CurrentColumn > 7
				|| m_ChessBoard[m_CurrentRow][m_CurrentColumn] != 0){
				m_CurrentRow -= m_Horizontal[direction];
				m_CurrentColumn -= m_Vertical[direction];
				continue;
			}

			m_Footprint[counter] = direction;
			m_Move++;
			break;
		}
	}
}

main.cpp

#include "Knight.h"

int main(){
	for (int row = 0 ; row < 8 ; row++)
		for (int col = 0 ; col < 8 ; col++){
			CKnight knight(row, col);
			knight.showPosition();
			knight.tour();
			knight.showPosition();
			knight.showNightTour();
			knight.~CKnight();
		}

	return 0;
}

Bugs & Gossips

• 재니야--; Night가 아니고 Knight야--;
  • 와하하~ 페이지 이름 잘못 적어서 새로 만들다..ㅡ.ㅡ;;; -재니
• 위의 알고리즘은 broot-force하게 루트를 찾는 것인데,

나이트가 위치한 셀이 고립된 경우 BackStep 과정을 한 번 더 실행하면 루트를 찾는 시간이 훨씬 짧아짐.

• • 셀이 고립되면 어차피 다른 경로로 접근할 수 없어서 BackStep 을 두번 한 건데...

  몇몇 경우에서 broot-force 보다 더 검색을 많이 하는 경우도 발견됨.