I was given the task of making a grid peg solitaire puzzle. Here are the programs, the basic puzzle file, and the actual grid solitaire puzzle:
The puzzle software
class Puzzle:
""""
Snapshot of a full-information puzzle, which may be solved, unsolved,
or even unsolvable.
"""
def fail_fast(self):
"""
Return True iff Puzzle self can never be extended to a solution.
Override this in a subclass where you can determine early that
this Puzzle can't be solved.
@type self: Puzzle
@rtype: bool
"""
return False
def is_solved(self):
"""
Return True iff Puzzle self is solved.
This is an abstract method that must be implemented
in a subclass.
@type self: Puzzle
@rtype: bool
"""
raise NotImplementedError
def extensions(self):
"""
Return list of legal extensions of Puzzle self.
This is an abstract method that must be implemented
in a subclass.
@type self: Puzzle
@rtype: list[Puzzle]
"""
raise NotImplementedError
The grid peg solitaire puzzle with the above puzzle imported above.:
from puzzle import Puzzle
class GridPegSolitairePuzzle(Puzzle):
"""
Snapshot of peg solitaire on a rectangular grid. May be solved,
unsolved, or even unsolvable.
"""
def __init__(self, marker, marker_set):
"""
Create a new GridPegSolitairePuzzle self with
marker indicating pegs, spaces, and unused
and marker_set indicating allowed markers.
@type marker: list[list[str]]
@type marker_set: set[str]
"#" for unused, "*" for peg, "." for empty
"""
assert isinstance(marker, list)
assert len(marker) > 0
assert all([len(x) == len(marker[0]) for x in marker[1:]])
assert all([all(x in marker_set for x in row) for row in marker])
assert all([x == "*" or x == "." or x == "#" for x in marker_set])
self._marker, self._marker_set = marker, marker_set
# TODO
# implement __eq__, __str__ methods
# __repr__ is up to you
#Received help from TA Bryan
def __eq__(self, other):
"""
Return whether GridPegSolitairePuzzle self is equivalent to other.
@type self: GridPegSolitairePuzzle
@type other: GridPegSolitairePuzzle | Any
@rtype: bool
>>> grid = [["*", "*", "*", "*", "*"]]
>>> grid.append(["*", "*", "*", "*", "*"])
>>> grid.append(["*", "*", "*", "*", "*"])
>>> grid.append(["*", "*", ".", "*", "*"])
>>> grid.append(["*", "*", "*", "*", "*"])
>>> gpsp1 = GridPegSolitairePuzzle(grid, {"*", ".", "#"})
>>> grid = [["*", "*", "*", "*", "*"]]
>>> grid.append(["*", "*", "*", "*", "*"])
>>> grid.append(["*", "*", "*", "*", "*"])
>>> grid.append(["*", "*", ".", "*", "*"])
>>> grid.append(["*", "*", "*", "*", "*"])
>>> gpsp2 = GridPegSolitairePuzzle(grid, {"*", ".", "#"})
>>> grid = [[".", ".", ".", ".", "."]]
>>> grid.append(["*", "*", "*", "*", "*"])
>>> grid.append(["*", "*", "*", "*", "*"])
>>> grid.append(["*", "*", ".", "*", "*"])
>>> grid.append(["*", "*", "*", "*", "*"])
>>> gpsp3 = GridPegSolitairePuzzle(grid, {"*", ".", "#"})
>>> gpsp1.__eq__(gpsp2)
True
>>> gpsp1.__eq__(gpsp3)
False
"""
#TA Bryan added return (type(other) == type(self) part for me
return (type(other) == type(self) and
self._marker == other._marker and
self._marker_set == other._marker_set)
def __str__(self):
"""
Return a human-readable string representation of GridPegSolitairePuzzle.
@type self: GridPegSolitairePuzzle
@rtype: str
>>> grid = [["*", "*", "*", "*", "*"]]
>>> grid.append(["*", "*", "*", "*", "*"])
>>> grid.append(["*", "*", "*", "*", "*"])
>>> grid.append(["*", "*", ".", "*", "*"])
>>> grid.append(["*", "*", "*", "*", "*"])
>>> gpsp1 = GridPegSolitairePuzzle(grid, {"*", ".", "#"})
>>> print(gpsp1)
* * * * *
* * * * *
* * * * *
* * . * *
* * * * *
"""
return "\n".join([" ".join(row) for row in self._marker])
def extensions(self):
"""
Return list of extensions of GridPegSolitairePuzzle self.
@type self: GridPegSolitairePuzzle
@rtype: list[GridPegSolitairePuzzle]
>>> grid = [[".", ".", ".", "*", "*"]]
>>> grid.append([".", ".", ".", ".", "."])
>>> grid.append([".", ".", ".", ".", "."])
>>> grid.append([".", ".", ".", ".", "."])
>>> grid.append([".", ".", ".", ".", "."])
>>> gpsp1 = GridPegSolitairePuzzle(grid, {"*", ".", "#"})
>>> L1 = gpsp1.extensions()
>>> grid[0] = [".", ".", "*", ".", "."]
>>> L2 = [GridPegSolitairePuzzle(grid, {"*", ".", "#"})]
>>> len(L1) == len(L2)
True
>>> all([s in L2 for s in L1])
True
>>> all([s in L1 for s in L2])
True
"""
legal = []
# For each peg, checks whether it can be jumped up, down, left, or right
# If so, that configuration is added to the list of legal extensions
for r in range(len(self._marker)):
for c in range(len(self._marker[r])):
if self._marker[r][c] == "*":
legal.extend(jump_left(self._marker, r, c))
legal.extend(jump_right(self._marker, r, c))
legal.extend(jump_up(self._marker, r, c))
legal.extend(jump_down(self._marker, r, c))
return legal
def is_solved(self):
"""
Returns true iff there is one peg, '*', remaining in the grid
@type self: GridPegSolitairePuzzle
@rtype: bool
>>> grid = [[".", "*", ".", ".", "*"]]
>>> grid.append([".", ".", "*", ".", "."])
>>> grid.append(["*", "*", "*", "*", "*"])
>>> grid.append(["*", "*", ".", "*", "*"])
>>> grid.append(["*", "*", "*", "*", "*"])
>>> gpsp1 = GridPegSolitairePuzzle(grid, {"*", ".", "#"})
>>> grid = [[".", ".", ".", ".", "."]]
>>> grid.append([".", ".", ".", ".", "."])
>>> grid.append([".", ".", ".", ".", "."])
>>> grid.append([".", ".", "*", ".", "."])
>>> grid.append([".", ".", ".", ".", "."])
>>> gpsp2 = GridPegSolitairePuzzle(grid, {"*", ".", "#"})
>>> gpsp1.is_solved()
False
>>> gpsp2.is_solved()
True
"""
# Makes a list of how many pegs are in each row
# Checks that one row has one peg, and the rest have none
pegs = [row.count('*') for row in self._marker]
return pegs.count(1) == 1 and pegs.count(0) == len(pegs) - 1
def jump_left(markers, row, column):
"""
Returns the grid that results after the marker at (row, column) jumps left
@type markers: list[list[str]]
@type row: int
@type column: int
@rtype: list[GridPegSolitairePuzzle]
>>> grid = [["*", "*", "*", "*", "*"]]
>>> grid.append(["*", "*", "*", "*", "*"])
>>> grid.append(["*", "*", "*", "*", "*"])
>>> grid.append(["*", "*", ".", "*", "*"])
>>> grid.append(["*", "*", "*", "*", "*"])
>>> gpsp1 = GridPegSolitairePuzzle(grid, {"*", ".", "#"})
>>> L1 = jump_left(gpsp1._marker, 3, 4)
>>> grid[3][2] = "*"
>>> grid[3][3] = "."
>>> grid[3][4] = "."
>>> L2 = [GridPegSolitairePuzzle(grid, {"*", ".", "#"})]
>>> L1 == L2
True
"""
# Checking bounds and whether the right pieces are in the positions needed
if (column - 2) >= 0 and (markers[row][column - 2] == ".") and\
(markers[row][column - 1] == "*"):
# Each row must be copied individually (since they are all lists)
m_copy = []
for i in range(len(markers)):
m_copy.append(markers[i].copy())
new_grid = GridPegSolitairePuzzle(m_copy, {"*", ".", "#"})
# Performs the jump
new_grid._marker[row][column] = "."
new_grid._marker[row][column - 1] = "."
new_grid._marker[row][column - 2] = "*"
return [new_grid]
else:
return []
def jump_right(markers, row, column):
"""
Returns the grid that results after the marker at (row, column) jumps right
@type markers: list[list[str]]
@type row: int
@type column: int
@rtype: list[GridPegSolitairePuzzle]
>>> grid = [["*", "*", "*", "*", "*"]]
>>> grid.append(["*", "*", "*", "*", "*"])
>>> grid.append(["*", "*", "*", "*", "*"])
>>> grid.append(["*", "*", ".", "*", "*"])
>>> grid.append(["*", "*", "*", "*", "*"])
>>> gpsp1 = GridPegSolitairePuzzle(grid, {"*", ".", "#"})
>>> L1 = jump_right(gpsp1._marker, 3, 0)
>>> grid[3][2] = "*"
>>> grid[3][0] = "."
>>> grid[3][1] = "."
>>> L2 = [GridPegSolitairePuzzle(grid, {"*", ".", "#"})]
>>> L1 == L2
True
"""
# Checking bounds and whether the right pieces are in the positions needed
if (column + 2) < len(markers[row]) and\
(markers[row][column + 2] == ".") and\
(markers[row][column + 1] == "*"):
# Each row must be copied individually (since they are all lists)
m_copy = []
for i in range(len(markers)):
m_copy.append(markers[i].copy())
new_grid = GridPegSolitairePuzzle(m_copy,
{"*", ".", "#"})
# Performs the jump
new_grid._marker[row][column] = "."
new_grid._marker[row][column + 1] = "."
new_grid._marker[row][column + 2] = "*"
return [new_grid]
else:
return []
def jump_up(markers, row, column):
"""
Returns the grid that results after the marker at (row, column) jumps up
@type markers: list[list[str]]
@type row: int
@type column: int
@rtype: list[GridPegSolitairePuzzle]
>>> grid = [["*", "*", "*", "*", "*"]]
>>> grid.append(["*", "*", "*", "*", "*"])
>>> grid.append(["*", "*", ".", "*", "*"])
>>> grid.append(["*", "*", "*", "*", "*"])
>>> grid.append(["*", "*", "*", "*", "*"])
>>> gpsp1 = GridPegSolitairePuzzle(grid, {"*", ".", "#"})
>>> L1 = jump_up(gpsp1._marker, 4, 2)
>>> grid[2][2] = "*"
>>> grid[3][2] = "."
>>> grid[4][2] = "."
>>> L2 = [GridPegSolitairePuzzle(grid, {"*", ".", "#"})]
>>> L1 == L2
True
"""
# Checking bounds and whether the right pieces are in the positions needed
if (row - 2) >= 0 and (markers[row - 2][column] == ".") and\
(markers[row - 1][column] == "*"):
# Each row must be copied individually (since they are all lists)
m_copy = []
for i in range(len(markers)):
m_copy.append(markers[i].copy())
new_grid = GridPegSolitairePuzzle(m_copy,
{"*", ".", "#"})
# Performs the jump
new_grid._marker[row][column] = "."
new_grid._marker[row - 1][column] = "."
new_grid._marker[row - 2][column] = "*"
return [new_grid]
else:
return []
def jump_down(markers, row, column):
"""
Returns the grid that results after the marker at (row, column) jumps down
@type markers: list[list[str]]
@type row: int
@type column: int
@rtype: list[GridPegSolitairePuzzle]
>>> grid = [["*", "*", "*", "*", "*"]]
>>> grid.append(["*", "*", "*", "*", "*"])
>>> grid.append(["*", "*", "*", "*", "*"])
>>> grid.append(["*", "*", ".", "*", "*"])
>>> grid.append(["*", "*", "*", "*", "*"])
>>> gpsp1 = GridPegSolitairePuzzle(grid, {"*", ".", "#"})
>>> L1 = jump_down(gpsp1._marker, 1, 2)
>>> grid[3][2] = "*"
>>> grid[2][2] = "."
>>> grid[1][2] = "."
>>> L2 = [GridPegSolitairePuzzle(grid, {"*", ".", "#"})]
>>> L1 == L2
True
"""
# Checking bounds and whether the right pieces are in the positions needed
if (row + 2) < len(markers) and\
(markers[row + 2][column] == ".") and\
(markers[row + 1][column] == "*"):
# Each row must be copied individually (since they are all lists)
m_copy = []
for i in range(len(markers)):
m_copy.append(markers[i].copy())
new_grid = GridPegSolitairePuzzle(m_copy,
{"*", ".", "#"})
# Performs the jump
new_grid._marker[row][column] = "."
new_grid._marker[row + 1][column] = "."
new_grid._marker[row + 2][column] = "*"
return [new_grid]
else:
return []
if __name__ == "__main__":
import doctest
doctest.testmod()
from puzzle_tools import depth_first_solve
grid = [["*", "*", "*", "*", "*"],
["*", "*", "*", "*", "*"],
["*", "*", "*", "*", "*"],
["*", "*", ".", "*", "*"],
["*", "*", "*", "*", "*"]]
gpsp = GridPegSolitairePuzzle(grid, {"*", ".", "#"})
import time
start = time.time()
solution = depth_first_solve(gpsp)
end = time.time()
print("Solved 5x5 peg solitaire in {} seconds.".format(end - start))
print("Using depth-first: \n{}".format(solution))
The code works entirely, but the professor does not like how I broke up the function definitions into jump_right, jump_left, jump_up, jump_down. He says I should do this all in one function called jump. What would the code be for this?
