How to make Prolog depth-first-search algorithm go deeper into the tree? (Applied to Sokoban) -

-

i'm trying solve sokoban puzzle in prolog using depth-first-search algorithm, cannot manage search solution tree in depth. i'm able explore first level.

all sources @ github (links revision when question asked) feel free explore , test them. divided rules several files:

  • board.pl: contains rules related board: directions, neighbourhoods,...
  • game.pl: file states rules movements, valid positions,...
  • level1.pl: defines board, position of boxes , solution squares sample game.
  • sokoban.pl: tries implement dfs :(

i know need go deeper when new state created instead of checking if final state , backtracking... need continue moving, impossible reach final state 1 movement.

any help/advice highly appreciated, i've been playing around without improvements.

thanks!

ps.- ¡ah! i'm working swi-prolog, in case makes difference

ps.- i'm newbie prolog, , maybe i'm facing obvious mistake, reason i'm asking here.

this easy fix: in sokoban.pl, predicate solve_problem/2, limiting solution lists of single element in goal:

   solve_dfs(problem, initial, [initial], [solution])

instead, mean:

    solve_dfs(problem, initial, [initial], solution)

because solution can consist of many moves.

in fact, better search strategy iterative deepening, with:

    length(solution, _),     solve_dfs(problem, initial, [initial], solution)

iterative deepening complete search strategy , optimal strategy under quite general assumptions.

other that, recommend cut down significant number of impure i/o calls in program. there many predicates write on screen.

instead, focus on clear declarative description, , cleanly separate output description of solution looks like. in fact, let toplevel printing you: describe solution looks (you doing this), , let toplevel display solution variable bindings. also, think declaratively, , use better names dfs_moves/4, problem_solution/2 instead of solve_dfs/4, solve_problem/2 etc.

dcgs may in places of code more conveniently describe lists.

+1 tackling nice , challenging search problem prolog!


Comments

Post a Comment

Popular posts from this blog

java - Custom OutputStreamAppender not run: LOGBACK: No context given for <MYAPPENDER> -

-
i wish write custom appender on basis of outputstreamappender . wrote following class package tests; import java.io.ioexception; import java.io.outputstream; import ch.qos.logback.core.outputstreamappender; public class myappender<e> extends outputstreamappender<e> { public myappender() { system.out.println("myappender created"); setoutputstream(new outputstream() { @override public void write(int b) throws ioexception { throw new unsupportedoperationexception(); } }); } } then wrote following runner: package tests; import org.slf4j.loggerfactory; import ch.qos.logback.classic.logger; public class runner { private static final logger log = (logger) loggerfactory.getlogger(runner.class); public static void main(string[] args) { //log.addappender(new myappender<iloggingevent>()); log.info("hello world"); } } finall...
Read more

java - UML - How would you draw a try catch in a sequence diagram? -

-
Image
is there standard way of drawing try catch sequence diagrams? i've made attempt based on this feel end result doesn't feel right. code diagram based around: public static void save () { try { filehandle filehandle = gdx.files.external(file); filehandle.writestring(boolean.tostring(constantshandler.soundenabled)+"\n", false); (int = 0; < 5; i++) { filehandle.writestring(integer.tostring(constantshandler.highscores[i])+"\n", true); } } catch (throwable e) { } } my attempt note: know still need add loop. that's ok. fragments meant show conditional control flow in sequence diagram. superstructures puts limitations on use of fragments (see pp. 467 of ss2.1.1). should use critical region try part above. , option catch . however, keep telling can take quite freedom in using uml. it's language , such changes in life time. long reader ge...
Read more

c++ - No viable overloaded operator for references a map -

-
i trying use map can make tag names reference number. when try , use it, in code error (6 in total every time reference map): src/main.cpp:25:45: error: no viable overloaded operator[] type 'std::map<std::string, std::string>' const char* idcs = node.child_value(tagmap[3]); this code: #include "pugi/pugixml.hpp" #include <iostream> #include <string> #include <map> int main() { pugi::xml_document doca, docb; std::map<std::string, pugi::xml_node> mapa, mapb; std::map<std::string, std::string> tagmap {{"1", "data"}, {"2", "entry"}, {"3", "id"}, {"4", "content"}}; if (!doca.load_file("a.xml") || !docb.load_file("b.xml")) { std::cout << "can't find input files"; return 1; } (auto& node: doca.child(tagmap[1]).children(tagmap[2])) { co...
Read more