머리도 식힐겸 재미난 프로그램을 하나 만들어보았습니다.

이 프로그램에 필요한 기술은 

1. 2차원 slice

2. call by reference, call by value등에 대한 이해

3. 재귀호출

입니다.

우선 knight move가 무엇인지 궁금하실꺼라 생각합니다.

5x5 형태의 체스판이 있고 knight (장기로 쳤을 때 '마'에 해당하는 기물)가 한쪽 귀퉁이에 있습니다.

이 knight를 움직여서 모든 칸을 한번씩만 밟도록 하는 것이 목표입니다.

이 움직임을 두고 knight move라고 합니다. 

package main

import "fmt"
import "os"

type Position struct {
	x int
	y int
}

var knightMove []Position

func cloneBoard(src [][]int) [][]int {
	dest := make([][]int, len(src))

	for y, line := range src {
		dest[y] = make([]int, len(line))
		for x, p := range line {
			dest[y][x] = p
		}
	}

	return dest
}

func checkBoard(board [][]int) int {
	count := 0
	for _, line := range board {
		for _, p := range line {
			if p == 0 {
				count++
			}
		}
	}

	return count
}

func printBoard(board [][]int, history []Position) {
	fmt.Println("----------------------------------")
	cur := history[0]
	for _, move := range history[1:] {
		fmt.Println(move, (move.x - cur.x), (move.y - cur.y))
		cur = move
	}

	fmt.Println(history)
	fmt.Println("----------------------------------")
	for _, line := range board {
		fmt.Println(line)
	}
	fmt.Println("----------------------------------")
}

func moveKnight(board [][]int, history []Position) {
	if checkBoard(board) <= 0 {
		printBoard(board, history)
		os.Exit(0)
	}

	cur := history[len(history) - 1]
	for _, move := range knightMove {
		temp := cur
		temp.x = cur.x + move.x
		temp.y = cur.y + move.y

		if 0 <= temp.x && temp.x <= 4 && 0 <= temp.y && temp.y <= 4 {
			local := cloneBoard(board)

			if local[temp.y][temp.x] == 0 {
				local[temp.y][temp.x] = 1
				tempHistory := append(history, temp)
				moveKnight(local, tempHistory)
			} else {
			}
		}
	}
}

func main() {
	board := [][]int { {0,0,0,0,0},{0,0,0,0,0},{0,0,0,0,0},{0,0,0,0,0},{0,0,0,0,1}}
	history := make([]Position, 0, 30)

	knightMove = []Position {{2, 1}, {2, -1}, {1, 2}, {1, -2}, {-1, 2}, {-1, -2}, {-2, 1}, {-2, -1}}


	cur := Position{4, 4}
	history = append(history, cur)
	moveKnight(board, history)

}

간단하게 결과만 보기 위해서 작성한 프로그램이라 특별한 기교는 부리지 않았습니다.

knight의 최초 위치를 우하 귀퉁이로 설정하고 움직일 수 있는 모든 칸에 대해서 재귀호출을 반복하는 형식입니다.

그렇게 했을 때 가장 먼저 모든 칸을 다 밟은 경우의 결과 1개에 대해서 출력을 하고 프로그램을 중단합니다.