- 前言
- 一、日历拼图是什么？
- 1. 不带星期
- 2. 带星期
- 二、主要思想
- 三、主要代码
- 1. 定义拼图块
- 2. 定义底板
- 3. 拼图块初始化
- 4. 遍历拼图块找一个解
- 总结
前言
前几天刷抖音，发现有人在玩日历拼图，看起来还挺好玩的。一个拼图号称能拼出全年365天，于是上某宝一看，还有难度更高一级的，带星期的玩法，于是入手了一个玩。别说，还挺有意思的，就是有点浪费时间，有时候得花半个小时的时间去拼当天的拼图。
边玩边想，这个东西其实没什么技术含量，就是暴力法一直尝试，完全可以交给代码来完成。于是上 github 一搜，果然有大神写了代码，但大神用的是 C++，并且是不带星期的简单玩法。着手改造：
- 代码全部改成 go
- 加上星期
- dfs 剪枝优化
- 启动 http server
- 添加前端页面
完整代码地址：
Github 地址：https://github.com/LeoNumber1/calender_puzzle
Gitee 地址：https://gitee.com/leono1/calender_puzzle
线上体验地址：点击体验
一、日历拼图是什么？
【日历拼图】是一款益智游戏，有带星期和不带星期两种。
1. 不带星期底板为7乘7的格子，去掉右上角的两块和右下角的四块。拼图块总共有8个块，能拼出一年365天的日期。如下所示：
底板为7乘8的格子，去掉右上角的两块和左下角的四块。拼图块总共有10个块，能拼出365*7的日期。堪称“顶级难度”的日历拼图，据说有2604种拼法，如下所示：
二、主要思想- 初始化底板map；
- 底板中加入墙体和日期；
- 初始化拼图块puzzle；
- 每个拼图块顺时针旋转90°四次，再镜像后顺时针旋转90°四次，将每次的结果去重后保存，得到每个拼图块能拼的所有形状shape；
- 遍历每一个拼图块及其形状，在底板上找一个合适的位置放下；检查是否能将其放置在map上的xy位置处，左上角对齐xy，如果能放置，则放置，设置map对应区域；
- dfs 剪枝优化，如果有连通区域小于最小拼图块，则回溯；
- 重复步骤5，如果发现还有块不能放下，则回溯。直到所有的拼图块都能完美放入底板中。
拼图块结构体代码如下：
type Puzzle struct {
ShapeNum *int // 当前拼图块有多少变种
X, Y *int // 当前在图形中，左上角右上角坐标
ShapeIndex int // 当前拼图的形状索引
allShapes [constant.PUZZLE_NUM]Shape // 所有不同的形状
}
// Shape struct for A block shape
type Shape struct {
Height int // 当前形状高
Width int // 当前形状宽
MyShape [][]int // 当前形状
}
拼图块变换：
// Rotate 顺时针旋转90度
func (sh Shape) Rotate() Shape {
arr := make([][]int, sh.Width)
for i := range arr {
arr[i] = make([]int, sh.Height)
for j := range arr[i] {
arr[i][j] = sh.MyShape[sh.Height-1-j][i]
}
}
return Shape{
Height: sh.Width,
Width: sh.Height,
MyShape: arr,
}
}
// Flip 左右镜像翻转
func (sh Shape) Flip() Shape {
arr := make([][]int, sh.Height)
for i := range arr {
arr[i] = make([]int, sh.Width)
for j := range arr[i] {
arr[i][j] = sh.MyShape[i][sh.Width-1-j]
}
}
return Shape{
Height: sh.Height,
Width: sh.Width,
MyShape: arr,
}
}
比如上图的拼图块，可以定义为二维数组
{1, 1, 1},
{1, 0, 0},
{1, 0, 0},
最终可以变换成四种形状，如下：
{1, 1, 1}, {1, 1, 1}, {1, 0, 0}, {0, 0, 1},
{1, 0, 0}, {0, 0, 1}, {1, 0, 0}, {0, 0, 1},
{1, 0, 0}, {0, 0, 1}, {1, 1, 1}, {1, 1, 1},
2. 定义底板
底板结构体代码如下：
type Map [][constant.MAP_WIDTH]int
func NewMap(modeEasy bool) *Map {
var height = constant.MAP_HEIGHT
if !modeEasy {
height = constant.MAP_HEIGHT_HARD
}
cal := make(Map, height)
return &cal
}
设置墙体和日期：
// 设置墙体
func (m *Map) SetWall(modeEasy bool) {
(*m)[0][6] = constant.WALL
(*m)[1][6] = constant.WALL
if !modeEasy {
(*m)[7][0] = constant.WALL
(*m)[7][1] = constant.WALL
(*m)[7][2] = constant.WALL
(*m)[7][3] = constant.WALL
} else {
(*m)[6][3] = constant.WALL
(*m)[6][4] = constant.WALL
(*m)[6][5] = constant.WALL
(*m)[6][6] = constant.WALL
}
}
// 设置日期和星期
func (m *Map) SetDate(month, day int, week string) {
(*m)[(month-1)/6][(month-1)%6] = constant.MONTH
(*m)[(day-1)/7+2][(day-1)%7] = constant.DAY
switch week {
case constant.MONDAY:
(*m)[6][4] = constant.WEEK
case constant.TUESDAY:
(*m)[6][5] = constant.WEEK
case constant.WEDNESDAY:
(*m)[6][6] = constant.WEEK
case constant.THURSDAY:
(*m)[7][4] = constant.WEEK
case constant.FRIDAY:
(*m)[7][5] = constant.WEEK
case constant.SATURDAY:
(*m)[7][6] = constant.WEEK
case constant.SUNDAY:
(*m)[6][3] = constant.WEEK
}
return
}
3. 拼图块初始化
每个拼图块顺时针旋转90°四次，再镜像后顺时针旋转90°四次，将每次的结果去重后保存，得到每个拼图块能拼的所有形状shape。
func (p *Puzzle) InitShape(origin Shape) {
//给定初始形状，生成8个旋转、翻转形状，相同的不保存
p.allShapes[0] = origin
shapeNum := 1
tempShape := origin.Flip()
if !tempShape.Equal(origin) {
// 翻转后不相等
p.allShapes[1] = tempShape
shapeNum++
for i := 0; i < 3; i++ {
tempShape = tempShape.Rotate()
same := false
for j := 0; j < shapeNum; j++ {
if tempShape.Equal(p.allShapes[j]) {
same = true
tempShape = p.allShapes[j]
break
}
}
if !same {
p.allShapes[shapeNum] = tempShape
shapeNum++
}
}
}
tempShape = origin
for i := 0; i < 3; i++ {
tempShape = tempShape.Rotate()
same := false
for j := 0; j < shapeNum; j++ {
if tempShape.Equal(p.allShapes[j]) {
same = true
break
}
}
if !same {
p.allShapes[shapeNum] = tempShape
shapeNum++
}
}
p.ShapeNum = &shapeNum
}
4. 遍历拼图块找一个解
遍历每一个拼图块及其形状，在底板上找一个合适的位置放下；检查是否能将其放置在map上的xy位置处，左上角对齐xy，如果能放置，则放置，设置map对应区域；
func searchOneRes(modeEasy bool, calendar *shape.Map, week string) ([][constant.MAP_WIDTH]int, int64) {
var (
back bool // 回溯标识
stackIndex int // 拼图块索引
pieceNum = constant.PIECE_NUM // 块数量
height = constant.MAP_HEIGHT // 底板高度
puzs = puzzles // 拼图块数组
)
if !modeEasy {
pieceNum = constant.PIECE_NUM_HARD
height = constant.MAP_HEIGHT_HARD
puzs = puzzlesHard
}
// 逐一为拼图块选好位置和形状，如果遇到无处安放的块，则回溯
backCount := 0
for stackIndex < pieceNum && stackIndex >= 0 {
// 初始化
var i, j, k int
if back {
backCount++
//需要回溯，也就是当前拼图需要一个新的位置,要先从旧的位置删除掉
puzs[stackIndex].Clear(calendar)
i = *puzs[stackIndex].Y
j = *puzs[stackIndex].X
k = puzs[stackIndex].ShapeIndex + 1
} else {
i, j, k = 0, 0, 0
}
//为stack_index号拼图找一个位置
success := false
for ; i < height; i++ {
for ; j < constant.MAP_WIDTH; j++ {
for ; k < *puzs[stackIndex].ShapeNum; k++ {
if puzs[stackIndex].Check(calendar, j, i, k, height, modeEasy) {
success = true
break
}
}
if success {
break
}
k = 0
}
if success {
break
}
j = 0
}
if success {
stackIndex++
back = false
} else {
stackIndex--
back = true
}
}
fmt.Printf("Down.Total search %d possibilitiesn", backCount)
if show {
calendar.Show(height, week)
}
return *calendar, int64(backCount)
}
总结
把实际问题转化为代码解决是一件蛮酷的事情，尤其是看到代码一步步解决了问题，再一步步优化复杂度，满足和喜悦之情不胜言表。也许，这就是程序的魅力吧。
最后最后，附上完整代码地址，喜欢的话拜托点一个star吧，感谢！！！
完整代码地址：
Github 地址：https://github.com/LeoNumber1/calender_puzzle
Gitee 地址：https://gitee.com/leono1/calender_puzzle
