This is the 8th day of my participation in the First Challenge 2022
Antecedents to review
Before we have completed the modeling of the checkerboard, the next is the core part of the violence solving program, namely the enumeration algorithm.
After being insulted by my IQ detector, I became angry.
🎮 game introduction: boring weekend, to play [IQ detector] – nuggets (juejin. Cn) 🎮 click to try to play: Hopscotch game – Gitee (Gitee. IO)
Algorithm implementation
In order for the program to constantly try and error every move, you need to design an enumeration algorithm. When the first piece is set, the moves corresponding to the second move correspond to several moves of the third move, so that when the first piece is fixed, all the moves on the board form a tree. There are 16 options for the position of the first piece. Considering the symmetry, repetition can be omitted, leaving only 4 unique starting points. Thus, all moves in the entire game can be represented by a forest of four trees. Enumeration algorithms, on the other hand, try to find the ones that finish the game among all the leaves.
Next, we let the algorithm explore and refine the tree, starting at the root.
Basic operation
First, we need some basic operations.
To represent the checkerboard state (which squares are empty and which have pieces), we define an occupied list and maintain an unoccupied list for convenience. The two lists of preliminary tests are as follows:
NodesOccupied = []
NodesUnoccupied = list(range(15))
Copy the codeGet all the moves of the chess piece N in the current board, enter the number as the chess piece n, and this operation will walk through NodesUnoccupied to get all the moves of the chess piece, that is, which two squares to occupy next:
def getRoads(n) :
options_all = list(combinations(NodesUnoccupied, 2))
options = []
for option in options_all:
if isSameRow(n, option[0], option[1]) is True\
and ((n < option[0] and n < option[1]) or (n > option[0] and n > option[1])):
options.append(option)
return options
Copy the codeTo perform a certain move, enter (n, n1, n2), which are the number n of the piece and the next two positions to be occupied, N1 and n2. This operation is used to update NodesOccupied and NodesUnoccupied and record the move for final program output. Of course, this step could be wrong, and if it is, there will be something else to pop it out of the list later.
def action(n, n1, n2) :
NodesOccupied += [n1, n2]
NodesOccupied.remove(n)
NodesUnoccupied.append(n)
NodesUnoccupied.remove(n1)
NodesUnoccupied.remove(n2)
temp_unoccupied = NodesUnoccupied[:]
solution.append([[n, n1, n2], temp_unoccupied])
Copy the codeThe fallback. If the program finds that it can’t go any further, that it reaches a leaf node, and the condition to complete the game is not met at this point, then it is not on the right path, at least in the last few steps. At this point, you need to go back to the previous selection position. The fallback mechanism requires that we have a stack to keep track of every place where choices are made, so I define a safe_stack. A fallback relies on this security state stack, and requires NodesUnoccupied and NodesUnoccupied to be refreshed and the last step of the action list to be displayed because this is not the correct move.
def get_back() :
NodesOccupied = safe_stack[-1] [0][:]
NodesUnoccupied = []
for i in range(15) :if i not in NodesOccupied:
NodesUnoccupied.append(i)
solution.pop()
Copy the codeThe main function
With the basic operations defined, we start implementing the main function.
The logic of the main function is simple: it loops through the safe state stack until there is only one space left on the board.
The code is as follows:
def main() :
There are four trees in total. For simplicity, execute them four times.
startPoints = [0.1.3.4]
# for startPoint in startPoints:
startPoint = startPoints[0]
NodesOccupied.append(startPoint)
NodesUnoccupied.remove(startPoint)
isAction = 1
while len(NodesUnoccupied) > 1:
if isAction:
temp_Occupied = NodesOccupied[:]
safe_stack.append([temp_Occupied, []])
for node in temp_Occupied:
options = getRoads(node)
for option in options:
safe_stack[-1] [1].append([node] + list(option))
if len(safe_stack[-1] [1]):
action(safe_stack[-1] [1] [0] [0], safe_stack[-1] [1] [0] [1], safe_stack[-1] [1] [0] [2])
isAction = 1
else:
if len(safe_stack) > 1:
safe_stack.pop()
safe_stack[-1] [1].pop(0)
get_back()
isAction = 0
else:
print('Fail.\n')
break
print('Success.\n')
for each in solution:
print(f'remove {each[0] [0]}, append {each[0] [1:]}, NodesUnoccupied: {each[1]}')
Copy the codeAt this point, the violence solver is done, and it prints out the first solution it has figured out:
Success.
remove 0, append [1, 3], NodesUnoccupied: [2, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 0]
remove 1, append [4, 8], NodesUnoccupied: [2, 5, 6, 7, 9, 10, 11, 12, 13, 14, 0, 1]
remove 3, append [6, 10], NodesUnoccupied: [2, 5, 7, 9, 11, 12, 13, 14, 0, 1, 3]
remove 4, append [7, 11], NodesUnoccupied: [2, 5, 9, 12, 13, 14, 0, 1, 3, 4]
remove 6, append [1, 3], NodesUnoccupied: [0, 2, 4, 5, 9, 12, 13, 14, 6]
remove 7, append [2, 4], NodesUnoccupied: [0, 5, 9, 12, 13, 14, 6, 7]
remove 8, append [6, 7], NodesUnoccupied: [0, 5, 9, 12, 13, 14, 8]
remove 11, append [12, 13], NodesUnoccupied: [0, 5, 9, 14, 8, 11]
remove 2, append [5, 9], NodesUnoccupied: [0, 14, 8, 11, 2]
remove 5, append [0, 2], NodesUnoccupied: [14, 8, 11, 5]
remove 12, append [8, 5], NodesUnoccupied: [14, 11, 12]
remove 13, append [11, 12], NodesUnoccupied: [14, 13]
remove 12, append [14, 13], NodesUnoccupied: [12]
Copy the codeRemove 0, append [1, 3], and NodesUnoccupied indicates that the grid is not pied. According to the program to give the guide, the final only one space, the game is completed.
Yuezih-playground /Hopscotch (github.com)