SJS wrote:
I as at a friend's place over the holidays, and I picked up a little
sliding-tile puzzle of a lizard. There were 8 pieces on a little 3x3
grid, and I futzed with it a bit and decided that I didn't even like
those sorts of puzzles when they were that small.
That night, the cat got up in my lap, arranged itself across my
forearms, so I decided to "solve" the 3x3 8-piece sliding tile
puzzle. Now, this would have been an ideal time to try out Ruby, but
with a purring cat trapping my arms, that wasn't really practical.
Same with perl or TCL... I'd need a reference book at hand, and that
wasn't going to happen unless I dumped the cat. And it's just wrong
to dump a purring cat, so I fell back on that old standby we call C.
Funny. I wouldn't be able to pull that C out without grabbing at K&R.
However, my Python, even after not having written it for probably about
1 1/2 years is *still* just fine. I think you are far more clever than
I in choice of algorithm. I just used a simple recursive descent and
used a hash table to remember what states I already visited.
What is interesting to me is the difference in lines of code. Not
because Python is so much better, but simply because I could use vectors,
hash tables, strings, and sequences directly and Stewart had to reimplement
a data structure (deque).
And this matches my philosophy very well. I *HATE* reimplementing data
structures that already exist.
-a
After about 80 minutes of coding I have:
#!env python
import sys
import copy
availableDirs = [[(1, 0), (0, 1)], [(-1, 0), (0, 1), (1, 0)], [(-1, 0), (0, 1)],
[(0, -1), (1, 0), (0, 1)], [(-1, 0), (0, -1), (1, 0), (0, 1)],
[(0, -1), (-1, 0), (0, 1)],
[(1, 0), (0, -1)], [(-1, 0), (0, -1), (1, 0)], [(-1, 0), (0,
-1)]]
def swapSpace(puzzleState, direction):
spacePosition = puzzleState.find(" ")
spaceI = spacePosition % 3
spaceJ = spacePosition / 3
coordI = spaceI + direction[0]
coordJ = spaceJ + direction[1]
coordPosition = coordI + coordJ*3
newStateList = []
for ii in range(len(puzzleState)):
if ii == spacePosition:
newStateList.append(puzzleState[coordPosition])
elif ii == coordPosition:
# Redundant, should just use space
newStateList.append(puzzleState[spacePosition])
else:
newStateList.append(puzzleState[ii])
newState = "".join(newStateList)
return newState
def solveSingleStep(solutionState, targetState, visitedSolutions):
flgSolutionFound = False
nextSolutionState = []
solution = None
for (previousSteps, puzzleState) in solutionState:
nextDirs = availableDirs[puzzleState.find(" ")]
visitedSolutions[puzzleState] = True
for testDir in nextDirs:
newState = swapSpace(puzzleState, testDir)
newPreviousSteps = copy.copy(previousSteps)
newPreviousSteps.append(testDir)
if newState == targetState:
flgSolutionFound = True
solution = (newPreviousSteps, newState)
break
elif newState in visitedSolutions:
# New solution has already been visited ... ignore
pass
else:
nextSolutionState.append((newPreviousSteps, newState))
if flgSolutionFound:
break
if flgSolutionFound:
return (True, solution)
else:
return (False, nextSolutionState)
def boardPPrint(currentState):
ll = []
for ii in currentState:
ll.append(ii)
ll = tuple(ll)
print "[%s] [%s] [%s]\n[%s] [%s] [%s]\n[%s] [%s] [%s]\n\n" % ll
def main():
if len(sys.argv) != 3:
print "Wrong number of arguments"
exit()
startingState = sys.argv[1]
targetState = sys.argv[2]
flgSolved = False
solutionState = [([], startingState)]
visitedSolutions = {}
while(not flgSolved):
(flgSolved, newSolutionState) = solveSingleStep(solutionState,
targetState, visitedSolutions)
solutionState = newSolutionState
print "NSS:", len(newSolutionState), len(visitedSolutions)
if flgSolved:
print "SOLVED in %d steps: %s" % (len(solutionState[0]),
str(solutionState))
currentState = startingState
for ss in solutionState[0]:
boardPPrint(currentState)
currentState = swapSpace(currentState, ss)
boardPPrint(currentState)
if __name__ == "__main__":
main()
andrewl$ time python puzzle3.py "12345678 " " 87654321"
NSS: 2 1
NSS: 4 3
NSS: 8 7
NSS: 16 15
NSS: 20 31
NSS: 40 51
NSS: 66 90
NSS: 128 152
NSS: 164 268
NSS: 316 420
NSS: 456 706
NSS: 862 1102
NSS: 1206 1850
NSS: 2260 2874
NSS: 3162 4767
NSS: 5836 7279
NSS: 7760 11764
NSS: 13920 17402
NSS: 17344 26931
NSS: 29282 37809
NSS: 33280 54802
NSS: 51332 71912
NSS: 52140 95864
NSS: 71268 116088
NSS: 58492 140135
NSS: 65554 155713
NSS: 39710 170273
NSS: 2 171445
SOLVED in 28 steps: ([(-1, 0), (-1, 0), (0, -1), (0, -1), (1, 0), (1, 0), (0,
1), (0, 1), (-1, 0), (-1, 0), (0, -1), (0, -1), (1, 0), (1, 0), (0, 1), (0, 1),
(-1, 0), (-1, 0), (0, -1), (0, -1), (1, 0), (1, 0), (0, 1), (0, 1), (-1, 0),
(-1, 0), (0, -1), (0, -1)], ' 87654321')
[1] [2] [3]
[4] [5] [6]
[7] [8] [ ]
[1] [2] [3]
[4] [5] [6]
[7] [ ] [8]
[1] [2] [3]
[4] [5] [6]
[ ] [7] [8]
[1] [2] [3]
[ ] [5] [6]
[4] [7] [8]
[ ] [2] [3]
[1] [5] [6]
[4] [7] [8]
[2] [ ] [3]
[1] [5] [6]
[4] [7] [8]
[2] [3] [ ]
[1] [5] [6]
[4] [7] [8]
[2] [3] [6]
[1] [5] [ ]
[4] [7] [8]
[2] [3] [6]
[1] [5] [8]
[4] [7] [ ]
[2] [3] [6]
[1] [5] [8]
[4] [ ] [7]
[2] [3] [6]
[1] [5] [8]
[ ] [4] [7]
[2] [3] [6]
[ ] [5] [8]
[1] [4] [7]
[ ] [3] [6]
[2] [5] [8]
[1] [4] [7]
[3] [ ] [6]
[2] [5] [8]
[1] [4] [7]
[3] [6] [ ]
[2] [5] [8]
[1] [4] [7]
[3] [6] [8]
[2] [5] [ ]
[1] [4] [7]
[3] [6] [8]
[2] [5] [7]
[1] [4] [ ]
[3] [6] [8]
[2] [5] [7]
[1] [ ] [4]
[3] [6] [8]
[2] [5] [7]
[ ] [1] [4]
[3] [6] [8]
[ ] [5] [7]
[2] [1] [4]
[ ] [6] [8]
[3] [5] [7]
[2] [1] [4]
[6] [ ] [8]
[3] [5] [7]
[2] [1] [4]
[6] [8] [ ]
[3] [5] [7]
[2] [1] [4]
[6] [8] [7]
[3] [5] [ ]
[2] [1] [4]
[6] [8] [7]
[3] [5] [4]
[2] [1] [ ]
[6] [8] [7]
[3] [5] [4]
[2] [ ] [1]
[6] [8] [7]
[3] [5] [4]
[ ] [2] [1]
[6] [8] [7]
[ ] [5] [4]
[3] [2] [1]
[ ] [8] [7]
[6] [5] [4]
[3] [2] [1]
real 0m15.413s
user 0m15.181s
sys 0m0.160s
Time is in a 2.16GHz core 2 duo
--
[email protected]
http://www.kernel-panic.org/cgi-bin/mailman/listinfo/kplug-lpsg
