超星 - 9. 回溯算法 - 查题吧

填空题

回溯算法采用了的思想，与枚举的思路类似。

填空题

补充下列程序（数独）：board = [[5,3,0,0,7,0,0,0,0],[6,0,0,1,9,5,0,0,0],[0,9,8,0,0,0,0,6,0],[8,0,0,0,6,0,0,0,3],[4,0,0,8,0,3,0,0,1],[7,0,0,0,2,0,0,0,6],[0,6,0,0,0,0,2,8,0],[0,0,0,4,1,9,0,0,5],[0,0,0,0,8,0,0,7,9]]def checkBoard(i,j,num):for t in range(9):if t!=j and board[i][t] == num:return Falseif t!= i and board[t][j] == num:return Falsefor t in range(i-i%3, 3+i-i%3):for s in range(j-j%3, 3+j-j%3):if t!=i and s!=j and board[t][s] ==num:return Falsereturn Trueres = []import copydef helper(index):if index==:solution= copy.deepcopy(board)res.append(solution)i =j =if :for num in range(1,10):board[i][j] = numif checkBoard(i,j,num):helper(index+1)else:helper(index+1)

填空题

补充下列程序（N皇后问题）：n = 4cols = [0 for i in range(n)]def checkBoard(rowIndex):for i in range(rowIndex):if cols[i]==cols[rowIndex]:return Falseif abs(cols[i]-cols[rowIndex]) == :return Falsereturn Trueres = []def NQueens(rowIndex):if :board = [[0 for j in range(n)] for i in range(n)]for i in range(n):board[i][cols[i]] = 1res.append(board)returnfor i in range(n):cols[rowIndex] =if checkBoard(rowIndex):NQueens(rowIndex+1)NQueens(0)res

1