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

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

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 - Cannot secure connection using TLS -

-
i'm trying establish secure socket connection between java client applet (built jdk 1.7.0_75-b13) , vc++ server application. as test vehicle, used vc++ client/server sample found in msdn forums, modified use schannel , able establish socket using cipher suite tls_rsa_with_aes_128_cbc_sha. works of tls 1.0/1.1/1.2. when try opening socket java applet same server application, connection rejected server reporting following: tls 1.0 acceptsecuritycontext failed: 0x80090327 tls 1.1 acceptsecuritycontext failed: 0x80090331 tls 1.2 acceptsecuritycontext failed: 0x80090331 this java code used create socket: debugprint("setting secure connection"); sslsocketfactory sslsocketfactory = (sslsocketfactory) sslsocketfactory.getdefault(); sslsocket sslsocket = (sslsocket) sslsocketfactory.createsocket("127.0.0.1", socketnumber); debugprint("starting handshake"); sslsocket.settcpnodelay(true); sslsocket.setsolinger(false, 0); sslsocket.s
Read more