拼圖求解器 - TreeNode幫助

Question

我想編碼拼圖求解器應用程序。 我需要找出需要多少動作，以及有多少種解決方案。

我不想在這個難題上提供太多的細節。 但玩家在移動時會圍繞網格（例如5 x 7） 移動，因此可能會捕獲障礙物，因此需要跟蹤板的狀態。 （可以這樣做一個字符串或數組）

我明白我需要創建一個樹節點，以根目錄開始（玩家起始位置） 並給出可能的行動的每個節點的孩子，直到所有可能的計算移動。 然後可以收集拼圖統計數據。 可能的解決方案的數量，要解決的最小移動次數，要解決的平均移動次數等。

我有創建的解謎邏輯，如果移動是可能的，並且會返回。 我在創建TreeNode結構時遇到問題，並確保移動不重複。

拼圖應用程序本身在iPhone上，但我正在Mac上編寫此解算器/編輯器。 任何幫助將非常感激。

Answer 1

也許你可以做一個tree recursion的變種？以遞歸方式遍歷樹，使每個末端節點返回一個值，表明如何到達那裏（如果有不同移動的成本）以及它如何到達那裏的描述。這當然要求玩家只向一個方向移動，否則樹形結構不會描述問題。關於你確切的問題看起來會更有幫助。

這可能是一個沉重的算法，但它完成了工作。

Answer 2

對於檢測重複狀態，您可以將狀態置於一組中，然後每次檢查新狀態時查看它們是否已經存在。雖然如果空間是一個問題，你將不得不求助於只檢查孩子是否與父母不一樣，或者這種方法的某種限制版本。

節點類非常簡單。它只包含一個指向父代的指針（如果有的話）以及它保存的變量（如狀態）。您也可能需要其他變量，具體取決於您的應用程序。

當你到達一個節點時，你使用一個後繼函數從那裏獲得所有的子節點（可以一次到達的狀態）並將它們添加到列表中。你從列表中摘下來遍歷樹。