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