No older revisions available
No older revisions available
Synopsis ¶
- 나이트가 움직일 수 있는 여덟 방향을 일정한 순서에 따라 움직인다.
(2, -1), (1, -2), (-1, -2), (-2, -1), (-2, 1), (-1, 2), (1, 2), (2, 1)
- 나이트가 체스판의 모든 칸을 한번씩 방문하면 종료된다.
- 시작 지점을 (0, 0) 부터 (7, 7) 까지 64가지로 하여 순서대로 검색한다.
- 시작 지점과 종료 지점을 화면에 출력한다.
- 나이트가 움직인 순서를 화면에 출력한다.
Knight.h ¶
~cpp
// 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 ¶
~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 ¶
~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 과정을 한 번 더 실행하면 루트를 찾는 시간이 훨씬 짧아짐.
