使用深度优先搜索DFS求解star battle游戏
这里的star battle游戏不是指别的（像war frame），就是puzzle team club搞的游戏，在https://www.puzzle-star-battle.com/里面可以找到。
这里要解题的话，不能再像上回那样用舞蹈表（dancing link）了，因为游戏规则决定了方块的占用位置不是全部都要用，一个方格可以相邻1个或2个星星，无法像之前那样使用精确覆盖的做法。但是，这里要解题还是很简单的，约束条件的某一种（行内必须正好有n个星星）可以利用这点搞DFS。
star battle的规则如下：放置一定数量的星星在棋盘，使所有的星星邻近8格没有星星，且每行、每列、每个区域正好有指定数量的星星，至于指定数量是多少要看星星★左边是哪个数字
图1.1★表示每行每列每块必须正好有1个星星；3★则是正好有3个
这里就需要初始化每行每列每块占据的星星数为指定数字（这里的深度优先搜索参数就是行数，操作也是基于单行搜索，所以省略了每行占据星星数）
def init(): with open('starBattleChess1.txt','r') as f: chessStr = f.read() rowStrs = chessStr.split(' ') global rowsize, colsize rowsize = len(rowStrs) colsize = len(rowStrs[0].split(' ')) maxnum = 0 for rowStr in rowStrs: row = [] validrow = [] for j in range(2): occupy[j].append(limit) #0是每列，1是每块 for j in range(limit): answer.append([]) for colStr in rowStr.split(' '): maxnum = maxnum if int(colStr) < maxnum else int(colStr) row.append(int(colStr)) validrow.append(1) chess.append(row) valid.append(validrow)
深度优先搜索部分（基于单行横向搜索），答案部分用一个谜面长度*限制大小为长度的数组储存。这里对方格的占据操作使用类似于舞蹈表的消除（remove）和还原（resume）操作
def dfs(depth, occ, start): #print('depth : ' + str(depth) + ' occ : ' + str(occ) + ' start : ' + str(start)) if depth == rowsize: print(answer) printAnswer() return for i in range(start, colsize-limit+occ+1): if occupy[0][i] <= 0 or occupy[1][chess[depth][i]] <= 0 or valid[depth][i] == 0: continue resumePos = [] occupy[0][i] -= 1 occupy[1][chess[depth][i]] -= 1 for j in range(depth-1, depth+2): for k in range(i-1, i+2): if j < 0 or j > rowsize - 1:continue if k < 0 or k > rowsize - 1:continue if valid[j][k] != 0: valid[j][k] = 0 resumePos.append([j, k]) answer[depth * limit + occ] = [depth, i] if occ >= limit - 1: dfs(depth+1, 0, 0) else: dfs(depth, occ+1, i+1) for resume in resumePos: valid[resume[0]][resume[1]] = 1 occupy[0][i] += 1 occupy[1][chess[depth][i]] += 1