Maintenance script: Repair batch-0002 pages from live compare

2026-03-27T00:16:06Z

Repair batch-0002 pages from live compare

imported>Unknown at 05:23, 7 February 2021

2021-02-07T05:23:36Z

New page

= 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 보다 더 검색을 많이 하는 경우도 발견됨.

← Older revision		Revision as of 00:16, 27 March 2026
Line 26:		Line 26:
	{		{
	private:		private:
	int m_ChessBoard[8][8];		int m_ChessBoard[8][8];
	int m_Vertical[8], m_Horizontal[8];		int m_Vertical[8], m_Horizontal[8];
	int m_CurrentRow, m_CurrentColumn;		int m_CurrentRow, m_CurrentColumn;
	int m_Footprint[65];		int m_Footprint[65];
	unsigned int m_Move;		unsigned int m_Move;
	public:		public:
Line 55:		Line 55:
	CKnight::CKnight(int sr, int sc)		CKnight::CKnight(int sr, int sc)
	{		{
	int tempHorizontal[] = {2, 1, -1, -2, -2, -1, 1, 2};		int tempHorizontal[] = {2, 1, -1, -2, -2, -1, 1, 2};
	int tempVertical[] = {-1, -2, -2, -1, 1, 2, 2, 1};		int tempVertical[] = {-1, -2, -2, -1, 1, 2, 2, 1};
	for (int row = 0 ; row < 8 ; row++){		for (int row = 0 ; row < 8 ; row++){
	for (int col = 0 ; col < 8 ; col++) {		for (int col = 0 ; col < 8 ; col++) {
	m_ChessBoard[row][col] = 0;		m_ChessBoard[row][col] = 0;
	m_Footprint[row * 8 + col] = 0;		m_Footprint[row * 8 + col] = 0;
	}		}
	m_Horizontal[row] = tempHorizontal[row];		m_Horizontal[row] = tempHorizontal[row];
	m_Vertical[row] = tempVertical[row];		m_Vertical[row] = tempVertical[row];
	}		}
	m_Move = 0;		m_Move = 0;
Line 80:		Line 80:
	printf("\n\n");		printf("\n\n");
	for (int col = 0 ; col < 8 ; col++)		for (int col = 0 ; col < 8 ; col++)
	printf("%d\t", m_ChessBoard[col][row]);		printf("%d\t", m_ChessBoard[col][row]);
	}		}

	printf("\n\n경 로 :\n");		printf("\n\n경 로 :\n");
	for (int counter = 0 ; counter < 64 ; counter++){		for (int counter = 0 ; counter < 64 ; counter++){
	printf(" %d", m_Footprint[counter]);		printf(" %d", m_Footprint[counter]);
	if (counter % 32 == 31)		if (counter % 32 == 31)
	printf("\n");		printf("\n");
Line 103:		Line 103:
	{		{
	for (int counter = 1 ; counter < 65 ; counter++) {		for (int counter = 1 ; counter < 65 ; counter++) {
	m_ChessBoard[m_CurrentRow][m_CurrentColumn] = counter;		m_ChessBoard[m_CurrentRow][m_CurrentColumn] = counter;

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

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

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

	m_Footprint[counter] = direction;		m_Footprint[counter] = direction;
	m_Move++;		m_Move++;
	break;		break;
Line 158:		Line 158:
	** 셀이 고립되면 어차피 다른 경로로 접근할 수 없어서 BackStep 을 두번 한 건데...		** 셀이 고립되면 어차피 다른 경로로 접근할 수 없어서 BackStep 을 두번 한 건데...
	몇몇 경우에서 broot-force 보다 더 검색을 많이 하는 경우도 발견됨.		몇몇 경우에서 broot-force 보다 더 검색을 많이 하는 경우도 발견됨.

KnightTour/재니 - Revision history

Maintenance script: Repair batch-0002 pages from live compare

imported>Unknown at 05:23, 7 February 2021