Results 1 to 12 of 12

Thread: 8 Puzzle Solving

  1. #1
    Join Date
    May 2006
    Location
    Australia
    Posts
    370
    Mentioned
    0 Post(s)
    Quoted
    0 Post(s)

    Default 8 Puzzle Solving

    Hey hey
    I am currently writing a dungeoneering script, and I need to solve the sliding puzzle (3x3 grid, need to slide each tile to the right place).
    I think I'll use A*, but not too sure.

    Just wondering if anyone else wants to do this bit for me?
    Not sure how many here are capable, its university level programming - but its a great challenge.

    The reason I ask is because there are just so many puzzles I need to write solvers for, and it'd be great if someone could lend a hand

    All I need is the logic. So It needs to receive a state, and output a list of moves to get to the completed state. (Pro-tip: use a long to store the game state, 4 bits for each position).

    If anyone can do it, they receive full credit on script release.
    Otherwise I'll get around to it.



    Just thought you programming junkies might enjoy the challenge :P
    ------
    Strong Holder
    Kill Goblins and Zombies in (ex) bot free zones. Loot & Bank. Stable: 1.2b

  2. #2
    Join Date
    Nov 2006
    Posts
    2,369
    Mentioned
    4 Post(s)
    Quoted
    78 Post(s)

    Default

    Sounds like a nice challenge. If I were you I would try it myself.

  3. #3
    Join Date
    Aug 2007
    Location
    Colorado
    Posts
    7,421
    Mentioned
    268 Post(s)
    Quoted
    1442 Post(s)

    Default

    Yeah I can understand you're reluctant to do yet another puzzle solver. I'm very sorry but I'm for sure this is out of my ability... Just know we're all proud of your progress.

    Current projects:
    [ AeroGuardians (GotR minigame), Motherlode Miner, Blast furnace ]

    "I won't fall in your gravity. Open your eyes,
    you're the Earth and I'm the sky..."


  4. #4
    Join Date
    Dec 2006
    Location
    Latvia
    Posts
    97
    Mentioned
    0 Post(s)
    Quoted
    0 Post(s)

    Default

    Ooh, ooh!

    I want, I want!

    I will look into it sometime this evening.

  5. #5
    Join Date
    Mar 2007
    Posts
    3,042
    Mentioned
    1 Post(s)
    Quoted
    14 Post(s)

    Default

    I take it that you'd want this solver to be written for use in Simba. I wrote one in Java when I was bored about a month ago, but I might look into doing it again with Simba.
    :-)

  6. #6
    Join Date
    Jan 2011
    Location
    Denver, CO
    Posts
    1,351
    Mentioned
    2 Post(s)
    Quoted
    72 Post(s)

    Default

    You can always look at how it's done in iDungeonPro

  7. #7
    Join Date
    May 2006
    Location
    Australia
    Posts
    370
    Mentioned
    0 Post(s)
    Quoted
    0 Post(s)

    Default

    Quote Originally Posted by Echo_ View Post
    You can always look at how it's done in iDungeonPro
    Nah. Don't even want to open that, just makes what I'm doing cheap if I copy :P

    @Method: Yeah, I am awful with PS. This would be a million times easier with OO.
    ------
    Strong Holder
    Kill Goblins and Zombies in (ex) bot free zones. Loot & Bank. Stable: 1.2b

  8. #8
    Join Date
    Apr 2011
    Posts
    32
    Mentioned
    0 Post(s)
    Quoted
    0 Post(s)

    Default

    When I get some free time, I'll take a look at it.

  9. #9
    Join Date
    May 2007
    Posts
    527
    Mentioned
    12 Post(s)
    Quoted
    109 Post(s)

    Default

    Hi,

    What about hashing solutions from all possible initial configurations? I don't think the search will be that big.

    edit:

    Damn, I quess my suggestion won't work as the empty tile in final position will vary. Seems your best choices
    are either A* or IDDFS.
    Last edited by superuser; 05-18-2011 at 12:10 PM.

  10. #10
    Join Date
    May 2006
    Location
    Australia
    Posts
    370
    Mentioned
    0 Post(s)
    Quoted
    0 Post(s)

    Default

    Quote Originally Posted by superuser View Post
    Hi,

    What about hashing solutions from all possible initial configurations? I don't think the search will be that big.

    edit:

    Damn, I quess my suggestion won't work as the empty tile in final position will vary. Seems your best choices
    are either A* or IDDFS.
    Empty tile in final position varies?
    Eh?

    Also, the search is too big to just hash solutions.
    ------
    Strong Holder
    Kill Goblins and Zombies in (ex) bot free zones. Loot & Bank. Stable: 1.2b

  11. #11
    Join Date
    May 2007
    Posts
    527
    Mentioned
    12 Post(s)
    Quoted
    109 Post(s)

    Default

    Quote Originally Posted by Iamadam View Post
    Empty tile in final position varies?
    Eh?

    Also, the search is too big to just hash solutions.
    I mean, if the final position can be either for example

    Code:
    123
    4 5
    678
    or

    Code:
    123
    456
    78
    or anything between, my suggestion won't work. However, if it's always ended in, say, the latter one, the hash will work.

  12. #12
    Join Date
    May 2006
    Location
    Australia
    Posts
    370
    Mentioned
    0 Post(s)
    Quoted
    0 Post(s)

    Default

    Solved.
    Used A* algorithm, with NSS as heuristic.
    ------
    Strong Holder
    Kill Goblins and Zombies in (ex) bot free zones. Loot & Bank. Stable: 1.2b

Thread Information

Users Browsing this Thread

There are currently 1 users browsing this thread. (0 members and 1 guests)

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •