Solving Programs

[hawkmp4]

Let me first say that I do NOT want code or any existing solvers.
For a project in my intro to computer science class, I decided to write a solver for the floppy cube in Python. It's simple, as expected, but I don't feel like it's very elegant. I'm not sure how to go about actually searching for puzzles that need a deeper depth.
In my program there is a function called 'move' that takes in a list describing the state of the puzzle and a string containing the move and changes the list based on what the move would do on the physical puzzle. I'm looping through the possible moves for each element in a given depth solution algorithm. Example-
stateToCheck = move(move(move(initialState),move1),move2),move3)
where move1, move2, and move3 take on U, R, L, D.
Of course, my loop and particularly the code for checking for redundant moves (U U) has to be copied and pasted and edited for EACH depth that I want to search for. For something as simple as a floppy cube, that's still 8 times.
Does anyone have any hints as to how I might make a better approach at this? I'm going to start working on a solver for the 2x2x3 for my own learning and enjoyment.

 

[stiwi griffin]

i don't know the exact name in english, but you could try with the algorithm of ordenation(method of bubble), it is not the best, but for the floppy it might be ok

 

[LNZ]

The is only 192 possible states for the floppy cube. It can be solved optimally in 12 face turns or less.

 

[tim]

Of course, my loop and particularly the code for checking for redundant moves (U U) has to be copied and pasted and edited for EACH depth that I want to search for. For something as simple as a floppy cube, that's still 8 times.
Does anyone have any hints as to how I might make a better approach at this?

Use a loop.

 

[Cangurino]

Use recursion.

 

[Johannes91]

http://www.jaapsch.net/puzzles/compcube.htm#tree
http://en.wikipedia.org/wiki/Depth-first_search

It can be solved optimally in 12 face turns or less.

Eight is enough. Previous thread about Floppy Cube: http://www.speedsolving.com/forum/showthread.php?t=11379.

 

[hawkmp4]

Thank you, all who replied and particularly Johannes. I should have known to look on Jaap's site.

 

[Musturd]

Recursion is a good idea (like someone above me said)
I wrote a Rubik's cube solver for my final project in my intro-computer science class, and my professor told me that depth first searching would work better than recursion, but that I probably wouldn't be able to implement DFS with my current comp sci knowledge without some extra research.

 

[Ranzha]

DO A BARREL ROLL.
Always helps me XD.

anyway, recursion = great.

 

[Johannes91]

my professor told me that depth first searching would work better than recursion

Recursion isn't an algorithm, comparing it to DFS doesn't make any sense. DFS can be (and often is) implemented using recursion.

, but that I probably wouldn't be able to implement DFS with my current comp sci knowledge without some extra research.

It's trivial really. In a high-level language it can take about 10 lines of code.

 

[hawkmp4]

Wouldn't a breadth-first search be faster for something like this? Where the average depth (around 4.4 moves for floppy if I remember correctly) is much less than the maximum depth?

 

[Johannes91]

You mean a single depth-first search? Yeah, that's not good; use iterative deepening (wiki).

For puzzles with a very low branching factor (less than 2 or so), breadth-first search can well be faster. But when it's larger, IDDFS works well because the repeated computations don't cost much (because searching at depth N takes longer than searching all lower depths combined), and the memory BFS requires can become significant.

In the case of floppy, it shouldn't matter which algorithm you use because the space is tiny.

 

[hawkmp4]

Yes, that's what I meant. Wrong word. Search depth 1, 2, 3 ... 8 in this case. Okay. Thanks, that's what I thought.