问题描述:

所谓“马踏棋盘”问题,就是指在中国象棋的棋盘上,用马的走法走遍整个棋盘,在8*8的方格中,每个格都要遍历,且只能遍历一次。

我们把棋盘抽象成一个二维数据,输入起始位置的坐标(x,y),根据马的“日”字走法,将马走的步数写入二维数组,然后输出.

解决思路

设当前马的坐标为(x,y),则下一步可以走的有8 个方向

(x-2,y+1)、(x-1,y+2)、(x+1,y+2)、(x+2,y+1)、(x+2,y-1)、(x+1,y-2)、(x-1,y-2)、(x-2,y-1)

创建一个二维数组记录马可以走的8个方向

chess     [8][8]int //初始化棋盘
direction = [2][9]int{{0, -2, -1, 1, 2, 2, 1, -1, -2},
        {0, 1, 2, 2, 1, -1, -2, -2, -1}} // 马可以走的8个方向
        探测下一步需要走,可以用下面公式
        x = x+direction[0][i]
        y = y+direction[1][i]

每一个马都有八个下一步的选择,我们在满足要求的点中任意找一个进行遍历,当八个点都不满足要求时,就回溯的上一步,找其他点进行遍历。

Feasible 该点是不是可以走,超出棋盘界限或者已经走过(棋盘初始为0),都不能走.
0 <= x && x < 8 && 0 <= y && y < 8 && chess[x][y] == 0

贪心算法

[ 2  3  4  4  4  4  3  2]
[ 3  4  6  6  6  6  4  3]
[ 4  6  8  8  8  8  6  4]
[ 4  6  8  8  8  8  6  4]
[ 4  6  8  8  8  8  6  4]
[ 4  6  8  8  8  8  6  4]
[ 3  4  6  6  6  6  4  3]
[ 2  3  4  4  4  4  3  2]

当(x,y)点被占用的时候,当前节点权值设置为9,位置(x,y)周围所有的可行点权值减1

setWeight(2,7)
[ 2  3  4  4  4  4  2  2]  //3-->2
[ 3  4  6  6  6  5  4  3]  //6-->5
[ 4  6  8  8  8  8  6  9]  //4-->9
[ 4  6  8  8  8  7  6  4]  //8-->7
[ 4  6  8  8  8  8  5  4]  //6-->5
[ 4  6  8  8  8  8  6  4]
[ 3  4  6  6  6  6  4  3]
[ 2  3  4  4  4  4  3  2]

需要重新计算weight[i][j]的权值, 依次探测周围,若可行,则weight[i][j]++;

其周围可行点的权值weight[x][y]++

NextDirection 每次走下一步,选择下一步最少的权值,进行贪心算法.

如果不先遍历它的话以后可能会很难遍历到它,即使能遍历到,也需要花费大量的回退操作.

go代码

/*
Copyright 2019 louis.
@Time : 2019/9/25 22:30
@Author : louis
@File : mataqipan
@Software: GoLand

*/

package main

import (
    "fmt"
    "gogs.wangke.co/go/algo/stack"
)

var (
    chess     [8][8]int //初始化棋盘
    direction = [2][9]int{{0, -2, -1, 1, 2, 2, 1, -1, -2},
        {0, 1, 2, 2, 1, -1, -2, -2, -1}} // 马可以走的8个方向
    cur, next Spot        //当前步数和下一步
    s         stack.Stack //栈
    weight    [8][8]int   //表示该位置周围可行点的数目,比如weight[0][0] = 2 只有两步可走.
)

//Spot 保存当前点的位置及可行走方向是否走过
type Spot struct {
    x int    //行
    y int    //列
    d [9]int //d[i]记录了第i号方向是否已经走过,1表示走过
}
//Feasible 该点是不是可以走,超出棋盘界限或者已经走过,都不能走.
func Feasible(x, y int) bool {
    if 0 <= x && x < 8 && 0 <= y && y < 8 && chess[x][y] == 0 {
        return true
    }
    return false
}


//NextDirection 每次走下一步,选择下一步最少的权值,进行贪心算法,返回下一步的方向
func NextDirection(c Spot) int {
    var MinDirection, Min int
    var x, y int
    Min = 9
    for i := 1; i <= 8; i++ {
        //访问过则不考虑
        if c.d[i] != 0 {
            continue
        }
        x = c.x + direction[0][i]
        y = c.y + direction[1][i]
        //选择最小的权值
        if Feasible(x, y) && weight[x][y] < Min {
            Min = weight[x][y]
            MinDirection = i
        }
    }
    return MinDirection
}


// InitWeight 初始化每个点的权值
// 初始为0; 对每个点进行探索,若方向可以行,则weight[i][j]++
func InitWeight() {
    for i := 0; i < 8; i++ {
        for j := 0; j < 8; j++ {
            for k := 1; k <= 8; k++ {
                x := i + direction[0][k]
                y := j + direction[1][k]
                if Feasible(x, y) {
                    weight[i][j]++
                }
            }
        }
    }
}

//SetWeight 当(x,y)点被占用的时候,当前节点权值设置为9,位置(x,y)周围所有的可行点权值减1
func SetWeight(x, y int) {
    for k := 1; k <= 8; k++ {
        weight[x][y] = 9
        i := x + direction[0][k]
        j := y + direction[1][k]
        if Feasible(i, j) {
            weight[i][j]--
        }
    }
}

// UnsetWeight 回退操作,需要重新计算weight[i][j]的权值,
// 依次探测周围,若可行,则weight[i][j]++; 其周围可行点的权值+1
func UnsetWeight(x, y int) {
    for k := 1; k <= 8; k++ {
        weight[x][y] = 0
        i := x + direction[0][k]
        j := y + direction[1][k]
        if Feasible(i, j) {
            weight[x][y]++
            weight[i][j]++
        }
    }
}
//output 输出棋盘
func output() {
    for j := 0; j < 8; j++ {
        fmt.Printf("%2d\n", chess[j])
    }
    //for j := 0; j < 8; j++ {
    //  fmt.Printf("%2d\n", weight[j])
    //}
}

func outWeight() {
    for j := 0; j < 8; j++ {
        fmt.Printf("%2d\n", weight[j])
    }
}

// 当找不到下一个位置时,即NextDirection返回值为0,要进行回退
// 为了回退方便,使用栈来存储, 能进时,当前的位置入栈, 向i走一步
// 回退操作, 在棋牌的cur点置0,Step--; 出栈一个点,设置为当前的cur
// 回退操作, 不能重复探测,去重操作.
func main() {
    InitWeight()
    //outWeight()
    fmt.Scanln(&cur.x,&cur.y)
    backup := 0
    Step := 1
    SetWeight(cur.x, cur.y)
    chess[cur.x][cur.y] = Step
    for Step < 64 {
        //获取下一步访问方向,根据贪心策略,会选择这一步的weight值最少的那个方向
        k := NextDirection(cur)
        if k != 0 {
            //这一步可以走,将这一步记录下来
            next.x = cur.x + direction[0][k]
            next.y = cur.y + direction[1][k]
            cur.d[k] = 1
            s.Push(cur)
            cur = next
            Step++
            chess[cur.x][cur.y] = Step
            SetWeight(cur.x, cur.y)
            //回退
        } else {
            //这步不可以走,得回退到上一步
            chess[cur.x][cur.y] = 0
            backup++//回退次数
            Step--
            UnsetWeight(cur.x, cur.y)
            cur = s.Pop().(Spot)
        }
    }
    output()
    fmt.Print(backup)
}

依赖的stack

/*
@Time : 2019/9/23 23:29
@Author : louis
@File : stack
@Software: GoLand
*/

package stack

type Item struct {
    item interface{}
    next *Item
}

// Stack is a base structure for LIFO
type Stack struct {
    sp    *Item
    depth uint64
}

// Initialzes new Stack
func New() *Stack {
    var stack = new(Stack)

    stack.depth = 0
    return stack
}

// Pushes a given item into Stack
func (stack *Stack) Push(item interface{}) {
    stack.sp = &Item{item: item, next: stack.sp}
    stack.depth++
}

// Deletes top of a stack and return it
func (stack *Stack) Pop() interface{} {
    if stack.depth > 0 {
        item := stack.sp.item
        stack.sp = stack.sp.next
        stack.depth--
        return item
    }

    return nil
}

// Peek returns top of a stack without deletion
func (stack *Stack) Peek() interface{} {
    if stack.depth > 0 {
        return stack.sp.item
    }

    return nil
}

//IsEmpty returns true means Empty Stack
func (stack *Stack) IsEmpty() bool  {
    return stack.depth == 0
}

验证

$ go run main.go
2 4  
[25 12 27 38 23  2 59 52]
[28 39 24 13 58 51 22  3]
[11 26 37 42  1 60 53 62]
[40 29 14 57 50 63  4 21]
[15 10 41 36 43 56 61 54]
[32 35 30 49 64 47 20  5]
[ 9 16 33 44  7 18 55 46]
[34 31  8 17 48 45  6 19]
0

感谢您的阅读~

参考