for (char i = '1'; i <= '9'; i++) { 

        //判别以后位置[row，col]能否可以放数字i，假设不能放再判别下        //一个能不能放，直到找到能放的为止，假设从1-9都不能放，就会下面 

        //直接return false 

        if (!isValid(board, row, col, i)) 

            continue;        //假设能放数字i，就把数字i放出来        board[row][col] = i;        //假设成功就直接前往，不需求再尝试了        if (backTrace(board, row, col)) 

            return true; 

        //否则就撤销重新选择        board[row][col] = '.'; 

    }    //假设以后位置[row，col]不能听任何数字，直接前往false 

    return false; 

}//验证以后位置[row，col]能否可以寄存字符cprivate static boolean isValid(char[][] board, int row, int col, char c) { 

    for (int i = 0; i < 9; i++) { 

        if (board[i][col] != '.' && board[i][col] == c) 

            return false; 

        if (board[row][i] != '.' && board[row][i] == c) 

            return false; 

        if (board[3 * (row / 3) + i / 3][3 * (col / 3) + i % 3] != '.' && 

                board[3 * (row / 3) + i / 3][3 * (col / 3) + i % 3] == c) 

            return false; 

    }    return true; 

} 

总结

回溯算法要和递归结合起来就很好了解了，递归分为两部分，第一部分是先往下传递，第二部分抵达终止条件的时分然后再反弹往回走，我们来看一下阶乘的递归

其实回溯算法就是在往下传递的时分把某个值给改动，然后往回反弹的时分再把原来的值恢复即可。比如八皇后的时分我们先假定一个位置可以放皇后，假设走不通就把以后位置给撤销，放其他的位置。假设是组合之类的成绩，往下传递的时分我们把以后值参加到list中，然后往回反弹的时分在把它从list中给移除掉即可。

(责任编辑：admin)