Recently, Large Language Models (LLMs) attained impressive performance in math and reasoning benchmarks. However, they still often struggle with logic problems and puzzles that are relatively easy for humans. To further investigate this, we introduce a new benchmark, , containing 11 unique search problems, each equipped with automated pipelines to generate an arbitrary number of instances and analyze the feasibility, correctness, and optimality of LLM-generated solutions. We show that even the most advanced LLMs fail to solve these problems end-to-end in text, e.g., GPT4 solves only 1.4%.  problems require considering multiple pathways to the solution as well as backtracking, posing a significant challenge to auto-regressive models. Instructing LLMs to generate code that solves the problem helps, but only slightly, e.g., GPT4's performance rises to 11.7%. In this work, we show that in-context learning with A* algorithm implementations enhances performance. The full potential of this promoting approach emerges when combined with our proposed Multi-Stage-Multi-Try method, which breaks down the algorithm implementation into two stages and verifies the first stage against unit tests, raising GPT-4's performance above 57%.

§ INTRODUCTION

The advent of Large Language Models (LLMs) has revolutionized the field of natural language processing, with models like Gemini[Li et al., 2024], GPT-4[OpenAI, 2023] demonstrating unprecedented performance on reasoning tasks such as GSM8k[Cobbe et al., 2021]. However, these models still exhibit surprising failures on some intuitive tasks[Bian et al., 2023, Qin et al., 2023, Marcus, 2020] and struggle with multi-step compositional reasoning, combinatorial problems, and planning [Dziri et al., 2024, Valmeekam et al., 2022, Wu et al., 2023]. Inspired by these observations and to further investigate LLMs' reasoning abilities,  we offer a new benchmark of search problems, .
The problems in  are combinatorial, defined as tasks that involve finding an optimal object from a finite set of objects, where the set of feasible solutions is either discrete or can be reduced to a discrete set [43]. These problems are predominantly NP-hard and necessitate systematic exploration of action paths and backtracking to intermediate feasible states; thus,  implicitly investigates the LLM's capacity for non-linear reasoning.

has five distinct problem categories: (i) pathfinding, (ii) puzzles, (iii) subset sum, (iv) sorting, and (v) under-determined systems; further divided into 11 unique problem types.

Each problem type is inspired by known puzzles and combinatorial problems but

augmented with modified rules and constraints to ensure substantial differences from similar problems LLMs encountered during their training. And the solution to each problem is a sequence of actions leading from the initial state to the goal state, while optimizing a cost.

We generate $\sim$100 instances of varying difficulty per problem type using an automatic pipeline, resulting in 1107 problem instances total.
Each problem type in  is equipped with an automatic pipeline that evaluates LLM-generated solutions on three dimensions: feasibility, correctness, and optimality. Feasibility checks whether the actions taken follow the problem's rules; correctness verifies if a feasible solution reaches the goal state; and optimality checks if the least cost solution was found.

is challenging to LLMs due to several factors. Firstly, natural language is less suited for describing or updating accurate representations of complex intermediate states.

Secondly, our experiments show LLMs struggle with exploring a combinatorial exponentially exploding state-space. Despite the fact that some methods were developed for long-context reasoning [Chen et al., 2023, Huang et al., 2022, Zhao et al., 2024],  problems cannot be easily summarized [Chen et al., 2023], reasoned about [Huang et al., 2022], or processed in parallel due to their size [Zhao et al., 2024, Xi et al., 2023].

Our findings show that even the strongest LLMs [OpenAI, 2023] almost completely fail to solve   problems in

text-only mode.

The taxonomy of SearchBench. The five nodes in level one represent the problem categories, and the 11 nodes in level two represent the problem types. We detail how the rules of known puzzles and combinatorial problems are modified in  to ensure that LLMs have not encountered a solved instance of the problem during their massive training.

To provide further insights, we show that LLMs' performance on  improves by prompting the models to solve the problems using the A* search algorithm [Hart et al., 1968]. A* is a heuristic-based graph traversal algorithm known for its time efficiency and provable optimality guarantees, making it the most suitable search algorithm for solving the problems in our benchmark. This method leverages A*'s correctness and optimality, while offloading some of the non-linear computations involved in searching the state-space to code execution.

Additionally, to improve the quality of generated A* codes, motivated that ensembling helps generation quality[Wang et al., 2022, Yao et al., 2023, Long, 2023], we introduce the  () inference strategy.

In the "Multi-Try" aspect of , before evaluating the solution returned by the code, we first verify whether the code generated by the model satisfies a set of unit tests: (i) it is executable; (ii) it returns a list as output; and (iii) data type of list elements is correct. If the code fails any of the tests,  re-runs the LLM until a valid code is generated or allowed number of attempts is exhausted.
The "Multi-Stage" aspect of  generates the code in two steps: (i) `A* Implementation' - the implementation of an instance-agnostic A* algorithm for the problem type; and (ii) Initialization - the instantiation of initial conditions and state variables of the problem instance. In  'Initialization' is generated conditioned on the `A* Implementation' (which is generated separately first and provided in `Intitialization' prompt).

We demonstrate that our  A* method (Fig. <ref>) significantly enhances the LLMs' ability to solve search problems, outperforming all other prompting strategies we used to evaluate models on , including 0-shot text, 4-shot Chain-of-Thought (CoT)[Wei et al., 2022] text, 0-shot code generation, and 4-shot A* prompting with the naive greedy decoding strategy.

To summarize, our main contributions are as follows:
(i) We contribute the  benchmark designed to assess the capability of LLMs in solving state-based problems requiring combinatorial search;
(ii) We introduce the A*  () framework that leverages the flexibility and natural language comprehension capabilities of LLMs, reliability and structured nature of the A* algorithm, along with unitests to verify LLMs' code generation in order to address search problems.

(iii) We show a strong advantage of  A* prompting for

solving search problems robustly with LLMs, suggesting interesting future work directions and yet leaving significant room for future improvement on .

Our  () A* prompting approach.

§  BENCHMARK

includes five categories of problems: puzzles, subset sum, sorting, pathfinding, and under-determined systems, further subdivided into 11 problem types and instantiated as 1107 natural language problem instances. Each problem type requires a different algorithmic approach to solve.

Our problems are inspired by well-known (mostly NP-hard) puzzles and search problems, though their rules were modified to ensure a solved instance of a problem similar to any SearchBench problem was not observed during LLMs' massive internet-scale training. The  taxonomy and rule modifications are illustrated in Fig. <ref>.

Additionally,  problem instances are of variable difficulty and guaranteed to be solvable.

Finally, we note that only basic algebra skills are required for  problems, ensuring standard model pre-training should suffice for computing the answer to the problems.

An example  problem is provided in Table <ref>, instances of each problem type with two difficulty levels are provided in Appendix section <ref>.

In contrast to other reasoning benchmarks [Saparov and He, 2022, Cobbe et al., 2021, Hendrycks et al., 2021, Patel et al., 2021, Clark et al., 2020, Tafjord et al., 2020, Sap et al., 2019, Le et al., 2019] that only measure correctness, to gain a more comprehensive understanding of LLM performance on , our evaluation pipeline assesses LLM solutions across 3 dimensions: Feasibility, Correctness, and Optimality.

Feasibility determines if any problem rule violations (e.g. passing through labyrinth walls) occurred along the solution steps.

Correctness requires that the solution path is both feasible and reaches the desired goal state from the given start state.

Optimality requires a solution that is both correct and has minimum problem-specific cost w.r.t. known optimum. For each  problem we have implemented a fast A* algorithm with a provably admissible and consistent heuristic that is guaranteed to produce an optimal solution against which we measure optimality.

Problem statement

In the 'taxed coin exchange' problem, you are required to choose a subset of coins from this list lightgreen[3, 6, 9, 10, 13, 15, 18, 5, 21, 19, 12, 15, 5, 9, 4, 16, 8, 4, 7, 7, 7, 2, 16, 14, 18, 3, 89, 21, 12, 10, 7, 14, 4, 11, 6, 20], such that the sum of the chosen coins adds up to lightgreen229. lightorangeEach coin in the list is unique and can only be used once. Also lightorangecoins carry a tax value. The tax values for each coin is lightgreen14: 1, 89: 13, 2: 2, 5: 2, 4: 4, 6: 6, 8: 2, 16: 5, 21: 4, 20: 2, 18: 9, 11: 10, 10: 3, 12: 12, 15: 5, 13: 1, 3: 1, 19: 19, 7: 7, 9: 3, where the tax for coins of the same value is the same. Also, lightorangeif the coin chosen is smaller than the previous one, it must have an even value, otherwise, if the coin is larger than or equal to the previous coin chosen, it must have an odd value. The objective is to determine which subset of coins should be selected to lightorangeminimize the total tax paid. The solution should be presented as a list of numbers, representing the value of the coins chosen in order, with the first coins chosen being in index 0, formatted in Python syntax.

An instance of the 'Coin Exchange' problem type as it was shown to LLMs. The lightgreengreen indicate instance-specific components, and the lightorangeorange represent modifications to the classic coin exchange problem rules specific to . GPT-4 fails to generate a feasible solution for this problem instance using our baseline promoting methods (0-shot, 4-shot CoT text, 0-shot code). However, produces correct but non-optimal code solution using A* and  A*.

§ EVALUATED METHODS

We use the following 3 baseline prompting methods to evaluate LLMs on : 0-shot text, 4-shot CoT text, and 0-shot code. Moreover, we introduce two additional code-based methods demonstrating improved performance: 4-shot A* prompting and  A*. The full prompts given to the models for each of the 5 approaches along with GPT-4's generations for an example problem in  are provided in Appendix section <ref>.

0-shot text and 4-shot CoT text prompting
instruct the model to solve the problem step-by-step (CoT [Wei et al., 2022]) using text only.

In CoT part of in-context examples we use ASCII character graphics to represent the intermediate states of the problem after each action in order to ground the model's generation and prevent hallucinations or illogical leaps in reasoning. In-context examples were always drawn from the four  problem categories that differ from the category of the evaluated problem instance.

0-shot code
instructs the LLM to produce a Python code that solves the given problem instance and explains the reasoning behind each line of code step-by-step (in code comments). Code is executed and its output is evaluated according to our metrics explained above.

A* Prompting
prompts the LLM to implement an A* algorithm that solves $\mathcal{P}^C_i$ - a problem instance number $i$ of problem category $C$, providing 4 in-context examples of A* codes for 4 unrelated problems $\mathcal{P}^{\hat{C}}_j$ from different categories $\hat{C} \ne C$. In in-context A* implementations, problem states are modeled as graph nodes, and A* is used to traverse the graph to find an optimal path to the goal state.

To implement A* for the target  problem, an LLM must perform a kind of abstract reasoning to devise a strategy that can be applied to any state within the search space. Additionally, it must understand the problem's rules and  map them to code by drawing parallels to rules of other (unrelated) problems and their respective A* implementations.

Our in-context examples include detailed comments before each code segment, explaining the reasoning used to develop the strategy implemented in the segment according to the problem statements. This encourages the LLM to implement the same kind of comments, which, in turn, serves as CoT reasoning for the generated A*.

() A* Prompting

receives the same in-context examples as the `A* prompting', but operates in two stages and with different instructions in the prompt (Fig. <ref>). In the first stage,
the model is instructed to divide the code into two functions: the 'a_star' function implementing an A* algorithm for the target problem type, and the 'initialize' function, which initializes the data structures and encodes the variables given in the problem statement.

At this stage we only verify if the generated code satisfies a set of unit tests: (i) code is executable; (ii) code returns a list; (iii) and the list elements match the data type specified by the problem statement. If the code fails any unit test we re-generate the code.
In the second stage, the LLM is instructed to implement a refined `initialize' function, conditioned on the `a_star' function from stage 1.

The inclusion of simple unit tests, which can be expanded to more detailed tests if needed, offers a robust method for selecting a higher-quality sample from the model's generations.

§ RELATED WORK

Mathematical and Reasoning Benchmarks: The evaluation of LLMs [Brown et al., 2020, OpenAI, 2023, OpenAI, 2022, Chung et al., 2024, Chowdhery et al., 2022, Rae et al., 2021, Taylor et al., 2022, Thoppilan et al., 2022] on mathematical and reasoning tasks has been a focus of recent research in natural language processing, leading to the development of benchmarks such as BIG-BENCH[Srivastava et al., 2022], GSM8K[Cobbe et al., 2021], AQUA[Ling et al., 2017], SVAMP[Patel et al., 2021], CommonsenseQA[Talmor et al., 2018], StrategyQA[Geva et al., 2021], and MATH[Hendrycks et al., 2021]. However, these benchmarks have limitations. For instance, GSM8K problems are relatively simple and often require a repetitive reasoning pattern to solve. The MATH dataset, while more challenging, may not accurately reflect a model's reasoning or problem-solving capabilities due to the advanced mathematical skills required. Tasks in BIG-BENCH are mostly single-step reasoning tasks which do not challenge the models in effectively combining multiple steps required solve compositionally complex problems. When prompted to solve problems end-to-end using CoT prompting, LLMs perform well on these tasks; however, they almost completely fail on our benchmark's problems, indicating that these benchmarks offer limited insight into LLMs’ ability to systematically explore a state space and explore multiple reasoning chains that might lead to a solution.

Application of LLMs to Combinatorial Problems:
Several recent studies [Yang et al., 2023, Liu et al., 2024, Masoud et al., 2024, Mittal et al., 2024, Iklassov et al., 2024] have explored using LLMs to solve combinatorial problems.  Yang et al., 2023, Liu et al., 2024, Masoud et al., 2024 investigated promting LLMs to solve the Traveling Salesman Problem through multiple inferences. Mittal et al., 2024 introduced a dataset of combinatorial problems, "PuzzleBench"; however, they only selected problems that can be represented in a symbolic solver (SMT2.0) and assumed there exists fixed pre-defined symbolic representations for input problems and outputs, somewhat limiting their datasets’ generalizability. Additionally, problems selected by Mittal et al., 2024 and Iklassov et al., 2024 are instances of the classical combinatorial problems, raising issues of memorization as algorithm implementations for instances of such problems are often available online.
In contrast, our benchmark features problems with altered rules to ensure they are out of LLM's training data distribution. These problems require optimized solutions based on uniquely defined costs, making them more open-ended and challenging. Moreover, we introduce an automated pipeline for generating new instances and evaluating solutions on multiple dimensions, significantly improving the scalability of generating various instances of each type of problem.

Prompting and Inference Strategies:
Sophisticated prompting strategies have been developed to enhance models' reasoning abilities. One notable approach is Chain-of-Thought (CoT) prompting [Wei et al., 2022], which prompts LLMs to generate the intermediate steps leading to the final output. This technique has led to advanced variations, including Self-consistency with CoT[Wang et al., 2022], Tree-of-Thoughts[Yao et al., 2023, Long, 2023], and Graph-of-Thought[Yao et al., 2023, Lei et al., 2023, Besta et al., 2023] methods. Decomposition prompting strategies, such as those by Khot et al., 2022, Zhou et al., 2022, Zhang et al., 2023, simplify complex tasks into smaller, manageable subtasks via symbolic programs or structured algorithms. Other works, like LLM-Augmenter system [Peng et al., 2023], rely on external databases to consolidate evidence and verify segments of the LLM generation.
In our experiments, we found CoT reasoning in text to be an ineffective prompting strategy for SearchBench problems. Hence, we propose the A* prompting strategy, where we prompt the model to solve problems by converting the problem states into a graph and implementing a unique A* algorithm to solve them. Similarly, our A* MSMT approach decomposes the task of implementing the search algorithm into two stages and checks the model's generations against external validators; we use simple unit tests instead of external data sources or solved solution instances in our work.

§ EXPERIMENTS

Implementation details:
GPT-4 and GPT-3.5 Turbo (GPT3.5 hereafter) were used through official Open-AI platform APIs. For all code evaluation experiments we used a machine with 96 64-bit Intel Xeon Gold 5220R CPUs with a maximum speed of 4GHz, and 71.5 MiB Level 3 cache.

Average rate of feasible, correct, and optimal solutions and compute time of codes returning a correct solution for all problems using GPT4, GPT3.5, and Code Llama.

We evaluated the SearchBench performance of GPT-4 [OpenAI, 2023], GPT-3.5, and Code Llama Instruct 34B [Roziere et al., 2023] (finetuned on the Phind dataset [29]), using the five methods explained in Sec. <ref>: 0-shot text, 4-shot CoT text, 0-shot code, 4-shot A*, and 4-shot  A*. Results are summarized in Fig. <ref>.

0-shot text and 4-shot CoT text: The combinatorial nature of the search space of  problems and the difficulty of backtracking on state sequences explored during auto-regressive generation, make it very challenging to solve the problems using text based promoting approaches even using the strongest LLMs.
As shown in Fig. <ref>, the correct solutions rate of both GPT4 and GPT3.5 is below 1% using 0-shot text prompting, and less than 9% of GPT4 solutions are feasible (follow the problem rules).

4-shot CoT text prompting improves the correct rate to 1.4% for GPT4, and negligibly improves the feasible rate by less than 2%.
This validates that the inherent complexity of  search problems cannot be effectively addressed by text-based prompting alone.

0-shot code: This promoting method results in a small improvement compared to text-based prompting.

From Fig. <ref>, less than 20% of GPT-4’s code generations result in a feasible solution, with only 11.7% being correct.

Moreover, on average, GPT-4’s 0-shot code generations, returning a correct solution, run 900 times slower than the optimal A* implementation. Expectedly, GPT-3.5 and Code Llama fall significantly below GPT4. This indicates  problems are indeed difficult even when facilitated through code generation.

Performance of GPT4, prompted with our code-based approaches, on each problem.

A* Prompting: As shown in Fig. <ref>, A* prompting improves GPT-4 and GPT-3.5 performance on . GPT-4's feasible, correct, and optimal solution rates increase by 10%, 5%, and 5% respectively. The compute time improved to 213 times slower than optimal A* implementation, indicating GPT-4's heuristics are still less efficient than optimal. However, Code Llama shows almost no improvement, indicating potential limitations in the model's in-context learning capability or ability to follow instructions.

Count of feasible, correct, and optimal solutions generated by GPT4 via code-based methods for 3 levels of problem difficulty.

Figure <ref> details GPT-4 code-based method performance for each of 's 11 problems. Consistently 4-shot A* prompting outperforms 0-shot code for most problems. Interestingly for problems in the pathfinding category, prompting GPT4 with 0-shot code outperforms A* prompting.

Examining closer, GPT-4 mainly uses DFS for pathfinding in 0-shot code. While simpler than A*, DFS doesn't guarantee optimal solutions, as reflected in GPT-4's high feasible and correct rates but lower optimal rates. Implementing A* with an admissible and consistent heuristic requires the model to implement a more complex strategy in the code involving additional constraints and more sophisticated data structures. This increases the likelihood of reasoning or coding errors, which could explain the dip in GPT-4's performance using A* prompting compared to 0-shot code when solving these problems.

From Fig. <ref>, we see that the  A* prompting significantly enhances performance of both GPT-4 and GPT-3.5. With  A*, GPT-4's code generations correctly solved 57.1% of  problem instances and attained a 28.6% rate of optimal solutions, consistently outperforming the model's performance using other promoting strategies for all problem types (Fig. <ref>). A similar strong improvement is observed for other LLMs (only in feasibility in Code Llama as it still has issues with following the instructions even when using  A*).
The improvement of  A* over A* prompting shows that while LLMs can generate correct code, they often make coding and reasoning errors.  unit tests help select higher-quality samples to mitigate these errors. The overall improvement in performance of LLMs promoted with  A* demonstrates that emulating a structured algorithm in models through in-context learning and selecting a verified sample can significantly boost LLM's problem-solving capabilities. That said, the 28.6% optimal performance, although inspiring, still leaves a lot of room for further improvements, underlining the importance of  for future research.

Comparing GPT-4's performance, using A* prompting approaches, when one of the in-context examples is switched to a problem that shares the same category as the inference problem.

§ ABLATIONS AND ANALYSIS

Does including a more similar problem in the in-context examples improve GPT-4's performance?

In our main experiments with A* and  A* (Fig. <ref>), we used 4 different category problems (different from target evaluated problem) as in-context examples (Sec. <ref>). This ensured no segment of the target problem solution was observed by the LLM in the in-context examples, hence better measuring LLM's reasoning generalization.

Here, we evaluated the effect of the prompt including a solved instance of a  problem of a different type than the evaluated problem, but sharing the same category. We used 5  problems (1 per category) for this evaluation. Results are summarized in Fig. <ref>.

For all problems we observe small improvements of up to 15 additional instances solved. This underlines that  problems of the same category are still significantly different in terms of their rules, constraints, and the target A* algorithm implementations.

We observe the most significant improvement for the Consecutive Grid problems, from the `under-determined systems' category. Mapping states of the under-determined systems to a graph is a difficult task, and this category more significantly differs from the others in terms of needed reasoning patterns, intuitively supporting our finding that seeing more similar problems in the prompt should lead to greater improvement.

Rate of errors returned by python programs generated by GPT-4, categorized into 6 error types, calculated across all problems in  for which the provided solution was not feasible.

What types of errors occur, and how often, when running GPT-4's codes generated using different prompting methods? We analyzed the run result of codes generated by GPT-4 that resulted in infeasible solutions, either by returning solutions that violated problem rules or by failing to produce valid solutions. The results of this analysis are summarized in Fig. <ref>. In this figure "Solution Not Feasible" indicates that the code executed successfully and returned a solution in the correct format, but the solution did not adhere to the problem rules. "Program Returned None" means the program failed to find a solution, despite all instances in our dataset having provable guarantees to be solvable."Program Killed" signifies that the program did not complete execution within the allotted time frame (set between 2200 to 3200 seconds depending on the problem type. Our fast A*  implementation return an optimal solution for all  problems in under 600 seconds on the same system.)

As shown in Fig. <ref>, prompting the model with the A* method results in a higher number of non-compiling code instances compared to 0-shot code prompting. This is expected as implementing A* is more complex and requires generating longer code than the simpler algorithms typically used by the model in 0-shot code generation, such as the greedy algorithm, BFS, or DFS. However, the number of infeasible solutions significantly decreases with A* prompting, indicating that the model can better reason about the problem when provided with the A* code context.

When comparing A* prompting to the  A*method, we notice that all of the errors that lead to failing our unit tests significantly decrease. 'Program Returned None', 'Program Killed', 'Incorrect Solution Type', 'Incomplete Generation', and 'Program Didn't Compile' all fail at least one of the 3 unit tests utilized in our  method.

What are the most common reasoning errors made in GPT-4's A* implementations? We manually analyzed 50 A* codes generated by GPT-4 that returned an non-optimal solutions across five problems: three pathfinding problems and two puzzle problems. These problems were chosen because for them GPT-4 with A* prompting showed either the least or the greatest improvement compared to 0-shot code, respectively. We identified seven distinct failure modes in the GPT-4-generated A* implementations. Each failure mode corresponds to a critical subtask within the overall search strategy of the A* algorithm (see Tab.  <ref> for the list of subtasks). Failing any one of these subtasks results in a suboptimal solution.  Results are summarized in Tab. <ref> where the percent of `correct reasoning' (disregarding coding errors) is reported for each subtask.

As can be seen, in pathfinding problems, the most common reasoning mistake was failing to record the list of coordinates visited (13% success rate). Specifically, the model often did not record the start coordinate in the list of visited states. This in turn led to feasible yet incorrect solutions, as the intermediate actions taken adhered to the problem's rules. For the puzzle problems, the most frequent reasoning mistake was in encoding the goal state. This is likely because our puzzle problem designs featured unique expected goal states, e.g. different from the conventional 8-puzzle problem.

Pathfinding Problems     Puzzle Problems

Encoding Initial State     47%     100%

Encoding Goal State     74%     20%

Recording the Path/Actions     13%     70%

Exit Condition     70%     100%

Iterating Through Successor States     57%     100%

Generate New State     87%     100%

Admissible and Consistent Heuristc     93%     60%

The average accuracy of GPT-4 on the identified A* (failure modes) subtasks. This analysis was based on 50 codes implemented for pathfinding and puzzle problems, using A* prompting.

§ CONCLUSIONS, LIMITATIONS, AND BROADER IMPACT

In this work, we introduced , a pioneering benchmark designed to assess the reasoning capabilities of large language models (LLMs) in solving challenging and ubiquitous search problems using various text-based and code-based prompting methods.We demonstrated that advanced LLMs can, to some extent, successfully solve search problems by implementing structured algorithms with scaled reliability, especially when the models' implementations are verified against unit tests.

This suggests a potential future path for automating the addition of new problem types to . Specifically, we could leverage LLMs to generate evaluation and instance generation pipelines for new problem types based on a natural language description of the problem. Our  approach could then verify the accuracy of these pipelines using comprehensive unit tests, significantly streamlining the process of scaling the dataset to include new problem types.

Limitations: The primary challenge in developing the  dataset was scaling the number of problem types. Designing unique search problems and creating pipelines to generate numerous instances with guaranteed solutions is both time-consuming and complex. Additionally, implementing a fast, instance-agnostic A* algorithm and developing evaluation pipelines to assess LLM-proposed solutions on multiple criteria further adds to the complexity.

Broader Impact: Our research, which aims to assist the development of models capable of general reasoning and reliable problem-solving, has the potential to yield significant societal benefits. Combinatorial problems, like those in our dataset, are fundamental in fields such as robotics, logistics, network design, and industrial optimization. Developing models that can tackle unique versions of these problems by designing efficient algorithms or performing systematic searches end-to-end could greatly enhance AI's applicability across various domains.  However, this improvement in the reasoning capabilities of language models could also lead to job displacement, as these models could increasingly automate complex tasks traditionally performed by humans.

[Besta et al., 2023]
Maciej Besta, Nils Blach, Ales Kubicek, Robert Gerstenberger, Lukas Gianinazzi, Joanna Gajda, Tomasz Lehmann, Michal Podstawski, Hubert Niewiadomski, Piotr Nyczyk, and Torsten Hoefler.
Graph of thoughts: Solving elaborate problems with large language models.
ArXiv, abs/2308.09687, 2023.

[Bian et al., 2023]
Ning Bian, Xianpei Han, Le Sun, Hongyu Lin, Yaojie Lu, Ben He, Shanshan Jiang, and Bin Dong.
Chatgpt is a knowledgeable but inexperienced solver: An investigation of commonsense problem in large language models.
arXiv preprint arXiv:2303.16421, 2023.

[Brown et al., 2020]
Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al.
Language models are few-shot learners.
Advances in neural information processing systems, 33:0 1877–1901, 2020.

[Chen et al., 2023]
Howard Chen, Ramakanth Pasunuru, Jason Weston, and Asli Celikyilmaz.
Walking down the memory maze: Beyond context limit through interactive reading.
arXiv preprint arXiv:2310.05029, 2023.

[Chowdhery et al., 2022]
Aakanksha Chowdhery, Sharan Narang, Jacob Devlin, Maarten Bosma, Gaurav Mishra, Adam Roberts, Paul Barham, Hyung Won Chung, Charles Sutton, Sebastian Gehrmann, Parker Schuh, Kensen Shi, Sasha Tsvyashchenko, Joshua Maynez, Abhishek Rao, Parker Barnes, Yi Tay, Noam M. Shazeer, Vinodkumar Prabhakaran, Emily Reif, Nan Du, Benton C. Hutchinson, Reiner Pope, James Bradbury, Jacob Austin, Michael Isard, Guy Gur-Ari, Pengcheng Yin, Toju Duke, Anselm Levskaya, Sanjay Ghemawat, Sunipa Dev, Henryk Michalewski, Xavier García, Vedant Misra, Kevin Robinson, Liam Fedus, Denny Zhou, Daphne Ippolito, David Luan, Hyeontaek Lim, Barret Zoph, Alexander Spiridonov, Ryan Sepassi, David Dohan, Shivani Agrawal, Mark Omernick, Andrew M. Dai, Thanumalayan Sankaranarayana Pillai, Marie Pellat, Aitor Lewkowycz, Erica Moreira, Rewon Child, Oleksandr Polozov, Katherine Lee, Zongwei Zhou, Xuezhi Wang, Brennan Saeta, Mark Díaz, Orhan Firat, Michele Catasta, Jason Wei, Kathleen S. Meier-Hellstern, Douglas Eck, Jeff Dean, Slav Petrov,
and Noah Fiedel.
Palm: Scaling language modeling with pathways.
J. Mach. Learn. Res., 24:0 240:1–240:113, 2022.

[Chung et al., 2024]
Hyung Won Chung, Le Hou, Shayne Longpre, Barret Zoph, Yi Tay, William Fedus, Yunxuan Li, Xuezhi Wang, Mostafa Dehghani, Siddhartha Brahma, et al.
Scaling instruction-finetuned language models.
Journal of Machine Learning Research, 250 (70):0 1–53, 2024.

[Clark et al., 2020]
Peter Clark, Oyvind Tafjord, and Kyle Richardson.
Transformers as soft reasoners over language.
arXiv preprint arXiv:2002.05867, 2020.

[Cobbe et al., 2021]
Karl Cobbe, Vineet Kosaraju, Mohammad Bavarian, Mark Chen, Heewoo Jun, Lukasz Kaiser, Matthias Plappert, Jerry Tworek, Jacob Hilton, Reiichiro Nakano, et al.
Training verifiers to solve math word problems.
arXiv preprint arXiv:2110.14168, 2021.

[Dziri et al., 2024]
Nouha Dziri, Ximing Lu, Melanie Sclar, Xiang Lorraine Li, Liwei Jiang, Bill Yuchen Lin, Sean Welleck, Peter West, Chandra Bhagavatula, Ronan Le Bras, et al.
Faith and fate: Limits of transformers on compositionality.
Advances in Neural Information Processing Systems, 36, 2024.

[Geva et al., 2021]
Mor Geva, Daniel Khashabi, Elad Segal, Tushar Khot, Dan Roth, and Jonathan Berant.
Did aristotle use a laptop? a question answering benchmark with implicit reasoning strategies.
Transactions of the Association for Computational Linguistics, 9:0 346–361, 2021.

[Hart et al., 1968]
Peter E. Hart, Nils J. Nilsson, and Bertram Raphael.
A formal basis for the heuristic determination of minimum cost paths.
IEEE Trans. Syst. Sci. Cybern., 4:0 100–107, 1968.

[Hendrycks et al., 2021]
Dan Hendrycks, Collin Burns, Saurav Kadavath, Akul Arora, Steven Basart, Eric Tang, Dawn Song, and Jacob Steinhardt.
Measuring mathematical problem solving with the math dataset.
arXiv preprint arXiv:2103.03874, 2021.

[Huang et al., 2022]
Jiaxin Huang, Shixiang Shane Gu, Le Hou, Yuexin Wu, Xuezhi Wang, Hongkun Yu, and Jiawei Han.
Large language models can self-improve.
arXiv preprint arXiv:2210.11610, 2022.

[Iklassov et al., 2024]
Zangir Iklassov, Yali Du, Farkhad Akimov, and Martin Takac.
Self-guiding exploration for combinatorial problems.
arXiv preprint arXiv:2405.17950, 2024.

[Khot et al., 2022]
Tushar Khot, Harsh Trivedi, Matthew Finlayson, Yao Fu, Kyle Richardson, Peter Clark, and Ashish Sabharwal.
Decomposed prompting: A modular approach for solving complex tasks.
arXiv preprint arXiv:2210.02406, 2022.

[Le et al., 2019]
Matthew Le, Y-Lan Boureau, and Maximilian Nickel.
Revisiting the evaluation of theory of mind through question answering.
In Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP), pages 5872–5877, Hong Kong, China, 2019. Association for Computational Linguistics.

[Lei et al., 2023]
Bin Lei, Pei-Hung Lin, Chunhua Liao, and Caiwen Ding.
Boosting logical reasoning in large language models through a new framework: The graph of thought.
ArXiv, abs/2308.08614, 2023.

[Li et al., 2024]
Chunyuan Li, Zhe Gan, Zhengyuan Yang, Jianwei Yang, Linjie Li, Lijuan Wang, Jianfeng Gao, et al.
Multimodal foundation models: From specialists to general-purpose assistants.
Foundations and Trends® in Computer Graphics and Vision, 160 (1-2):0 1–214, 2024.

[Ling et al., 2017]
Wang Ling, Dani Yogatama, Chris Dyer, and Phil Blunsom.
Program induction by rationale generation: Learning to solve and explain algebraic word problems.
arXiv preprint arXiv:1705.04146, 2017.

[Liu et al., 2024]
Fei Liu, Xialiang Tong, Mingxuan Yuan, Xi Lin, Fu Luo, Zhenkun Wang, Zhichao Lu, and Qingfu Zhang.
An example of evolutionary computation+ large language model beating human: Design of efficient guided local search.
arXiv preprint arXiv:2401.02051, 2024.

[Long, 2023]
Jieyi Long.
Large language model guided tree-of-thought.
arXiv preprint arXiv:2305.08291, 2023.

[Marcus, 2020]
Gary Marcus.
The next decade in ai: four steps towards robust artificial intelligence.
arXiv preprint arXiv:2002.06177, 2020.

[Masoud et al., 2024]
Mahmoud Masoud, Ahmed Abdelhay, and Mohammed Elhenawy.
Exploring combinatorial problem solving with large language models: A case study on the travelling salesman problem using gpt-3.5 turbo.
arXiv preprint arXiv:2405.01997, 2024.

[Mittal et al., 2024]
Chinmay Mittal, Krishna Kartik, Parag Singla, et al.
Puzzlebench: Can llms solve challenging first-order combinatorial reasoning problems?
arXiv preprint arXiv:2402.02611, 2024.

[OpenAI, 2022]
Chatgpt: Optimizing language models for dialogue, 2022.

[OpenAI, 2023]
Gpt-4 technical report.
ArXiv, abs/2303.08774, 2023.

[Patel et al., 2021]
Arkil Patel, Satwik Bhattamishra, and Navin Goyal.
Are nlp models really able to solve simple math word problems?
arXiv preprint arXiv:2103.07191, 2021.

[Peng et al., 2023]
Baolin Peng, Michel Galley, Pengcheng He, Hao Cheng, Yujia Xie, Yu Hu, Qiuyuan Huang, Lars Liden, Zhou Yu, Weizhu Chen, et al.
Check your facts and try again: Improving large language models with external knowledge and automated feedback.
arXiv preprint arXiv:2302.12813, 2023.

[29]
Beating gpt-4 on humaneval with a fine-tuned codellama-34b.

[Qin et al., 2023]
Chengwei Qin, Aston Zhang, Zhuosheng Zhang, Jiaao Chen, Michihiro Yasunaga, and Diyi Yang.
Is chatgpt a general-purpose natural language processing task solver?
arXiv preprint arXiv:2302.06476, 2023.

[Rae et al., 2021]
Jack W. Rae, Sebastian Borgeaud, Trevor Cai, Katie Millican, Jordan Hoffmann, Francis Song, John Aslanides, Sarah Henderson, Roman Ring, Susannah Young, Eliza Rutherford, Tom Hennigan, Jacob Menick, Albin Cassirer, Richard Powell, George van den Driessche, Lisa Anne Hendricks, Maribeth Rauh, Po-Sen Huang, Amelia Glaese, Johannes Welbl, Sumanth Dathathri, Saffron Huang, Jonathan Uesato, John F. J. Mellor, Irina Higgins, Antonia Creswell, Nathan McAleese, Amy Wu, Erich Elsen, Siddhant M. Jayakumar, Elena Buchatskaya, David Budden, Esme Sutherland, Karen Simonyan, Michela Paganini, L. Sifre, Lena Martens, Xiang Lorraine Li, Adhiguna Kuncoro, Aida Nematzadeh, Elena Gribovskaya, Domenic Donato, Angeliki Lazaridou, Arthur Mensch, Jean-Baptiste Lespiau, Maria Tsimpoukelli, N. K. Grigorev, Doug Fritz, Thibault Sottiaux, Mantas Pajarskas, Tobias Pohlen, Zhitao Gong, Daniel Toyama, Cyprien de Masson d'Autume, Yujia Li, Tayfun Terzi, Vladimir Mikulik, Igor Babuschkin, Aidan Clark, Diego de Las Casas, Aurelia Guy, Chris
Jones, James Bradbury, Matthew G. Johnson, Blake A. Hechtman, Laura Weidinger, Iason Gabriel, William S. Isaac, Edward Lockhart, Simon Osindero, Laura Rimell, Chris Dyer, Oriol Vinyals, Kareem W. Ayoub, Jeff Stanway, L. L. Bennett, Demis Hassabis, Koray Kavukcuoglu, and Geoffrey Irving.
Scaling language models: Methods, analysis & insights from training gopher.
ArXiv, abs/2112.11446, 2021.

[Roziere et al., 2023]
Baptiste Roziere, Jonas Gehring, Fabian Gloeckle, Sten Sootla, Itai Gat, Xiaoqing Ellen Tan, Yossi Adi, Jingyu Liu, Tal Remez, Jérémy Rapin, et al.
Code llama: Open foundation models for code.
arXiv preprint arXiv:2308.12950, 2023.

[Sap et al., 2019]
Maarten Sap, Hannah Rashkin, Derek Chen, Ronan Le Bras, and Yejin Choi.
Social IQa: Commonsense reasoning about social interactions.
In Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP), pages 4463–4473, Hong Kong, China, 2019. Association for Computational Linguistics.

[Saparov and He, 2022]
Abulhair Saparov and He He.
Language models are greedy reasoners: A systematic formal analysis of chain-of-thought.
arXiv preprint arXiv:2210.01240, 2022.

[Srivastava et al., 2022]
Aarohi Srivastava, Abhinav Rastogi, Abhishek Rao, Abu Awal Md Shoeb, Abubakar Abid, Adam Fisch, Adam R Brown, Adam Santoro, Aditya Gupta, Adrià Garriga-Alonso, et al.
Beyond the imitation game: Quantifying and extrapolating the capabilities of language models.
arXiv preprint arXiv:2206.04615, 2022.

[Tafjord et al., 2020]
Oyvind Tafjord, Bhavana Dalvi Mishra, and Peter Clark.
Proofwriter: Generating implications, proofs, and abductive statements over natural language.
arXiv preprint arXiv:2012.13048, 2020.

[Talmor et al., 2018]
Alon Talmor, Jonathan Herzig, Nicholas Lourie, and Jonathan Berant.
Commonsenseqa: A question answering challenge targeting commonsense knowledge.
arXiv preprint arXiv:1811.00937, 2018.

[Taylor et al., 2022]
Ross Taylor, Marcin Kardas, Guillem Cucurull, Thomas Scialom, Anthony Hartshorn, Elvis Saravia, Andrew Poulton, Viktor Kerkez, and Robert Stojnic.
Galactica: A large language model for science.
arXiv preprint arXiv:2211.09085, 2022.

[Thoppilan et al., 2022]
Romal Thoppilan, Daniel De Freitas, Jamie Hall, Noam Shazeer, Apoorv Kulshreshtha, Heng-Tze Cheng, Alicia Jin, Taylor Bos, Leslie Baker, Yu Du, et al.
Lamda: Language models for dialog applications.
arXiv preprint arXiv:2201.08239, 2022.

[Valmeekam et al., 2022]
Karthik Valmeekam, Alberto Olmo, Sarath Sreedharan, and Subbarao Kambhampati.
Large language models still can't plan (a benchmark for llms on planning and reasoning about change).
arXiv preprint arXiv:2206.10498, 2022.

[Wang et al., 2022]
Xuezhi Wang, Jason Wei, Dale Schuurmans, Quoc Le, Ed Chi, Sharan Narang, Aakanksha Chowdhery, and Denny Zhou.
Self-consistency improves chain of thought reasoning in language models.
arXiv preprint arXiv:2203.11171, 2022.

[Wei et al., 2022]
Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, Ed Huai hsin Chi, F. Xia, Quoc Le, and Denny Zhou.
Chain of thought prompting elicits reasoning in large language models.
ArXiv, abs/2201.11903, 2022.

[43]
Combinatorial optimization.

[Wu et al., 2023]
Zhaofeng Wu, Linlu Qiu, Alexis Ross, Ekin Akyürek, Boyuan Chen, Bailin Wang, Najoung Kim, Jacob Andreas, and Yoon Kim.
Reasoning or reciting? exploring the capabilities and limitations of language models through counterfactual tasks.
arXiv preprint arXiv:2307.02477, 2023.

[Xi et al., 2023]
Zhiheng Xi, Wenxiang Chen, Xin Guo, Wei He, Yiwen Ding, Boyang Hong, Ming Zhang, Junzhe Wang, Senjie Jin, Enyu Zhou, et al.
The rise and potential of large language model based agents: A survey.
arXiv preprint arXiv:2309.07864, 2023.

[Yang et al., 2023]
Chengrun Yang, Xuezhi Wang, Yifeng Lu, Hanxiao Liu, Quoc V Le, Denny Zhou, and Xinyun Chen.
Large language models as optimizers.
arXiv preprint arXiv:2309.03409, 2023.

[Yao et al., 2023]
Shunyu Yao, Dian Yu, Jeffrey Zhao, Izhak Shafran, Thomas L. Griffiths, Yuan Cao, and Karthik Narasimhan.
Tree of thoughts: Deliberate problem solving with large language models.
ArXiv, abs/2305.10601, 2023a.

[Yao et al., 2023]
Yao Yao, Z. Li, and Hai Zhao.
Beyond chain-of-thought, effective graph-of-thought reasoning in large language models.
ArXiv, abs/2305.16582, 2023b.

[Zhang et al., 2023]
Tianhua Zhang, Jiaxin Ge, Hongyin Luo, Yung-Sung Chuang, Mingye Gao, Yuan Gong, Xixin Wu, Yoon Kim, Helen Meng, and James Glass.
Natural language embedded programs for hybrid language symbolic reasoning.
arXiv preprint arXiv:2309.10814, 2023.

[Zhao et al., 2024]
Andrew Zhao, Daniel Huang, Quentin Xu, Matthieu Lin, Yong-Jin Liu, and Gao Huang.
Expel: Llm agents are experiential learners.
In Proceedings of the AAAI Conference on Artificial Intelligence, pages 19632–19642, 2024.

[Zhou et al., 2022]
Denny Zhou, Nathanael Schärli, Le Hou, Jason Wei, Nathan Scales, Xuezhi Wang, Dale Schuurmans, Claire Cui, Olivier Bousquet, Quoc Le, et al.
Least-to-most prompting enables complex reasoning in large language models.
arXiv preprint arXiv:2205.10625, 2022.

§ SEARCHBENCH NUTRITION LABELS

Filename     SearchBench.jsonl

Format     jsonl

Dataset repository on Huggingface     <https://huggingface.co/datasets/NasimBrz/SearchBench>

URL to Github repository     <https://github.com/NasimBorazjani/Navigating_Labyrinth.git>

URL to Croissant metadata     <https://github.com/NasimBorazjani/Navigating_Labyrinth/blob/main/SearchBench_croissant.json>

Domain     Reasoning benchmarch

Keywords     Search problems, combinatorial search, optimization, mathematical reasoning

Type     tabular

Rows     1107

Columns     14

Missing     0%

License     CC BY-SA

Released     June 2024

Description      is designed to evaluate the performance of LLMs in solving state-based problems that involve combinatorial search and optimization. It is motivated by the observation that LLMs often struggle with multi-step compositional reasoning, combinatorial problems, and planning. The problem types included in SearchBench are predominantly NP-hard, requiring systematic exploration of action paths and backtracking to intermediate feasible states for resolution. As a result,  targets some of the inherent limitations of the autoregressive architecture of LLMs, which necessitates generating solutions in a sequential manner. SearchBench provides a rigorous assessment of LLMs' capabilities in designing new algorithms to solve complex problems. It also investigates the non-linear reasoning capability of LLMs to solve search problems end-to-end using text only.

Name     Nasim Borazjanizadeh

Url     <https://github.com/NasimBorazjani>

Email<EMAIL_ADDRESS>&<EMAIL_ADDRESS>
diff_sorted_id     A unique numeric identifier assigned to each problem instance within a specific problem type. These identifiers are ordered by difficulty level, that is the problem instance with diff_sorted_id of 1 is  easier than the instance with diff_sorted_id of 50.

problem_statement     A natural language description that outlines the problem to be solved. The problem statement is the sole piece of information given to language models when they are instructed to solve  problems.

problem_type     Indicates the problem type, out of 11 problem types in , that this particular problem is an instance of.

problem_category     The specific category, out of the five predefined problem categories in , to which this problem belongs.

relative_diff_score     A numeric score that indicates the difficulty of this problem instance relative to other instances within the same problem type. This value is not comparable across different problem types.

opt_solution     A list of actions that, starting from the given initial state, lead to the goal state  with the minimum cost as defined by the problem's criteria.

opt_solution_cost     The cost of the optimal solution for this problem instance.

opt_solution_compute_t     The time, in seconds, that our instance-agnostic A* implementation for the problem type took to solve this specific problem instance.

solution_depth     The number of actions required to reach the goal state from the given initial state with the minimum cost. This metric can be used to calculate an upper bound on the size of the search tree, represented as $b^{d}$, for this instance, where, b is an upper bound on the branching factor of the tree, which indicates the maximum number of actions leading to successor states from any given state, and d is the solution depth, representing the number of actions in the optimal solution.

max_successor_states     The maximum number of successor states that can be reached from any given state in this problem. This value is an upper bound on the branching factor of the state search tree for this problem.

num_vars_per_state     An upper bound on the number of variables in each state of the problem. Given that the number of states grows exponentially for SearchBench problems, this value provides an estimate of the memory required to traverse the search tree of the problem.

is_feasible_args     A list of variables of the problem instance that must be passed to the ‘is_feasible’ function of the evaluation pipeline to determine whether a suggested solution adheres to the rules and constraints of the problem.

is_correct_args     A list of variables in the problem statement of this instance that must be passed as arguments to the 'is_correct' function in the evaluation pipeline, in order to evaluate the correctness of a suggested solution.

A*_args    Variables of this problem instance that must be passed to our A* implementation for the problem type to obtain the optimal solution for the instance.

This table provides a description of each column in SearchBench. Each row in SeacrhBench is an specific problem instance, and columns are fields of each instance.

name     type     min     median     max     mean     standard deviation     missing

opt_solution_compute_t     float (seconds)     0.018     0.068     599.044     17.363     67.513     0%

solution_depth     int     4     14     46     15.516     7.89     0%

max_successor_states     int     4     12     132     24.633     24.622     0%

num_vars_per_state     int     2     13     60     14.785     12.05     0%

Statistics of metrics pertaining to the search-tree-size of a specific instance, compared across all instances within SearchBench.

Search Tree Size Plots

The plots depict the correlation between the increasing difficulty level and the corresponding increase in three metrics: the average depth of the solutions, the branching factor of the state search tree, and the exponential growth of the time required by our A* algorithm to solve the instances, demonstrated across five problem types in SearchBench.

Figure <ref> presents the relationship between the size of the state search tree and the difficulty levels of instances in SearchBench. It displays the average solution-depth and max_successor_state (normalized against the maximum and minimum solution_depth and max_successor_state across all instances in SearchBench)  for one problem type from each of the five categories in SearchBench. Additionally, it shows the time our A* algorithm took to navigate the search tree for instances of variable difficulty (compute time is averaged across instances with the same difficulty). We used a machine with 96 64-bit Intel Xeon Gold 5220R CPUs with a maximum speed of 4GHz, and 71.5 MiB Level 3 cache to run the A* implementations.

The figure shows that the solution depth increases linearly with the difficulty scores of problem instances. However, for the city graph, it remains relatively constant, suggesting that the optimal number of hops to reach a destination node from a start node is consistent for our chosen range of directed graph connectivity and sizes (10 to 15 nodes).The max_successor_states, which represents the upper bound on the number of actions leading to successor states from each state, either remains constant or grows linearly with increasing difficulty level. This metric indicates the branching factor of the search tree size.

However, the compute time required to navigate this search tree grows much faster, exponentially, for most problems, as expected, given the search tree size is $b^{d}$, where b is the branching factor, and d is the solution depth. It's worth noting that we used a fast heuristic A* algorithm, which doesn't navigate the full search tree. An exhaustive algorithm like BFS, which explores every node, would result in a much faster exponential growth of compute times. In our experiments, a BFS implementation didn't finish executing even for some of the easiest instances within a 12-hour window.

§ GPT4'S MSMT A* IMPLEMENTATIONS FOR TWO INSTANCES OF EACH PROBLEM TYPE

In this section, we present the A* algorithm generated by GPT-4 using the MSMT A* prompting method, which successfully passed the unit tests. Additionally, we include GPT-4's implementation of the 'initialize' function for a more challenging instance, generated in the second stage of the MSMT.

To facilitate the model's reasoning process when mapping the problem to a graph, designing steps of the A* algorithm, and reasoning about the admissibility or consistency of the heuristic, we employ a Chain of Thought (CoT) reasoning in text as comments in our in-context examples. We provide additional information before each code segment in our prompts that walk through the reasoning steps required to arrive at the strategy implemented in the code. Below, you can observe GPT-4's comments that outline the intermediate reasoning steps the model generated to implement various code sections.

The implementations begin on the next page.

8 Puzzle

8_puzzle instance (diff_sorted_id: 1): In the 8-puzzle game, you are given a grid with numbered square tiles arranged randomly and one tile missing. The goal is to arrange the tiles in descending order by sliding them into the empty space. The tiles can move in 4 directions: left, right, up, and down.  Given the initial state of the puzzle below, where the empty spot is represented as “_”, provide the shortest list of tiles that need to be swapped with the empty spot to achieve the goal state. The goal state is when all tiles are in descending order, with the largest number in the top left corner, and the empty spot is in the bottom right corner. The solution should be a list of numbers in Python format, where each number represents the number on the tile that the empty spot is swapped with at each turn. Initial state of the puzzle: [[12, 55, '_'], [35, 97, 43], [17, 25, 9]]

A* algorithm generated by GPT4 for the problem above using A*  approach that passed the unit tests:[language=Python]
import heapq

def initialize():
# Define the initial state of the puzzle as a 2d tuple
initial_state = ((12, 55, '_'), (35, 97, 43), (17, 25, 9))
num_rows = 3
num_cols = 3
goal_state = ((97, 55, 43), (35, 25, 17), (12, 9, '_'))
visited_costs =
visited_costs[initial_state] = 0
queue = [(0, 0, [], initial_state)]
return initial_state, num_rows, num_cols, goal_state, visited_costs, queue

def a_star():
initial_state, num_rows, num_cols, goal_state, visited_costs, queue = initialize()
while queue:
_, g, actions, state = heapq.heappop(queue)
# If the current state is the goal state, return the actions taken
if state == goal_state:
return actions
# Generate all possible actions from the current state, which includes swapping the empty spot with any of the 4 neighboring tiles
empty_spot_coord = [(i, j) for i, row in enumerate(state) for j, element in enumerate(row) if element == '_'][0]
for d_row, d_col in [(0, -1), (0, 1), (1, 0), (-1, 0)]:
new_row, new_col = empty_spot_coord[0] + d_row, empty_spot_coord[1] + d_col
# Check if the new coordinate is valid, ie if the new tile is within the bounds of the puzzle
if 0 <= new_row < num_rows and 0 <= new_col < num_cols:
# Generate the new state
new_state = [list(row[:]) for row in state]
# Swap the empty spot with the new tile
new_state[empty_spot_coord[0]][empty_spot_coord[1]], new_state[new_row][new_col] = new_state[new_row][new_col], new_state[empty_spot_coord[0]][empty_spot_coord[1]]
new_state = tuple(tuple(row) for row in new_state)
# The cost so far is the number of swaps made, as the task is to minimize the number of swaps required
new_cost = g + 1
if new_state not in visited_costs or new_cost < visited_costs[new_state]:
visited_costs[new_state] = new_cost
# The action taken is the number on the tile that was swapped with the empty spot
heapq.heappush(queue, (g + heuristic(new_state, goal_state), new_cost, actions + [int(new_state[empty_spot_coord[0]][empty_spot_coord[1]])], new_state))
return None

*The GPT4's implementation of the A* algorithm continues on the next page.

Continuation of GPT-4's implementation: [language=Python]
def heuristic(state, goal):
# An admissible and consistent heuristic for this problem is the sum of the Manhattan distances from each tile in its current position to its position in the goal state
# This heuristic relaxes the constraint that only the empty spot can be moved, and assumes that each tile can be moved to its goal position independently of the others
# Thus the heuristic reports a lower estimate on the cost of reaching the goal state and is admissible
# The heuristic is consistent because the estimated cost from the current state to the goal can never be greater than the sum of cost from the current node to a successor node plus the estimated cost from the successor node to the goal because the cost of moving the empty spot to an adjacent tile is 1, which is equal to the decrease in the Manhattan distance of the tile that was swapped with the empty spot
# Also the cost of the goal state is 0, as all tiles are in their goal positions
h = 0
for i in range(len(state)):
for j in range(len(state[0])):
if state[i][j] != '_':
goal_coord = [(x, y) for x, row in enumerate(goal) for y, element in enumerate(row) if element == state[i][j]][0]
h += abs(i - goal_coord[0]) + abs(j - goal_coord[1])
return h

The A* algorithm was generated by GPT4 using the MSMT A* approach. For 8_puzzle problem type, GPT4's A* implementation for the first instance passed the unit tests.

8_puzzle instance (diff_sorted_id: 94): In the 8-puzzle game, you are given a grid with numbered square tiles arranged randomly and one tile missing. The goal is to arrange the tiles in descending order by sliding them into the empty space. The tiles can move in 4 directions: left, right, up, and down.  Given the initial state of the puzzle below, where the empty spot is represented as “_”, provide the shortest list of tiles that need to be swapped with the empty spot to achieve the goal state. The goal state is when all tiles are in descending order, with the largest number in the top left corner, and the empty spot is in the bottom right corner. The solution should be a list of numbers in Python format, where each number represents the number on the tile that the empty spot is swapped with at each turn. Initial state of the puzzle: [[98, 30, 85, 44, 59, 40], [56, 68, 50, 61, 47, 15], [37, 48, 24, 81, 22, '_']]

'initialize' function generated by GPT4 for the problem above in the second stage of the MSMT approach[language=Python]
def initialize():
# Define the initial state of the puzzle as a 2d tuple
initial_state = (('98', '30', '85', '44', '59', '40'),
('56', '68', '50', '61', '47', '15'),
('37', '48', '24', '81', '22', '_'))
num_rows = 3
num_cols = 6
# Define the goal state of the puzzle as a 2d tuple
goal_state = (('98', '85', '68', '61', '59', '56'),
('50', '48', '47', '44', '40', '37'),
('30', '24', '22', '15', '81', '_'))

visited_costs =
visited_costs[initial_state] = 0
queue = [(0, 0, [], initial_state)]
return initial_state, num_rows, num_cols, goal_state, visited_costs, queue

GPT4 was only successful in generating a feasible solution for this instance using the MSMT A* approach. The other four code and text-based prompting methods used in our experiments resulted in infeasible solutions.

8 Puzzle Words

8_puzzle_words instance (diff_sorted_id: 1): In the game 'Sort the Chars', we are given a table of n by m dimensions. This table contains n words, each with m characters, except for the first word which has m - 1 characters. Each character is written on a separate tile. The objective of the game is to rearrange the characters such that row i spells the i-th word in the list, with the blank tile ('_') placed in the top left corner of the board in the end. We can rearrange the tiles by swapping the blank space with any of its 4 diagonal neighboring tiles. Given the list of words and initial state of the board below, where the black space is represented as '_', what is the shortest list of swap actions (reported in python syntax) that can sort the board into the given list of target words? The list must only include the 4 diagonal swap directions: up-right, down-right, up-left, or down-left, representing the direction in which the blank space was swpped in. Target words: cam, hill, pray, doer   The initial board: [['i', 'c', 'a', 'm'], ['h', 'p', 'l', 'o'], ['_', 'r', 'a', 'y'], ['d', 'l', 'e', 'r']]

A* algorithm generated by GPT4 for the problem above using A*  approach that passed the unit tests:[language=Python]
import heapq

def initialize():
# Define the initial state of the board as a 2d tuple
initial_state = (('i', 'c', 'a', 'm'), ('h', 'p', 'l', 'o'), ('_', 'r', 'a', 'y'), ('d', 'l', 'e', 'r'))
num_rows = 4
num_cols = 4
# Define the goal state of the board as a 2d tuple
goal_state = (('_', 'c', 'a', 'm'), ('h', 'i', 'l', 'l'), ('p', 'r', 'a', 'y'), ('d', 'o', 'e', 'r'))
visited_costs =
visited_costs[initial_state] = 0
queue = [(0, 0, [], initial_state)]
return initial_state, num_rows, num_cols, goal_state, visited_costs, queue

def a_star():
initial_state, num_rows, num_cols, goal_state, visited_costs, queue = initialize()
while queue:
_, g, actions, state = heapq.heappop(queue)
# If the current state is the goal state, return the actions taken
if state == goal_state:
return actions
# Generate all possible actions from the current state, which includes swapping the blank space with any of its 4 diagonal neighbors
for d_row, d_col in [(-1, 1), (1, 1), (-1, -1), (1, -1)]:
# Get the coordinate of the blank space
blank_coord = [(i, j) for i, row in enumerate(state) for j, element in enumerate(row) if element == '_'][0]
new_row, new_col = blank_coord[0] + d_row, blank_coord[1] + d_col
# Check if the new coordinate is valid, ie if the new position is within the bounds of the board
if 0 <= new_row < num_rows and 0 <= new_col < num_cols:
# Generate the new state
new_state = [list(row[:]) for row in state]
new_state[blank_coord[0]][blank_coord[1]], new_state[new_row][new_col] = new_state[new_row][new_col], new_state[blank_coord[0]][blank_coord[1]]
new_state = tuple(tuple(row) for row in new_state)
# The cost so far is the number of actions taken, as the task is to minimize the number of actions required to sort the board
new_cost = g + 1
if new_state not in visited_costs or new_cost < visited_costs[new_state]:
visited_costs[new_state] = new_cost
# The direction of the swap action is the direction in which the blank space was moved
if d_row == -1 and d_col == 1:
action = 'up-right'
elif d_row == 1 and d_col == 1:
action = 'down-right'
elif d_row == -1 and d_col == -1:
action = 'up-left'
elif d_row == 1 and d_col == -1:
action = 'down-left'
heapq.heappush(queue, (g + heuristic(new_state, goal_state), new_cost, actions + [action], new_state))
return None

*The GPT4's implementation of the A* algorithm continues on the next page.

Continuation of GPT-4's implementation: [language=Python]
def heuristic(state, goal):
# An admissible and consistent heuristic for this problem is the count of tiles that are not in their goal position
# This heuristic relaxes the constraint that only the blank space can be moved, and only to a diagonal position
# It is admissible because it never overestimates the cost to reach the goal, as each misplaced tile must be moved at least once
# It's consistent because moving a tile reduces the heuristic cost of the successor node by a max of 1 (if the moved tile is placed in its goal position), which is equal to the cost of reaching the successor node
# Thus h(n) is always less than or equal to c(n, n')(equal to 1) + h(n')
# And the cost of the goal state is 0, as all tiles will be in their goal position
h = 0
for i in range(len(state)):
for j in range(len(state[0])):
if state[i][j] != goal[i][j]:
h += 1
return h

The A* algorithm was generated by GPT4 using the MSMT A* approach. For 8_puzzle_words problem type, GPT4's A* implementation for the first instance passed the unit tests.

8_puzzle_words instance (diff_sorted_id: 93): In the game 'Sort the Chars', we are given a table of n by m dimensions. This table contains n words, each with m characters, except for the first word which has m - 1 characters. Each character is written on a separate tile. The objective of the game is to rearrange the characters such that row i spells the i-th word in the list, with the blank tile ('_') placed in the top left corner of the board in the end. We can rearrange the tiles by swapping the blank space with any of its 4 diagonal neighboring tiles. Given the list of words and initial state of the board below, where the black space is represented as '_', what is the shortest list of swap actions (reported in python syntax) that can sort the board into the given list of target words? The list must only include the 4 diagonal swap directions: up-right, down-right, up-left, or down-left, representing the direction in ehich the blank space was swpped in. Target words: helen, adelea, bumble, iodism, trullo   The initial board: [['d', 'h', '_', 'l', 'e', 'n'], ['a', 'a', 'e', 'b', 'e', 'u'], ['m', 'u', 'i', 'b', 'e', 'e'], ['i', 'o', 'd', 'm', 's', 'l'], ['t', 'r', 'l', 'l', 'l', 'o']]

'initialize' function generated by GPT4 for the problem above in the second stage of the MSMT approach[language=Python]
def initialize():
# Define the initial state of the board as a 2d tuple
initial_state = (('d', 'h', '_', 'l', 'e', 'n'),
('a', 'a', 'e', 'b', 'e', 'u'),
('m', 'u', 'i', 'b', 'e', 'e'),
('i', 'o', 'd', 'm', 's', 'l'),
('t', 'r', 'l', 'l', 'l', 'o'))
num_rows = 5
num_cols = 6
# Define the goal state of the board as a 2d tuple
goal_state = (('_', 'h', 'e', 'l', 'e', 'n'),
('a', 'd', 'e', 'l', 'e', 'a'),
('b', 'u', 'm', 'b', 'l', 'e'),
('i', 'o', 'd', 'i', 's', 'm'),
('t', 'r', 'u', 'l', 'l', 'o'))
visited_costs =
visited_costs[initial_state] = 0
queue = [(0, 0, [], initial_state)]
return initial_state, num_rows, num_cols, goal_state, visited_costs, queue

GPT4 was only successful in generating an optimal solution for this instance using the MSMT A* approach. The other four code and text-based prompting methods used in our experiments resulted in infeasible solutions.

Coin Exchange

coin_exchange instance (diff_sorted_id: 1): In the 'taxed coin exchange' problem, you are required to choose a subset of coins from this list [14, 2, 5, 8, 65, 5, 16, 2, 5, 2, 12, 17, 16, 15, 20, 4, 19, 9, 10, 64, 2, 10, 14, 2, 17], such that the sum of the chosen coins adds up to 208. Each coin in the list is unique and can only be used once. Also coins carry a tax value. The tax values for each coin is 20: 13, 4: 2, 17: 16, 19: 8, 64: 4, 5: 3, 14: 10, 10: 9, 65: 11, 16: 2, 12: 7, 8: 5, 2: 2, 15: 14, 9: 8, where the tax for coins of the same value is the same. Also, if the coin chosen is smaller than the previous one, it must have an even value, otherwise, if the coin is larger than or equal to the previous coin chosen, it must have an odd value. The objective is to determine which subset of coins should be selected to minimize the total tax paid. The solution should be presented as a list of numbers, representing the value of the coins chosen in order, with the first coins chosen being in index 0, formatted in Python syntax.

A* algorithm generated by GPT4 for the problem above using A*  approach that passed the unit tests:[language=Python]
import heapq

def initialize():
# Define the initial state of the problem, which includes the coins available, the sum of the coins chosen so far, the tax paid so far, and the value of the last coin chosen
initial_state = ((14, 2, 5, 8, 65, 5, 16, 2, 5, 2, 12, 17, 16, 15, 20, 4, 19, 9, 10, 64, 2, 10, 14, 2, 17), 0, 0, 0)
goal_sum = 208
tax_values = 20: 13, 4: 2, 17: 16, 19: 8, 64: 4, 5: 3, 14: 10, 10: 9, 65: 11, 16: 2, 12: 7, 8: 5, 2: 2, 15: 14, 9: 8
visited_costs =
visited_costs[initial_state] = 0
queue = [(0, 0, [], initial_state)]
return initial_state, goal_sum, tax_values, visited_costs, queue

def a_star():
initial_state, goal_sum, tax_values, visited_costs, queue = initialize()
while queue:
_, g, actions, state = heapq.heappop(queue)
# Unpack the information encoded in each state
coins, sum_coins, tax_paid, last_coin = state
# If the sum of the coins chosen so far equals the goal sum, return the coins chosen
if sum_coins == goal_sum:
return actions
# If the sum of the coins chosen so far is less than the goal sum, generate all possible actions from the current state, which includes choosing any of the remaining coins
elif sum_coins < goal_sum:
for coin in coins:
# Check if the new state, containing the new coin, would be valid; ie the coin must be even if it is smaller than the last coin chosen, and odd if it is larger than or equal to the last coin chosen
if (coin < last_coin and coin
# Generate the new state
new_state = (tuple(c for c in coins if c != coin), sum_coins + coin, tax_paid + tax_values[coin], coin)
# The additional cost of this state is the tax paid for the new coin as we are trying to minimize the total tax paid
new_cost = g + tax_values[coin]
if new_state not in visited_costs or new_cost < visited_costs[new_state]:
visited_costs[new_state] = new_cost
# The new coin must be added to the actions
heapq.heappush(queue, (g + heuristic(new_state, goal_sum), new_cost, actions + [coin], new_state))
return None

*The GPT4's implementation of the A* algorithm continues on the next page.

Continuation of GPT-4's implementation: [language=Python]
def heuristic(state, goal_sum):
# An admissible and consistent heuristic for this problem is the difference between the goal sum and the sum of the coins chosen so far
# The heuristic assumes we can reach the goal sum without paying any additional tax, thus reporting a lower cost estimate to reach the goal state, making it admissible
# The heuristic is consistent, ie non-decreasing along the path to the goal state, because the cost of choosing a coin is the tax paid for that coin, which is always greater than or equal to 0, the decrease in the difference between the goal sum and the sum of the coins chosen so far
# Also the cost of the goal state is 0, as the sum of the coins chosen equals the goal sum and there are no more coins to choose

return goal_sum - state[1]

The A* algorithm was generated by GPT4 using the MSMT A* approach. For coin_exchange problem type, GPT4's A* implementation for the first instance passed the unit tests.

coin_exchange instance (diff_sorted_id: 104): In the 'taxed coin exchange' problem, you are required to choose a subset of coins from this list [18, 23, 23, 36, 27, 10, 25, 14, 6, 43, 6, 31, 5, 43, 3, 13, 16, 8, 11, 6, 39, 44, 41, 28, 12, 8, 1, 14, 22, 23, 11, 24, 37, 9, 2, 31, 27, 10, 9, 38, 37, 4, 4, 17, 18, 36, 18, 32, 3, 12, 4, 42, 8, 4, 4, 16, 30, 40, 13, 41], such that the sum of the chosen coins adds up to 441. Each coin in the list is unique and can only be used once. Also coins carry a tax value. The tax values for each coin is 6: 4, 18: 3, 38: 1, 23: 2, 16: 8, 12: 2, 4: 2, 24: 13, 28: 17, 30: 17, 1: 1, 9: 9, 27: 8, 11: 4, 37: 16, 41: 19, 13: 3, 31: 8, 44: 8, 22: 7, 43: 13, 10: 3, 17: 8, 36: 7, 39: 3, 25: 17, 40: 10, 8: 6, 32: 16, 14: 4, 2: 1, 42: 3, 3: 2, 5: 2, where the tax for coins of the same value is the same. Also, if the coin chosen is smaller than the previous one, it must have an even value, otherwise, if the coin is larger than or equal to the previous coin chosen, it must have an odd value. The objective is to determine which subset of coins should be selected to minimize the total tax paid. The solution should be presented as a list of numbers, representing the value of the coins chosen in order, with the first coins chosen being in index 0, formatted in Python syntax.

'initialize' function generated by GPT4 for the problem above in the second stage of the MSMT approach[language=Python]
def initialize():
def initialize():
# Define the initial state of the problem, which includes the coins available, the sum of the coins chosen so far, the tax paid so far, and the value of the last coin chosen
initial_state = ((18, 23, 23, 36, 27, 10, 25, 14, 6, 43, 6, 31, 5, 43, 3, 13, 16, 8, 11, 6, 39, 44, 41, 28, 12, 8, 1, 14, 22, 23, 11, 24, 37, 9, 2, 31, 27, 10, 9, 38, 37, 4, 4, 17, 18, 36, 18, 32, 3, 12, 4, 42, 8, 4, 4, 16, 30, 40, 13, 41), 0, 0, 0)
goal_sum = 441
tax_values = 6: 4, 18: 3, 38: 1, 23: 2, 16: 8, 12: 2, 4: 2, 24: 13, 28: 17, 30: 17, 1: 1, 9: 9, 27: 8, 11: 4, 37: 16, 41: 19, 13: 3, 31: 8, 44: 8, 22: 7, 43: 13, 10: 3, 17: 8, 36: 7, 39: 3, 25: 17, 40: 10, 8: 6, 32: 16, 14: 4, 2: 1, 42: 3, 3: 2, 5: 2
visited_costs =
visited_costs[initial_state] = 0
queue = [(0, 0, [], initial_state)]
return initial_state, goal_sum, tax_values, visited_costs, queue

GPT4 was only successful in generating a correct (but non-optimal) solution for this instance of the coin_exchange problem type using the MSMT A* approach. The other four code and text-based prompting methods used in our experiments resulted in infeasible solutions.

Water Jug

water_jug instance (diff_sorted_id: 1): In the 'taxed coin exchange' problem, you are required to choose a subset of coins from this list [14, 2, 5, 8, 65, 5, 16, 2, 5, 2, 12, 17, 16, 15, 20, 4, 19, 9, 10, 64, 2, 10, 14, 2, 17], such that the sum of the chosen coins adds up to 208. Each coin in the list is unique and can only be used once. Also coins carry a tax value. The tax values for each coin is 20: 13, 4: 2, 17: 16, 19: 8, 64: 4, 5: 3, 14: 10, 10: 9, 65: 11, 16: 2, 12: 7, 8: 5, 2: 2, 15: 14, 9: 8, where the tax for coins of the same value is the same. Also, if the coin chosen is smaller than the previous one, it must have an even value, otherwise, if the coin is larger than or equal to the previous coin chosen, it must have an odd value. The objective is to determine which subset of coins should be selected to minimize the total tax paid. The solution should be presented as a list of numbers, representing the value of the coins chosen in order, with the first coins chosen being in index 0, formatted in Python syntax.

A* algorithm generated by GPT4 for the problem above using A*  approach that passed the unit tests:[language=Python]
import heapq

def initialize():
# Define the initial state of the buckets as a tuple
initial_state = (0, 0, 0)
# Define the goal state of the buckets as a tuple
goal_state = (274, 297, 343)
# Define the capacities of the jugs as a list
jug_capacities = [41, 26, 44, 75, 40, 136]
# Initialize a dictionary to store the cost of reaching each visited state
visited_costs =
visited_costs[initial_state] = 0
# Initialize a priority queue of states not yet visited, with the initial state as the first element. The priority of each element is the cost to reach that state (g) + the estimate remaining cost (h) to reach the goal
# Record the actions required to get to each state in a list; no actions performed to reach the initial state
queue = [(0, 0, [], initial_state)]
return initial_state, goal_state, jug_capacities, visited_costs, queue

def a_star():
# The initialize function initializes and returns the visited_costs dictionary and the priority queue and encodes all of the variables given in the problem (ie the initial and goal state of the buckets and the capacities of the jugs)
initial_state, goal_state, jug_capacities, visited_costs, queue = initialize()
# While there are un-visited states
while queue:
# Pop the state with the lowest sum of the cost so far and estimated cost to the goal from the queue
_, g, actions, state = heapq.heappop(queue)
# We can check if the current state is the goal state with a simple equality check, as the goal state is predefined
if state == goal_state:
return actions
# Generate all possible actions from the current state, which includes filling each of the 3 buckets with each of the 6 jugs, and emptying each of the 3 buckets with each of the 6 jugs
for i in range(len(jug_capacities)):
for j in range(len(state)):
# Check if the new state would be valid, ie if the bucket can be filled with the jug without overflowing and if the amount of water in each bucket does not exceed the amount of water in the bucket placed after it
if state[j] + jug_capacities[i] <= goal_state[j] and (j == len(state) - 1 or state[j] + jug_capacities[i] <= state[j + 1]):
# The action is valid, generate the new state
new_state = list(state)
new_state[j] += jug_capacities[i]
new_state = tuple(new_state)
# The cost so far is the number of actions performed, as our objective is to minimize the number of actions required to reach the goal state
new_cost = g + 1
# If the new state is unvisited or we found a new path with a lower cost to reach this state, add it to the queue of not-yet-visited states
if new_state not in visited_costs or new_cost < visited_costs[new_state]:
visited_costs[new_state] = new_cost
heapq.heappush(queue, (g + heuristic(new_state, goal_state), new_cost, actions + [('+', jug_capacities[i], j + 1)], new_state))

*The GPT4's implementation of the A* algorithm continues on the next page.

7.5pt8.5ptContinuation of GPT-4's implementation:
# Similarly, check if the new state would be valid, ie if the bucket can be emptied with the jug and if the amount of water in each bucket does not exceed the amount of water in the bucket placed after it
if state[j] - jug_capacities[i] >= 0 and (j == 0 or state[j] - jug_capacities[i] >= state[j - 1]):
# The action is valid, generate the new state
new_state = list(state)
new_state[j] -= jug_capacities[i]
new_state = tuple(new_state)
# The cost so far is the number of actions performed, as our objective is to minimize the number of actions required to reach the goal state
new_cost = g + 1
# If the new state is unvisited or we found a new path with a lower cost to reach this state, add it to the queue of not-yet-visited states
if new_state not in visited_costs or new_cost < visited_costs[new_state]:
visited_costs[new_state] = new_cost
heapq.heappush(queue, (g + heuristic(new_state, goal_state), new_cost, actions + [('-', jug_capacities[i], j + 1)], new_state))
return None

def heuristic(state, goal):
# An admissible and consistent heuristic is the sum of the differences between the current and goal amount of water in each bucket
# The heuristic relaxes the constraint that the amount of water in each bucket can not at any point in time exceed the amount of water in the bucket placed after it and presumes we can fill or empty the buckets directly to their goal amount
# Thus the heuristic reports a lower estimate on the cost to reach goal state and is admissible
# The heuristic is consistent because the cost of filling or emptying a bucket is always 1, which is exactly the decrease or increase in the difference between the current and goal amount of water in the bucket, if the bucket is filled or emptied, respectively, otherwise the estimated cost of the successor node is the same or higher, and the heuristic estimate for the goal state is 0, as the difference between the current and goal amount of water in each bucket would be 0 in the goal state.
return sum(abs(a - b) for a, b in zip(state, goal))

7.5pt9ptThe A* algorithm was generated by GPT4 using the MSMT A* approach. GPT4's first A* implementation for the water_jug problem type passed the unit tests.

8.2pt9.1ptwater_jug instance (diff_sorted_id: 100): Given 9 labeled water jugs with capacities 126, 120, 127, 110, 54, 39, 38, 47, 139, 99 liters, we aim to fill 4 unlabeled buckets, numbered 1 to 4 and arranged in a line in ascending order, with 219, 240, 312, 411 liters of water respectively. The amount of water in each unlabeled bucket can not at any point in time exceed the amount of water in the bucket placed after it. Jugs can only be filled to the top and emptied completely, and the unlabeled buckets cannot be overfilled. An action, represented as a tuple ('+', X, Y) or ('-', X, Y), involves adding to or removing water from the unlabeled bucket numbered Y, using the jug with capacity X. Determine the shortest sequence of actions needed to fill the buckets as specified, and present the solution as a list of action tuples in Python syntax.

8pt8.5pt'initialize' function generated by GPT4 for the problem above in the second stage of the MSMT approach[language=Python]
def initialize():
# Define the initial state of the buckets as a tuple
initial_state = (0, 0, 0, 0)
# Define the goal state of the buckets as a tuple
goal_state = (219, 240, 312, 411)
# Define the capacities of the jugs as a list
jug_capacities = [126, 120, 127, 110, 54, 39, 38, 47, 139, 99]
# Initialize a dictionary to store the cost of reaching each visited state
visited_costs =
visited_costs[initial_state] = 0
# Initialize a priority queue of states not yet visited, with the initial state as the first element. The priority of each element is the cost to reach that state (g) + the estimate remaining cost (h) to reach the goal
# Record the actions required to get to each state in a list; no actions performed to reach the initial state
queue = [(0, 0, [], initial_state)]
return initial_state, goal_state, jug_capacities, visited_costs, queue

7.5pt9ptGPT4 successfully generated a correct (but non-optimal) solution for this water_jug problem instance using the MSMT A* and A* prompting approach. The other three baseline code and text-based prompting methods resulted in infeasible solutions.

Restricted Sorting

restricted_sorting instance (diff_sorted_id: 3): In 'Restricted Sorting', there are 6 stacks each with a capacity of 4 blocks, with 3 stacks filled with blocks of varying shades and the remaining are empty. The challenge is to sort the blocks by shade such that if a stack is not empty, it is stacked with 3 blocks of a single shade. The player can only transfer one block at a time from the top of a stack to an empty stack or to a stack that has only blocks of that shade, without exceeding the stacks’ capacity. Transferring blocks to certain stacks is more expensive than others. The cost of moving one block to the top of each stack is: 0: 3, 1: 6, 2: 5, 3: 6, 4: 1, 5: 1, where the keys are the index of each stack, indexing from 0. The cost of moving a block is always at least 1. The solution should be a list of tuples, each containing, first, the index of the stack from which a block is picked up from and, second, the index of the stack to which it is transferred, indexing from 0. Given the initial state of the stacks, represented by the lists below (with the leftmost item being the shade of the topmost block in each stack)(and the first stack being the stack at index 0), what is the list of transfer pairs (reported in python syntax) with the least possible cost, that will result in all the blocks being correctly sorted? [[], ['Yellow', 'Green', 'Red', 'Red'], ['Blue', 'Green', 'Red', 'Green'], ['Yellow', 'Blue', 'Yellow', 'Blue'], [], []]

A* algorithm generated by GPT4 for the problem above using A*  approach that passed the unit tests:[language=Python]
import heapq

def initialize():
# Define the initial state of the stacks as a tuple of tuples
initial_state = ((), ('Yellow', 'Green', 'Red', 'Red'), ('Blue', 'Green', 'Red', 'Green'), ('Yellow', 'Blue', 'Yellow', 'Blue'), (), ())
num_stacks = 6
stack_capacity = 4
# Define the cost of moving a block to each stack
stack_costs = 0: 3, 1: 6, 2: 5, 3: 6, 4: 1, 5: 1
visited_costs =
visited_costs[initial_state] = 0
queue = [(0, 0, [], initial_state)]
return initial_state, num_stacks, stack_capacity, stack_costs, visited_costs, queue

def a_star():
initial_state, num_stacks, stack_capacity, stack_costs, visited_costs, queue = initialize()
while queue:
_, g, actions, state = heapq.heappop(queue)
# If all the stacks are empty or contain blocks of a single shade, return the actions taken
if all(len(stack) == 0 or len(set(stack)) == 1 for stack in state):
return actions
# Generate all possible actions from the current state, which includes moving the top block from any stack to any other stack
for from_stack_ind in range(num_stacks):
# Check if the stack has any blocks to move
if state[from_stack_ind]:
for to_stack_ind in range(num_stacks):
# Check if the stack can accept more blocks and if the block can be moved to the stack
if (len(state[to_stack_ind]) < stack_capacity and
(not state[to_stack_ind] or state[to_stack_ind][-1] == state[from_stack_ind][-1])):
# Generate the new state
new_state = list(list(stack) for stack in state)
block = new_state[from_stack_ind].pop()
new_state = tuple(tuple(stack) for stack in new_state)
# The cost of the new state is the cost of moving a block to the stack
new_cost = g + stack_costs[to_stack_ind]
if new_state not in visited_costs or new_cost < visited_costs[new_state]:
visited_costs[new_state] = new_cost
h = heuristic(new_state)
heapq.heappush(queue, (new_cost + h, new_cost, actions + [(from_stack_ind, to_stack_ind)], new_state))
return None

*The GPT4's implementation of the A* algorithm continues on the next page.

Continuation of GPT-4's implementation: [language=Python]
def heuristic(state):
# The heuristic function can be the sum of the number of blocks in each stack that are not of the same shade as the top block
# This heuristic is admissible because it presumes we can move the blocks to any stack, even if the stack is full or contains blocks of a different shade, thus reporting a lower cost estimate to reach the goal state
# The heuristic is consistent, ie non-decreasing along the path to the goal state, because the cost of moving a block from one stack to another is always at least 1, which is exactly the decrease in the heuristic value, if the block is moved to a stack with blocks of the same shade, otherwise the heuristic value of the successor node is the same or higher, and the heuristic estimate for the goal state is 0, as all the blocks in each stack are of the same shade in the goal state
h = 0
for stack in state:
if stack:
h += len([block for block in stack if block != stack[-1]])
return h

The A* algorithm was generated by GPT4 using the MSMT A* approach. GPT4's third A* implementation for the restricted_sorting problem type passed the unit tests.

restricted_sorting instance (diff_sorted_id: 57): In 'Restricted Sorting', there are 8 stacks each with a capacity of 5 blocks, with 4 stacks filled with blocks of varying shades and the remaining are empty. The challenge is to sort the blocks by shade such that if a stack is not empty, it is stacked with 4 blocks of a single shade. The player can only transfer one block at a time from the top of a stack to an empty stack or to a stack that has only blocks of that shade, without exceeding the stacks’ capacity. Transferring blocks to certain stacks is more expensive than others. The cost of moving one block to the top of each stack is: 0: 2, 1: 3, 2: 9, 3: 8, 4: 3, 5: 7, 6: 9, 7: 5, where the keys are the index of each stack, indexing from 0. The cost of moving a block is always at least 1. The solution should be a list of tuples, each containing, first, the index of the stack from which a block is picked up from and, second, the index of the stack to which it is transferred, indexing from 0. Given the initial state of the stacks, represented by the lists below (with the leftmost item being the shade of the topmost block in each stack)(and the first stack being the stack at index 0), what is the list of transfer pairs (reported in python syntax) with the least possible cost, that will result in all the blocks being correctly sorted? [[], [], ['Green', 'Red', 'Black', 'Blue', 'Blue'], ['Yellow', 'Blue', 'Blue', 'Green', 'Black'], ['Yellow', 'Yellow', 'Yellow', 'Red', 'Black'], [], [], ['Red', 'Green', 'Green', 'Red', 'Black']]

'initialize' function generated by GPT4 for the problem above in the second stage of the MSMT approach[language=Python]
def initialize():
# Define the initial state of the stacks as a tuple of tuples
initial_state = ((), (), ('Green', 'Red', 'Black', 'Blue', 'Blue'),
('Yellow', 'Blue', 'Blue', 'Green', 'Black'),
('Yellow', 'Yellow', 'Yellow', 'Red', 'Black'), (), (),
('Red', 'Green', 'Green', 'Red', 'Black'))
num_stacks = 8
stack_capacity = 5
# Define the cost of moving a block to each stack
stack_costs = 0: 2, 1: 3, 2: 9, 3: 8, 4: 3, 5: 7, 6: 9, 7: 5
visited_costs =
visited_costs[initial_state] = 0
queue = [(0, 0, [], initial_state)]
return initial_state, num_stacks, stack_capacity, stack_costs, visited_costs, queue

GPT4 successfully generated a feasible (but not correct) solution for this restricted_sorting problem instance using the MSMT A* and A* prompting approach. The other three baseline code and text-based prompting methods resulted in infeasible solutions.

Color Sorting

color_sorting instance (diff_sorted_id: 1): The game of 'Sort It' begins with 3 tubes, each filled with 4 balls of different colors. The goal is to sort the balls by color, with each tube containing balls of only one color. Only one ball can be moved at a time, taken from the top of one tube and placed on top of another. The capacity of each tube (maximum number of balls we can fit in each tube) is 6 balls. It is not allowed to place a ball in a tube that already has 6 balls. The solution should be a list of tuples, each containing, first, the index of the tube from which a ball is taken and, second, the index of the tube to which it is moved, indexing from 0. Given the initial state of the tubes, represented by the lists below (with the leftmost item being the color of the topmost ball in each tube), what is the shortest list of move tuples that will result in all the balls being correctly sorted? [['Green', 'Red', 'Green', 'Red'], ['Blue', 'Blue', 'Red', 'Green'], ['Red', 'Blue', 'Green', 'Blue']]

A* algorithm generated by GPT4 for the problem above using A*  approach that passed the unit tests:[language=Python]
import heapq

def initialize():
# Define the initial state and the goal state of the tubes, represented as 3x4 tuples
initial_state = (('Green', 'Red', 'Green', 'Red'), ('Blue', 'Blue', 'Red', 'Green'), ('Red', 'Blue', 'Green', 'Blue'))
goal_state = (('Red', 'Red', 'Red', 'Red'), ('Green', 'Green', 'Green', 'Green'), ('Blue', 'Blue', 'Blue', 'Blue'))
# Encoding other variables given in the problem statement
num_tubes = 3
tube_capacity = 6
# Initialize a dictionary to store the cost of reaching each visited state
visited_costs =
visited_costs[initial_state] = 0
# Initialize a priority queue of states not yet visited, with the initial state as the first element. The priority of each element is the cost to reach that state (g) + the estimate remaining cost (h) to reach the goal
# Record the moves required to get to each state in a list; no moves performed to reach the initial state
queue = [(0, 0, [], initial_state)]
return initial_state, goal_state, num_tubes, tube_capacity, visited_costs, queue

def a_star():
# The initialize function initializes and returns the visited_costs dictionary and the priority queue and encodes all of the variables given in the problem (ie the initial and goal state of the tubes and the tube capacity)
initial_state, goal_state, num_tubes, tube_capacity, visited_costs, queue = initialize()
# While there are un-visited states
while queue:
# Pop the state with the lowest sum of the cost so far and estimated cost to the goal from the queue
_, g, actions, state = heapq.heappop(queue)
# We can check if the current state is the goal state with a simple equality check, as the goal state is predefined
if state == goal_state:
return actions
# Generate all valid actions from the current state, which includes moving the top ball from any tube to the top of any other tube
for from_tube in range(num_tubes):
for to_tube in range(num_tubes):
# Check if the move is valid, ie if the from_tube is not empty and the to_tube is not full
if state[from_tube] and len(state[to_tube]) < tube_capacity:
# The action is valid, generate the new state
new_state = [list(tube[:]) for tube in state]
ball_to_be_moved = new_state[from_tube].pop(0)
# Do the move
new_state[to_tube].insert(0, ball_to_be_moved)
new_state = tuple(tuple(tube) for tube in new_state)
# The cost so far is the number of moves made, as our objective is to minimize the number of moves required to reach the goal state
new_cost = g + 1
# If the new state is unvisited or we found a new path with a lower cost to reach this state, add it to the queue of not-yet-visited states
if new_state not in visited_costs or new_cost < visited_costs[new_state]:
visited_costs[new_state] = new_cost
heapq.heappush(queue, (g + heuristic(new_state, goal_state), new_cost, actions + [(from_tube, to_tube)], new_state))
return None

*The GPT4's implementation of the A* algorithm continues on the next page.

Continuation of GPT-4's implementation: [language=Python]
def heuristic(state, goal):
# An admissible and consistent heuristic is the sum of the number of misplaced balls in each tube
# The heuristic relaxes the constraint that a ball can only be moved from the top of a tube and presumes we can move the balls to their goal position by taking them from any position in the tube
# Thus the heuristic reports a lower estimate on the cost to reach goal state and is admissible
# The heuristic is consistent because the cost of moving a ball to a neighboring tube is always 1, which is exactly the decrease in the number of misplaced balls, if the ball is moved toward its goal position, otherwise the estimated cost of the successor node is the same or higher, and the heuristic estimate for the goal state is 0, as the number of misplaced balls would be 0 in the goal state.
h = 0
for i in range(len(state)):
for j in range(len(state[i])):
# Can't compare integers with "_" when finding the goal position of each ball, thus ignore the "_" ball
if state[i][j] != '_':
# Add the the number of misplaced balls in each tube to the estimate
h += sum(1 for ball in state[i] if ball != goal[i][0])
return h

The A* algorithm was generated by GPT4 using the MSMT A* approach. GPT4's A* implementation for the first instance of the color_sorting problem type passed the unit tests.

color_sorting instance (diff_sorted_id: 97): The game of 'Sort It' begins with 3 tubes, each filled with 6 balls of different colors. The goal is to sort the balls by color, with each tube containing balls of only one color. Only one ball can be moved at a time, taken from the top of one tube and placed on top of another. The capacity of each tube (maximum number of balls we can fit in each tube) is 9 balls. It is not allowed to place a ball in a tube that already has 9 balls. The solution should be a list of tuples, each containing, first, the index of the tube from which a ball is taken and, second, the index of the tube to which it is moved, indexing from 0. Given the initial state of the tubes, represented by the lists below (with the leftmost item being the color of the topmost ball in each tube), what is the shortest list of move tuples that will result in all the balls being correctly sorted? [['Red', 'Red', 'Blue', 'Red', 'Blue', 'Green'], ['Red', 'Green', 'Blue', 'Blue', 'Green', 'Red'], ['Blue', 'Green', 'Green', 'Red', 'Blue', 'Green']]

'initialize' function generated by GPT4 for the problem above in the second stage of the MSMT approach[language=Python]
def initialize():
# Define the initial state and the goal state of the tubes, represented as 3x6 tuples
initial_state = (('Red', 'Red', 'Blue', 'Red', 'Blue', 'Green'),
('Red', 'Green', 'Blue', 'Blue', 'Green', 'Red'),
('Blue', 'Green', 'Green', 'Red', 'Blue', 'Green'))
goal_state = (('Red', 'Red', 'Red', 'Red', 'Red', 'Red'),
('Green', 'Green', 'Green', 'Green', 'Green', 'Green'),
('Blue', 'Blue', 'Blue', 'Blue', 'Blue', 'Blue'))
# Encoding other variables given in the problem statement
num_tubes = 3
tube_capacity = 9
# Initialize a dictionary to store the cost of reaching each visited state
visited_costs =
visited_costs[initial_state] = 0
# Initialize a priority queue of states not yet visited, with the initial state as the first element. The priority of each element is the cost to reach that state (g) + the estimate remaining cost (h) to reach the goal
# Record the moves required to get to each state in a list; no moves performed to reach the initial state
queue = [(0, 0, [], initial_state)]
return initial_state, goal_state, num_tubes, tube_capacity, visited_costs, queue

GPT4 successfully generated a correct (but non-optimal) solution for this color_sorting problem instance using MSMT A* approach. Prompting GPT4 with all other four code and text-based prompting methods resulted in infeasible solutions.

Magic Square

magic_square instance (diff_sorted_id: 1): The game of 'Sort It' begins with 3 tubes, each filled with 4 balls of different colors. The goal is to sort the balls by color, with each tube containing balls of only one color. Only one ball can be moved at a time, taken from the top of one tube and placed on top of another. The capacity of each tube (maximum number of balls we can fit in each tube) is 6 balls. It is not allowed to place a ball in a tube that already has 6 balls. The solution should be a list of tuples, each containing, first, the index of the tube from which a ball is taken and, second, the index of the tube to which it is moved, indexing from 0. Given the initial state of the tubes, represented by the lists below (with the leftmost item being the color of the topmost ball in each tube), what is the shortest list of move tuples that will result in all the balls being correctly sorted? [['Green', 'Red', 'Green', 'Red'], ['Blue', 'Blue', 'Red', 'Green'], ['Red', 'Blue', 'Green', 'Blue']]

A* algorithm generated by GPT4 for the problem above using A*  approach that passed the unit tests:[language=Python]
import heapq

def initialize():
# Define the initial state of the grid, the goal sums of the specified row, column, and diagonal, and the range of unique integers that can be used to replace 'x's
initial_state = (('35', 'x', '46'), ('x', 'x', 'x'), ('x', 'x', 'x'))
goal_sums = 'row1': 103, 'col1': 107, 'diag': 124
num_range = set(range(29, 49))
# Initialize a dictionary to store the cost of reaching each visited state
visited_costs =
visited_costs[initial_state] = 0
# Initialize a priority queue of states not yet visited, with the initial state as the first element. The priority of each element is the cost to reach that state (g) + the estimate remaining cost (h) to reach the goal
# Record the actions required to get to each state in a list; no actions performed to reach the initial state
queue = [(0, 0, [], initial_state)]
return initial_state, goal_sums, num_range, visited_costs, queue

def a_star():
# The initialize function initializes and returns the visited_costs dictionary and the priority queue and encodes all of the variables given in the problem (ie the initial state of the grid, the goal sums, and the range of unique integers)
initial_state, goal_sums, num_range, visited_costs, queue = initialize()
# While there are un-visited states
while queue:
# Pop the state with the lowest sum of the cost so far and estimated cost to the goal from the queue
_, g, actions, state = heapq.heappop(queue)
# Check if the current state is the goal state
# The goal state is where the sum of the specified row, column, and diagonal equal the goal sums, and there are no 'x's in the grid
if all(cell != 'x' for row in state for cell in row) and sum(int(cell) for cell in state[1]) == goal_sums['row1'] and sum(int(state[i][1]) for i in range(3)) == goal_sums['col1'] and sum(int(state[i][2-i]) for i in range(3)) == goal_sums['diag']:
return actions
# If the state has at least 1 remaining unknown number, ie 'x', generate all possible actions from the current state, which includes replacing the next x in the grid with any of avaiable unique integers (all numbers in the range - numbers present in the current state) in the range
if any(cell == 'x' for row in state for cell in row):
# Find the next 'x' in the grid
for i in range(3):
for j in range(3):
if state[i][j] == 'x':
# Generate the set of available numbers by subtracting the set of numbers present in the current state from the set of all numbers in the range
available_nums = num_range - set(int(cell) for row in state for cell in row if cell != 'x')
for num in available_nums:
# Generate the new state
new_state = [list(row) for row in state]
new_state[i][j] = str(num)
new_state = tuple(tuple(row) for row in new_state)
# The cost so far is the sum of the numbers in the grid, as the task is to minimize the sum of all of the numbers in the grid
new_cost = g + num
# If the new state is unvisited or we found a new path with a lower cost to arrive at this state, add it to the queue of un-visited states

*The GPT4's implementation of the A* algorithm continues on the next page.

7.5pt8ptContinuation of GPT-4's implementation:
if new_state not in visited_costs or new_cost < visited_costs[new_state]:
visited_costs[new_state] = new_cost
heapq.heappush(queue, (new_cost + heuristic(new_state, goal_sums), new_cost, actions + [(i, j, num)], new_state))
# Stop searching for 'x's after the first 'x' is found and all possible actions from it are generated
return None

def heuristic(state, goal_sums):
# An admissible and consistent heuristic for this problem is the sum of the absolute differences between the current sums and the goal sums of the specified row, column, and diagonal
# The heuristic relaxes the constraints that each number in the grid must be unique and that the sum of all of the numbers in the grid must be minimized; ie It presumes we can add or subtract any amount to the current sums to reach the goal sums
# Thus the heuristic reports a lower estimate on the cost of reaching the goal state and is admissible
# The heuristic is consistent because the estimated cost from the current state to the goal can never be greater than the sum of cost from the current node to a successor node plus the estimated cost from the successor node to the goal because the cost of reaching a successor node is the number added to the grid, which is always greater than or equal to 1, the decrease in the absolute difference between the current and goal sums
h = 0
if any(cell == 'x' for row in state for cell in row):
h += abs(sum(int(cell) for cell in state[1] if cell != 'x') - goal_sums['row1'])
h += abs(sum(int(state[i][1]) for i in range(3) if state[i][1] != 'x') - goal_sums['col1'])
h += abs(sum(int(state[i][2-i]) for i in range(3) if state[i][2-i] != 'x') - goal_sums['diag'])
return h

8pt8ptThe A* algorithm was generated by GPT4 using the MSMT A* approach. GPT4's first attempt at implementing the A* algorithm for the first instance of the magic_square problem type passed the unit tests.

8pt8.5ptmagic_square instance (diff_sorted_id: 34): In the magic square problem, a 3x3 grid is filled with unique integers ranging from 40 to 89. Some numbers are already given, while others are unknown and represented as 'x'. Sum of column 1 (counting from 0) must be 183, and sum of row 1 must be 194. Also, the sum of the numbers in the diagonal from the top right to the bottom left corner of the grid should equal 161. The goal is to find unique integers (ie each number can be in the final grid only once) in the given range to replace with ‘x’s in the grid below such that the sum of the specified rows, columns, and diagonal equals the given amounts and the sum of all of the numbers in the grid is as low as possible. The solution should be provided as a list of tuples in Python syntax. Each tuple should contain three numbers for each 'x' position: the row index, the column index (both starting from 0), and the value of the unique integer replaced with 'x' at that position.\n\nGrid:\n [['x' 'x' 'x']\n ['x' 'x' 'x']\n ['40' 'x' '71']]

8pt8.5pt'initialize' function generated by GPT4 for the problem above in the second stage of the MSMT approach[language=Python]
def initialize():
# Define the initial state of the grid, the goal sums of the specified row, column, and diagonal, and the range of unique integers that can be used to replace 'x's
initial_state = (('x', 'x', 'x'), ('x', 'x', 'x'), ('40', 'x', '71'))
goal_sums = 'row1': 194, 'col1': 183, 'diag': 161
num_range = set(range(40, 90))
# Initialize a dictionary to store the cost of reaching each visited state
visited_costs =
visited_costs[initial_state] = 0
# Initialize a priority queue of states not yet visited, with the initial state as the first element. The priority of each element is the cost to reach that state (g) + the estimate remaining cost (h) to reach the goal
# Record the actions required to get to each state in a list; no actions performed to reach the initial state
queue = [(0, 0, [], initial_state)]
return initial_state, goal_sums, num_range, visited_costs, queue

7.pt8ptGPT4 successfully generated a correct (but non-optimal) solution for this magic_square problem instance using MSMT A* approach. Prompting GPT4 with all other four code and text-based prompting methods resulted in infeasible solutions.

Consecutive Grid

8.4pt8.5ptconsecutive_grid instance (diff_sorted_id: 13): We have a 3x3 numerical grid, with numbers ranging from 21 to 59 (21 included in the range but 59 is not included). The numbers in each row and column must be strictly increasing or decreasing. This means that either first > second > third or first < second < third in each row and column. If a grid cell is marked with an 'x', the number in that position is hidden. The objective is to replace the 'x's with unique integers from the given range, ensuring that each number only appears once in the grid. The replacements must maintain the consecutive order in each row and column. Additionally, the sum of the numbers in the topmost row plus the numbers in the rightmost column plus the numbers in the diagonal connecting the top-left corner of the grid to its bottom-right corner should be minimized. The solution should be given as a list of tuples in Python syntax. Each tuple should represent the replacement of a number with an  'x' number and contain three elements: the row index of the 'x', the column index  of the 'x' (both starting from 0), and the value of the number that replaces the 'x'. The initial state of the grid is as follows: \n\nGrid:\n [['29' '45' 'x']\n ['x' 'x' 'x']\n ['x' '43' '34']]

7.5pt9ptA* algorithm generated by GPT4 for the problem above using A*  approach that passed the unit tests:[language=Python]
import heapq
import numpy as np

def initialize():
# Define the initial state of the grid, as a 2d tuple
initial_state = (('29', '45', 'x'), ('x', 'x', 'x'), ('x', '43', '34'))
# Define the range of numbers that can be used to replace 'x'
num_range = set(range(21, 59))
# Define the dimensions of the grid
num_rows = 3
num_cols = 3
# Initialize a dictionary to store the cost of reaching each visited state
visited_costs =
visited_costs[initial_state] = 0
# Initialize a priority queue of states not yet visited, with the initial state as the first element. The priority of each element is the cost to reach that state (g) + the estimate remaining cost (h) to reach the goal
# Record the actions required to get to each state in a list; no actions performed to reach the initial state
queue = [(0, 0, [], initial_state)]
return initial_state, num_range, num_rows, num_cols, visited_costs, queue

def a_star():
# The initialize function initializes and returns the visited_costs dictionary and the priority queue and encodes all of the variables given in the problem (ie the initial state of the grid, the range of numbers, and the dimensions of the grid)
initial_state, num_range, num_rows, num_cols, visited_costs, queue = initialize()
# While there are un-visited states
while queue:
# Pop the state with the lowest sum of the cost so far and estimated cost to the goal from the queue
_, g, actions, state = heapq.heappop(queue)
# If the current state does not have any 'x's, ie all the numbers have been filled in, and the numbers in each row and column are consecutive, return the actions taken to reach this state
if all(all(cell != 'x' for cell in row) for row in state) and all(all(int(row[i]) < int(row[i + 1]) for i in range(len(row) - 1)) or all(int(row[i]) > int(row[i + 1]) for i in range(len(row) - 1)) for row in state) and all(all(int(state[i][col]) < int(state[i + 1][col]) for i in range(len(state) - 1)) or all(int(state[i][col]) > int(state[i + 1][col]) for i in range(len(state) - 1)) for col in range(len(state[0]))):
return actions
# If the state has at least 1 remaining unknown number, ie 'x', generate all possible actions from the current state, which includes replacing the next x in the grid with any of avaiable unique integers (all numbers in the range - numbers present in the current state) in the range
if any('x' in row for row in state):
# Find the next 'x' in the grid
for row_ind in range(num_rows):
for col_ind in range(num_cols):
if state[row_ind][col_ind] == 'x':
# Generate all possible actions from the current state, which includes replacing the 'x' with any of the available unique integers in the range
for num in num_range - set(cell for row in state for cell in row if cell != 'x'):
# Generate the new state
new_state = [list(row[:]) for row in state]
new_state[row_ind][col_ind] = num
new_state = tuple(tuple(row) for row in new_state)
# The cost so far is the sum of the numbers in the topmost row, the rightmost column, and the diagonal from the top-left corner to the bottom-right corner of the grid

*7.5pt9ptThe GPT4's implementation of the A* algorithm continues on the next page.

7.5pt8.5ptContinuation of GPT-4's implementation: [language=Python]
new_cost = sum(int(cell) for cell in new_state[0] if cell != 'x') + sum(int(new_state[i][-1]) for i in range(num_rows) if new_state[i][-1] != 'x') + sum(int(new_state[i][i]) for i in range(num_rows) if new_state[i][i] != 'x')
# If the new state is unvisited or we found a new path with a lower cost to reach this state, add it to the queue of not-yet-visited states
if new_state not in visited_costs or new_cost < visited_costs[new_state]:
visited_costs[new_state] = new_cost
heapq.heappush(queue, (new_cost + heuristic(new_state), new_cost, actions + [(row_ind, col_ind, num)], new_state))
# Once we have generated all possible actions from the current state, break the loop
return None

def heuristic(state):
# An admissible and consistent heuristic for this problem is the sum of the minimum remaining numbers that can be used to replace the 'x's in the grid
# This heuristic is admissible because it never overestimates the cost to reach the goal, as the minimum remaining numbers are always less than or equal to the actual numbers that will replace the 'x's
# The heuristic is consistent because the estimated cost from the current state to the goal can never be greater than the sum of cost from the current node to a successor node plus the estimated cost from the successor node to the goal because the cost of replacing an 'x' with a number is the number itself, which is always greater than or equal to the minimum remaining number
return sum(sorted(set(range(21, 59)) - set(int(cell) for row in state for cell in row if cell != 'x'))[:sum(cell == 'x' for row in state for cell in row)])

8pt8ptThe A* algorithm was generated by GPT4 using the MSMT A* approach. GPT4's 13-th attempt at implementing the A* algorithm for consecutive_grid problem type passed the unit tests.

8pt8.5ptconsecutive_grid instance (diff_sorted_id: 43): We have a 3x3 numerical grid, with numbers ranging from 7 to 60 (7 included in the range but 60 is not included). The numbers in each row and column must be strictly increasing or decreasing. This means that either first > second > third or first < second < third in each row and column. If a grid cell is marked with an 'x', the number in that position is hidden. The objective is to replace the 'x's with unique integers from the given range, ensuring that each number only appears once in the grid. The replacements must maintain the consecutive order in each row and column. Additionally, the sum of the numbers in the topmost row plus the numbers in the rightmost column plus the numbers in the diagonal connecting the top-left corner of the grid to its bottom-right corner should be minimized. The solution should be given as a list of tuples in Python syntax. Each tuple should represent the replacement of a number with an  'x' number and contain three elements: the row index of the 'x', the column index  of the 'x' (both starting from 0), and the value of the number that replaces the 'x'. The initial state of the grid is as follows: \n\nGrid:\n [['13' 'x' 'x']\n ['x' 'x' '27']\n ['x' '26' 'x']]

'initialize' function generated by GPT4 for the problem above in the second stage of the MSMT approach[language=Python]
def initialize():
# Define the initial state of the grid, as a 2d tuple
initial_state = (('13', 'x', 'x'), ('x', 'x', '27'), ('x', '26', 'x'))
# Define the range of numbers that can be used to replace 'x'
num_range = set(range(7, 60))
# Define the dimensions of the grid
num_rows = 3
num_cols = 3
# Initialize a dictionary to store the cost of reaching each visited state
visited_costs =
visited_costs[initial_state] = 0
# Initialize a priority queue of states not yet visited, with the initial state as the first element. The priority of each element is the cost to reach that state (g) + the estimate remaining cost (h) to reach the goal
# Record the actions required to get to each state in a list; no actions performed to reach the initial state
queue = [(0, 0, [], initial_state)]
return initial_state, num_range, num_rows, num_cols, visited_costs, queue

8pt8ptGPT4 successfully generated an optimal and correct solution for this consecutive_grid problem instance using MSMT A* approach. Prompting GPT4 with all other four code and text-based prompting methods resulted in infeasible solutions.

8.5pt9pttraffic instance (diff_sorted_id: 1): Using the provided matrix map of a city, where numbers represent travel time in minutes (all numbers are positive integers) and 'x' marks closed workshops, find the quickest route for Ben to travel from his current workshop at index (5, 7) to his destination workshop at index (2, 1), indexing from 0. Ben's car can move north, south, east, or west from a given crossroad, provided there's no x in that direction. Also, there are 3 districts in the city with district 1 covering rows 0 to 2, district 2 covering rows 3 to 4, and district 3 covering rows 5 to 8. Ben has to visit at least 1 workshop in each district on his path to the destination. The roads are bidirectional. The answer should be a list of tuples (in Python syntax) indicating the index of workshops on Ben's path. The start and end workshops must be included in the path.\n[13 x x 3 10 20 3 x 5]\n[x x x x 20 16 x x 17]\n[3 14 18 8 1 20 14 x 7]\n[13 3 6 10 7 4 6 6 1]\n[10 12 2 x 11 x 10 8 11]\n[x x x 11 6 18 13 20 17]\n[x x 16 x 4 17 7 10 15]\n[x 7 16 6 19 4 7 x x]\n[x 11 18 x x x 3 8 x]

8pt8.5ptA* algorithm generated by GPT4 for the problem above using A*  approach that passed the unit tests:[language=Python]
import heapq

def initialize():
# Define the initial state and the goal state of the problem, represented as tuples
initial_state = (5, 7)
goal_state = (2, 1)
# Encoding other variables given in the problem statement
num_rows = 9
num_cols = 9
matrix = [[13, 'x', 'x', 3, 10, 20, 3, 'x', 5],['x', 'x', 'x', 'x', 20, 16, 'x', 'x', 17],[3, 14, 18, 8, 1, 20, 14, 'x', 7],[13, 3, 6, 10, 7, 4, 6, 6, 1],[10, 12, 2, 'x', 11, 'x', 10, 8, 11],['x', 'x', 'x', 11, 6, 18, 13, 20, 17],['x', 'x', 16, 'x', 4, 17, 7, 10, 15],['x', 7, 16, 6, 19, 4, 7, 'x', 'x'], ['x', 11, 18, 'x', 'x', 'x', 3, 8, 'x']]
districts = 1: range(0, 3), 2: range(3, 5), 3: range(5, 9)
# Initialize a dictionary to store the cost of reaching each visited state
visited_costs =
visited_costs[initial_state] = 0
# Initialize a priority queue of states not yet visited, with the initial state as the first element. The priority of each element is the cost to reach that state (g) + the estimate remaining cost (h) to reach the goal
# Record the actions required to get to each state in a list; no actions performed to reach the initial state
queue = [(0, 0, [], initial_state, 1: False, 2: False, 3: True)]
return initial_state, goal_state, num_rows, num_cols, matrix, districts, visited_costs, queue

def a_star():
initial_state, goal_state, num_rows, num_cols, matrix, districts, visited_costs, queue = initialize()
while queue:
_, g, actions, state, visited_districts = heapq.heappop(queue)
# Check if the current state is the goal state
if state == goal_state and all(visited_districts.values()):
return actions
# Generate all possible actions from the current state, which includes moving to any of the 4 neighboring cells
for d_row, d_col in [(0, -1), (0, 1), (1, 0), (-1, 0)]:
new_row, new_col = state[0] + d_row, state[1] + d_col
# Check if the new state would be valid, ie if the coordinate of the cell to move to is a valid coordinate within the bounds of the matrix and the cell is not 'x'
if 0 <= new_row < num_rows and 0 <= new_col < num_cols and matrix[new_row][new_col] != 'x':
# Generate the new state
new_state = (new_row, new_col)
# The cost so far is the sum of the travel times, as our objective is to minimize the total travel time
new_cost = g + matrix[new_row][new_col]
# Update the visited districts
new_visited_districts = visited_districts.copy()
for district, rows in districts.items():
if new_row in rows:
new_visited_districts[district] = True
# If the new state is unvisited or we found a new path with a lower cost to reach this state, add it to the queue of not-yet-visited states
if new_state not in visited_costs or new_cost < visited_costs[new_state]:
visited_costs[new_state] = new_cost
heapq.heappush(queue, (g + heuristic(new_state, goal_state), new_cost, actions + [new_state], new_state, new_visited_districts))
return None

*8pt8.5ptThe GPT4's implementation of the A* algorithm continues on the next page.

8pt8.5ptContinuation of GPT-4's implementation: [language=Python]
def heuristic(state, goal):
# An admissible and consistent heuristic is the Manhattan distance (the shortest path) of the current position from the goal position
# The heuristic relaxes the constraint that a cell can only be moved to if it's not 'x' and presumes we can move to the goal position by moving to any of the neighboring cells
# Thus the heuristic reports a lower estimate on the cost to reach goal state and is admissible
# The heuristic is consistent because the cost of moving to a neighboring coordinate is always greater than or equal to 1, which is exactly the decrease in the Manhattan distance, if the cell is moved toward its goal position, otherwise the estimated cost of the successor node is the same or higher, and he heuristic estimate for the goal state is 0, as the distance of the goal position from itself would be 0.
h = abs(state[0] - goal[0]) + abs(state[1] - goal[1])
return h

8pt8.5ptThe A* algorithm was generated by GPT4 using the MSMT A* approach. GPT4's first implementation of the A* algorithm for traffic problem type passed the unit tests.

8.5pt9pttraffic instance (diff_sorted_id: 104): Using the provided matrix map of a city, where numbers represent travel time in minutes (all numbers are positive integers) and 'x' marks closed workshops, find the quickest route for Ben to travel from his current workshop at index (7, 2) to his destination workshop at index (4, 14), indexing from 0. Ben's car can move north, south, east, or west from a given crossroad, provided there's no x in that direction. Also, there are 3 districts in the city with district 1 covering rows 0 to 4, district 2 covering rows 5 to 8, and district 3 covering rows 9 to 14. Ben has to visit at least 1 workshop in each district on his path to the destination. The roads are bidirectional. The answer should be a list of tuples (in Python syntax) indicating the index of workshops on Ben's path. The start and end workshops must be included in the path.\n[x x 7 18 11 4 9 x 15 x x x 1 x x]\n[x x 14 x 10 x x x 8 x x 16 1 x x]\n[17 17 x x x x x 7 6 12 x x x 7 x]\n[x x x x 10 x x 18 1 11 4 x 13 10 16]\n[x x x 12 1 x x x 2 7 1 x 2 x 5]\n[x x 8 x 12 x x 5 17 x 2 x 4 10 18]\n[x x 4 19 1 x 18 7 x 10 3 x 19 16 19]\n[6 12 15 16 5 9 16 18 10 15 5 x 5 14 x]\n[x 16 8 17 12 11 16 8 9 9 7 4 5 20 3]\n[19 17 15 x x 17 x 3 2 2 11 7 8 16 1]\n[13 4 17 x x x x 5 x 18 16 15 19 4 x]\n[11 x x x x 12 x x x x x x 19 x x]\n[18 x x x 9 19 x 16 6 x 9 3 16 15 x]\n[x x x 10 x x 4 3 x 3 x 16 18 x 12]\n[x 13 x x x x x 10 5 x 17 x x 7 x]

8pt8.5pt'initialize' function generated by GPT4 for the problem above in the second stage of the MSMT approach[language=Python]
def initialize():
# Define the initial state and the goal state of the problem, represented as tuples
initial_state = (7, 2)
goal_state = (4, 14)

# Encoding other variables given in the problem statement
num_rows = 15
num_cols = 15
matrix = [[ 'x', 'x', 7, 18, 11, 4, 9, 'x', 15, 'x', 'x', 'x', 1, 'x', 'x'], [ 'x', 'x', 14, 'x', 10, 'x', 'x', 'x', 8, 'x', 'x', 16, 1, 'x', 'x'], [ 17, 17, 'x', 'x', 'x', 'x', 'x', 7, 6, 12, 'x', 'x', 'x', 7, 'x'], [ 'x', 'x', 'x', 'x', 10, 'x', 'x', 18, 1, 11, 4, 'x', 13, 10, 16], [ 'x', 'x', 'x', 12, 1, 'x', 'x', 'x', 2, 7, 1, 'x', 2, 'x', 5], [ 'x', 'x', 8, 'x', 12, 'x', 'x', 5, 17, 'x', 2, 'x', 4, 10, 18], [ 'x', 'x', 4, 19, 1, 'x', 18, 7, 'x', 10, 3, 'x', 19, 16, 19], [ 6, 12, 15, 16, 5, 9, 16, 18, 10, 15, 5, 'x', 5, 14, 'x'], [ 'x', 16, 8, 17, 12, 11, 16, 8, 9, 9, 7, 4, 5, 20, 3], [ 19, 17, 15, 'x', 'x', 17, 'x', 3, 2, 2, 11, 7, 8, 16, 1], [ 13, 4, 17, 'x', 'x', 'x', 'x', 5, 'x', 18, 16, 15, 19, 4, 'x'], [ 11, 'x', 'x', 'x', 'x', 12, 'x', 'x', 'x', 'x', 'x', 'x', 19, 'x', 'x'], [ 18, 'x', 'x', 'x', 9, 19, 'x', 16, 6, 'x', 9, 3, 16, 15, 'x'], [ 'x', 'x', 'x', 10, 'x', 'x', 4, 3, 'x', 3, 'x', 16, 18, 'x', 12],[ 'x', 13, 'x', 'x', 'x', 'x', 'x', 10, 5, 'x', 17, 'x', 'x', 7, 'x']]
districts = 1: range(0, 5), 2: range(5, 9), 3: range(9, 15)
# Initialize a dictionary to store the cost of reaching each visited state
visited_costs =
visited_costs[initial_state] = 0
# Initialize a priority queue of states not yet visited, with the initial state as the first element. The priority of each element is the cost to reach that state (g) + the estimate remaining cost (h) to reach the goal
# Record the actions required to get to each state in a list; no actions performed to reach the initial state
queue = [(0, 0, [initial_state], initial_state, 1: False, 2: True, 3: False)]
return initial_state, goal_state, num_rows, num_cols, matrix, districts, visited_costs, queue

8pt8.5ptGPT4 successfully generated an optimal and correct solution for this traffic problem instance using MSMT A* approach. Prompting GPT4 with A* results in a feasible but incorrect solution and all other three baseline code and text-based prompting methods resulted in infeasible solutions.

Trampoline Matrix

7.9pt8.1pttrampoline_matrix instance (diff_sorted_id: 4): Alex is at a trampoline park with a grid of mini trampolines, arranged in a square of 9x9. Some trampolines are broken and unusable. A map of the park is provided below, with 1 indicating a broken trampoline and 0 indicating a functional one. Alex can jump to any of the eight adjacent trampolines, as long as they are not broken. However, Alex must make excatly 3 diagonal jumps, no more, no less, on his path to his destination. He is currently on the trampoline at position (8, 1) (positions are counted from 0, left to right, top to bottom) and wants to reach the trampoline at position (0, 5). What is the shortest sequence of trampolines he should jump on to reach his destination (including the first and final trampolines)? The answer should be a list of tuples, in Python syntax, indicating the row and column of each trampoline Alex jumps on. \n0 0 1 0 0 0 0 0 1\n0 1 0 1 1 0 0 0 0\n1 1 1 1 1 1 1 1 0\n1 1 0 1 1 0 0 0 0\n1 0 1 0 1 0 1 1 1\n1 0 1 0 0 0 1 0 1\n0 1 0 0 0 1 1 0 1\n0 0 1 0 1 1 1 1 1\n1 0 0 1 1 0 0 1 1

8pt8.5ptA* algorithm generated by GPT4 for the problem above using A*  approach that passed the unit tests:[language=Python]
import heapq

def initialize():
# Define the initial state and the goal state of the problem, represented as tuples
initial_state = (8, 1)
goal_state = (0, 5)
# Encoding other variables given in the problem statement
num_rows = 9
num_cols = 9
park_map = [[0, 0, 1, 0, 0, 0, 0, 0, 1],[0, 1, 0, 1, 1, 0, 0, 0, 0],[1, 1, 1, 1, 1, 1, 1, 1, 0],[1, 1, 0, 1, 1, 0, 0, 0, 0],[1, 0, 1, 0, 1, 0, 1, 1, 1],[1, 0, 1, 0, 0, 0, 1, 0, 1],[0, 1, 0, 0, 0, 1, 1, 0, 1],[0, 0, 1, 0, 1, 1, 1, 1, 1],[1, 0, 0, 1, 1, 0, 0, 1, 1]]
diagonal_jumps = 3
# Initialize a dictionary to store the cost of reaching each visited state
visited_costs =
visited_costs[(initial_state, diagonal_jumps)] = 0
# Initialize a priority queue of states not yet visited, with the initial state as the first element. The priority of each element is the cost to reach that state (g) + the estimate remaining cost (h) to reach the goal
# Record the actions required to get to each state in a list; no actions performed to reach the initial state
queue = [(0, 0, [], (initial_state, diagonal_jumps))]
return initial_state, goal_state, num_rows, num_cols, park_map, diagonal_jumps, visited_costs, queue

def a_star():
# The initialize function initializes and returns the visited_costs dictionary and the priority queue and encodes all of the variables given in the problem (ie the initial and goal state, dimensions of the park, park map, and number of diagonal jumps)
initial_state, goal_state, num_rows, num_cols, park_map, diagonal_jumps, visited_costs, queue = initialize()
# While there are un-visited states
while queue:
# Pop the state with the lowest sum of the cost so far and estimated cost to the goal from the queue
_, g, actions, (state, diagonal_jumps_left) = heapq.heappop(queue)
# We can check if the current state is the goal state with a simple equality check, as the goal state is predefined
if state == goal_state and diagonal_jumps_left == 0:
return actions
# Generate all valid actions from the current state, which includes jumping to any of the 8 neighboring trampolines
# Generate the coordinates of the neighboring trampolines
for d_row, d_col in [(0, -1), (0, 1), (1, 0), (-1, 0), (1, 1), (-1, -1), (1, -1), (-1, 1)]:
new_row, new_col = state[0] + d_row, state[1] + d_col
# Check if the jump is valid, ie if the coordinate of the trampoline to jump to is a valid coordinate within the bounds of the park and the trampoline is not broken
if 0 <= new_row < num_rows and 0 <= new_col < num_cols and park_map[new_row][new_col] == 0:
# The jump is valid, generate the new state
new_state = (new_row, new_col)
# The cost so far is the number of jumps made, as our objective is to minimize the number of jumps required to reach the goal state
new_cost = g + 1
# If the jump is diagonal, decrement the number of diagonal jumps left
if d_row != 0 and d_col != 0:
new_diagonal_jumps_left = diagonal_jumps_left - 1
new_diagonal_jumps_left = diagonal_jumps_left
# If the new state is unvisited or we found a new path with a lower cost to reach this state, add it to the queue of not-yet-visited states

*8pt8.5ptThe GPT4's implementation of the A* algorithm continues on the next page.

8pt8.5ptContinuation of GPT-4's implementation: [language=Python]