1, Background
The water sorting puzzle I accidentally saw on the QQ applet hit 88 and couldn't get through. Just want to solve the problem with algorithm.
2, Water sorting puzzle
The basic rule is:
There are 4 parts of water for each color
The capacity of each cup is 4 parts,
No water can be poured into a full glass,
Any water can be poured into an empty cup,
Only water of the same color can be poured into a cup that is not full or empty,
Adjacent portions of water of the same color are one,
Pour a piece of water of the same color at a time unless the target cup is full
Finally, four parts of water of each color are in the same cup, that is, each cup is empty or has four parts of water of the same color
2, Problem construction
The process of playing games is a process of finding solutions to game problems. This game is a typical problem that can be solved by search.
To solve the problem by searching, we must first define the initial state and state space of the problem, the transition model (the action that can be taken and the state reached by each state), the target and the path consumption (in this problem, the last path consumption is 1).
import copy
class Puzzle(object):
def __init__(self,cup_num=0,capacity=0) -> None:
self.cup_num = cup_num #Number of cups
self.capacity = capacity #Cup capacity
self.empty_cup = 0
self.state = None
def create(self):
# Input status
self.cup_num = int(input("Number of cups:"))
self.capacity = int(input("Cup capacity:"))
cup_num = self.cup_num
capacity = self.capacity
self.state = []
for i in range(cup_num):
# Space separation color
# The cup is empty
water = input("The first%d A cup(From bottom to top): "%i).split()[:capacity]
if len(water) == 0:
self.empty_cup += 1
self.state.append(water)
return self.state
def readfile(self,file):
# Read status from file
with open(file,'r') as f:
self.cup_num = int(f.readline())
self.capacity = int(f.readline())
self.state = []
for i in range(self.cup_num):
water = f.readline().split()[:self.capacity]
if len(water) == 0:
self.empty_cup += 1
self.state.append(water)
return self.state
def get_successors(self):
# Get all subsequent States and actions
suc = []
for i in range(self.cup_num):
for j in range(self.cup_num):
if self.isAction((j,i)):
suc.append(((j,i),self.move((j,i))))
return suc
def isAction(self,act:tuple,state=None):
# Judge whether it is a legal action
# from j to i
j,i = act
if state == None:
state = self.state
return i!=j and len(state[j])>0 and len(state[i])<self.capacity and (len(state[i])==0 or state[j][-1]==state[i][-1])
# Two different cups and the original cup is not empty and the target cup is not full (the target cup is empty or the top color is the same)
def move(self,act:tuple):
# Act on the current state and generate a new state
j,i = act
state = copy.deepcopy(self.state)
while self.isAction(act,state):
state[i].append(state[j].pop())
# Move one piece of water at a time instead of one share
new_puzzle = Puzzle(self.cup_num,self.capacity)
new_puzzle.empty_cup = self.empty_cup
new_puzzle.state = state
return new_puzzle
def isRight(self)->bool:
# Is the target state
if self.state is None:
return False
for i in range(self.cup_num):
if len(self.state[i]) != 0 and len(self.state[i]) != self.capacity:
return False
elif len(self.state[i]) == self.capacity:
for j in range(1,self.capacity):
if self.state[i][j] != self.state[i][0]:
return False
return True
def print(self,cup_width=6, cup_interval=3):
# Print current status
if self.state is None:
print(None)
return None
width = cup_width
interval = cup_interval
space = " "*interval
a = ""
for i in range(self.cup_num):
a += ("#%d"%i).center(width+2)+space
print(a)
print()
for j in range(self.capacity-1,-1,-1):
a = ""
for i in range(self.cup_num):
if len(self.state[i]) > j:
color = self.state[i][j]
else:
color = "."
a += "|"+("%s"%color).center(width)+"|"+space
print(a)
a = ""
for i in range(self.cup_num):
a += "\\"+"_".center(width,"_")+"/"+space
print(a)
return None
Enter a simple question to test:
p.txt
4 4 1 3 2 2 2 3 1 3 2 1 1 3
test = Puzzle()
# test.create()
test.readfile("p.txt")
print(test.state)
test.print()
print(test.get_successors())
Output:
. represents null
[[], ['1', '3', '2', '2'], ['2', '3', '1', '3'], ['2', '1', '1', '3']] #0 #1 #2 #3 | . | | 2 | | 3 | | 3 | | . | | 2 | | 1 | | 1 | | . | | 3 | | 3 | | 1 | | . | | 1 | | 2 | | 2 | \______/ \______/ \______/ \______/ [((1, 0), <__main__.Puzzle object at 0x000001FC01DE8820>), ((2, 0), <__main__.Puzzle object at 0x000001FC01EE7310>), ((3, 0), <__main__.Puzzle object at 0x000001FC01F19D90>)]
To facilitate testing, write a simple question generator:
puzzle_generator.py
import random
cup_num = int(input("Number of cups:"))
capacity = int(input("Cup capacity:"))
empty_cup = int(input("Number of empty cups:"))
state = []
for i in range(cup_num):
if i < empty_cup:
state.append([])
else:
state.append([i]*capacity)
path = []
N = 100
for step in range(N):
i = random.randint(0,cup_num-1)
while len(state[i])==0:
i = random.randint(0,cup_num-1)
j = random.randint(0,cup_num-1)
while j == i or len(state[j]) == capacity:
j = random.randint(0,cup_num-1)
state[j].append(state[i].pop())
path.append((j,i))
for i in range(empty_cup):
while len(state[i])!=0:
j = random.randint(empty_cup,cup_num-1)
while j == i or len(state[j]) == capacity:
j = random.randint(empty_cup,cup_num-1)
state[j].append(state[i].pop())
path.append((j,i))
print(state)
with open("p.txt",'w') as f:
f.writelines([str(cup_num)+'\n',str(capacity)+'\n'])
sss = []
for cup in state:
a = ""
for w in cup:
a += str(w)+" "
sss.append(a+'\n')
f.writelines(sss)
3, Problem solving
1.BFS width first search strategy
The first solution I think of is direct violent search, because it is simple and easy to write. Although it is not elegant, it can be solved.
Why not use DFS depth first search? Because I consider that there will be some cyclic actions, such as A inverted B, B inverted A, resulting in deepening depth, no solution can be found, and DFS cannot guarantee the optimization.
BFS code is as follows:
def bfs(puzzle:Puzzle,attemp=100000):
ttt = 0
q = []
q.append(([],puzzle))
while len(q)>0:
path,pz = q.pop(0)
if pz.isRight():
print("%d states searched"%ttt)
return path,pz
for succ in pz.get_successors():
act,suc_pz = succ
q.append((path.copy()+[act],suc_pz))
ttt += 1
if (ttt>attemp):
print("Maximum number of times exceeded")
return None
print("unsolvable")
return None
Test:
test = Puzzle()
# test.create()
test.readfile("p.txt")
test.print()
a = bfs(test)
if a == None:
print("None!")
else:
print("%d steps"%len(a[0]))
print(a[0])
a[1].print()
Output:
#0 #1 #2 #3 | . | | 2 | | 3 | | 3 | | . | | 2 | | 1 | | 1 | | . | | 3 | | 3 | | 1 | | . | | 1 | | 2 | | 2 | \______/ \______/ \______/ \______/ 98 states searched 8 steps [(2, 0), (3, 0), (2, 3), (2, 0), (1, 2), (1, 0), (3, 1), (3, 2)] #0 #1 #2 #3 | 3 | | 1 | | 2 | | . | | 3 | | 1 | | 2 | | . | | 3 | | 1 | | 2 | | . | | 3 | | 1 | | 2 | | . | \______/ \______/ \______/ \______/
Soon, the result will come out in a minute!
The problem is simple!
However, when you count more cups, it slows down
4 cups, 2 empty cups, 2080 states to be searched
5 cups, 2 empty cups, 85219 states to be searched
6 cups and 2 empty cups. Search for more than 1000000 states
How can this work!
2.BFS and pruning
If you can't use BFS directly, then cut the branches
In the search, it is likely to encounter the situation that a is inverted B and B is inverted A. this situation is not helpful for the solution, so it can be cut directly
For example:
#A #B | . | | 3 | | 3 | | 3 | | 2 | | 4 | | 2 | | 2 | \______/ \______/
In this case, B - > A is a legal action, but after the reverse, a - > b is a legal action, and the reverse may occur
The code is as follows:
def bfs_prune(puzzle:Puzzle,attemp=1000000):
ttt = 0
q = []
q.append(([],puzzle))
while len(q)>0:
path,pz = q.pop(0)
if pz.isRight():
print("%d states searched"%ttt)
return path,pz
if len(path)<2 or (len(path)>=2 and not (path[-1][1] == path[-2][0] and path[-1][0] == path[-2][1])):
# prune
for succ in pz.get_successors():
act,suc_pz = succ
q.append((path.copy()+[act],suc_pz))
ttt += 1
if (ttt>attemp):
print("Maximum number of times exceeded")
return None
print("unsolvable")
return None
The test did work:
Same question
4 cups, 2 empty cups, 1599 states to be searched
Five cups, two empty cups, to search 60440 States
6 cups and 2 empty cups. Search for more than 1000000 states
Still not
It seems that the search strategy without information is not feasible, and heuristic search must be used
3. Heuristic search
For heuristic search, refer to artificial intelligence, a modern method, 3rd Edition
A * search
Design a heuristic function
The heuristic function is the lowest estimate of the cost from the current state to the target state, and the estimated cost is less than the actual cost (acceptable)
Starting from the relaxation problem, it is a common method to design heuristics.
At present, there are many constraints in game problems, and several conditions can be removed to get the relaxation problem.
I remove the condition that empty cups are limited, and assume that there are infinite empty cups.
So, what kind of cost estimate will you get?
#0 #1 #2 #3 #4 #5 #6 #7 #8 | . | | . | | 4 | | 1 | | . | | . | | . | | . | | . | | . | | 3 | | 3 | | 2 | | . | | . | | . | | . | | . | | 2 | | 2 | | 2 | | 4 | | 3 | | . | | 5 | | . | | . | | 1 | | 1 | | 1 | | 4 | | 3 | | 4 | | 5 | | 5 | | 5 | \______/ \______/ \______/ \______/ \______/ \______/ \______/ \______/ \______/
To fill a cup, first remove the different colors on the top.
There are many colors in a cup
1. Upper part of cup
For #0 cups, we obviously want to get a cup full of 1. Then, first of all, remove the upper part and pour out 2. At least one step is required.
For #1 cups, first pour out 2 and 3, which takes 2 steps.
Similarly, #2 need 3 steps, #3 need 2 steps
To get a cup full of 1, we can turn 1 upside down while removing the top of other cups
2. Cup bottom
#0 #1 #2 cups have 1 at the bottom. We can't expect a cup full of 1 for each cup. Three cups need 1 of two cups to be poured into another cup, which requires at least 2 steps
There is only one color in a cup
This kind of cup has only the bottom and no upper part
When the cup is not full:
For #4 cups, there is no 3 at the bottom of other cups. Just let other cups move 3 and put them in #4 cups (instead of infinite empty cups), without consuming steps
For #5 cups, #3 there are 4 at the bottom of the cup. At least one step is needed to put them into a cup
For #6 #7 #8 cups, take at least 2 steps to put 5 into one cup
Cup full:
No operation is required at the cost of 0
However, in the actual test, I found that calculating the cost of a full cup as - 1 will greatly reduce the number of search states.
Heuristic function code
class Puzzle(object):
...
def A_star_cost(self)->int:
#smaller is better
# Acceptable and consistent heuristics
c = 0
bottom = {}
for cup in self.state:
if len(cup)==0:
continue
bottom[cup[0]] = bottom.get(cup[0],-1) + 1
w0 = cup[0]
all_same = 0
for i in range(1,len(cup)):
if cup[i] != w0:
w0 = cup[i]
c += 1
all_same = 1
if all_same == 0 and len(cup) == self.capacity:
c -= 1
if all_same == 0 and len(cup) < self.capacity and bottom[cup[0]]>=1:
c += 1
c += sum(bottom.values())
return c
A * search code
from queue import PriorityQueue
def A_star(puzzle:Puzzle,attemp=100000):
ttt = 0
q = PriorityQueue()
q.put((puzzle.A_star_cost(),[],puzzle))
while not q.empty():
score,path,pz = q.get()
if pz.isRight():
print("%d states searched"%ttt)
return path,pz
if len(path)<2 or (len(path)>=2 and not (path[-1][1] == path[-2][0] and path[-1][0] == path[-2][1])):
for succ in pz.get_successors():
act,suc_pz = succ
q.put((len(path)+suc_pz.A_star_cost(),path.copy()+[act],suc_pz))
ttt += 1
if (ttt>attemp):
print("Maximum number of times exceeded")
return None
print("unsolvable")
return None
test
89.txt
11 4 g r r b0 po g0 br po br y y g0 g o o g0 g y po br b0 po b o b b0 br r b y o b b0 g r g0
test = Puzzle()
# test.create()
test.readfile("89.txt")
test.print()
a = A_star(test)
if a == None:
print("None!")
else:
print("%d steps"%len(a[0]))
print(a[0])
a[1].print()
#0 #1 #2 #3 #4 #5 #6 #7 #8 #9 #10 | . | | . | | b0 | | po | | g0 | | g0 | | br | | o | | r | | b | | g0 | | . | | . | | r | | br | | y | | o | | po | | b | | br | | o | | r | | . | | . | | r | | g0 | | y | | o | | y | | po | | b0 | | y | | g | | . | | . | | g | | po | | br | | g | | g | | b0 | | b | | b | | b0 | \______/ \______/ \______/ \______/ \______/ \______/ \______/ \______/ \______/ \______/ \______/ 33 states searched 29 steps [(4, 0), (4, 1), (5, 0), (6, 4), (3, 6), (3, 4), (3, 0), (10, 0), (6, 3), (7, 5), (8, 10), (8, 4), (1, 6), (2, 8), (2, 1), (10, 1), (2, 10), (5, 2), (5, 10), (6, 5), (9, 7), (9, 2), (9, 5), (7, 9), (7, 3), (7, 8), (10, 6), (8, 10), (8, 9)] #0 #1 #2 #3 #4 #5 #6 #7 #8 #9 #10 | g0 | | r | | o | | po | | br | | y | | g | | . | | . | | b | | b0 | | g0 | | r | | o | | po | | br | | y | | g | | . | | . | | b | | b0 | | g0 | | r | | o | | po | | br | | y | | g | | . | | . | | b | | b0 | | g0 | | r | | o | | po | | br | | y | | g | | . | | . | | b | | b0 | \______/ \______/ \______/ \______/ \______/ \______/ \______/ \______/ \______/ \______/ \______/
97.txt
11 4 po o g y g0 o po g g b y o po po br r b g b0 o b0 y br b br y br r g0 b0 b0 g0 b g0 r r
#0 #1 #2 #3 #4 #5 #6 #7 #8 #9 #10 | . | | . | | y | | g | | o | | r | | o | | b | | r | | g0 | | r | | . | | . | | g | | po | | y | | br | | b0 | | br | | br | | b0 | | r | | . | | . | | o | | o | | b | | po | | g | | y | | y | | b0 | | g0 | | . | | . | | po | | g0 | | g | | po | | b | | b0 | | br | | g0 | | b | \______/ \______/ \______/ \______/ \______/ \______/ \______/ \______/ \______/ \______/ \______/ 52 states searched 27 steps [(2, 0), (3, 2), (5, 1), (8, 1), (8, 5), (8, 0), (10, 1), (5, 8), (3, 5), (4, 3), (4, 0), (6, 3), (7, 4), (7, 8), (7, 0), (6, 7), (2, 6), (9, 10), (9, 7), (9, 10), (2, 9), (2, 5), (3, 9), (10, 3), (4, 10), (6, 4), (6, 10)] #0 #1 #2 #3 #4 #5 #6 #7 #8 #9 #10 | y | | r | | . | | g0 | | g | | po | | . | | b0 | | br | | o | | b | | y | | r | | . | | g0 | | g | | po | | . | | b0 | | br | | o | | b | | y | | r | | . | | g0 | | g | | po | | . | | b0 | | br | | o | | b | | y | | r | | . | | g0 | | g | | po | | . | | b0 | | br | | o | | b | \______/ \______/ \______/ \______/ \______/ \______/ \______/ \______/ \______/ \______/ \______/
The effect is very good and can solve the problem quickly
summary
This paper designs A heuristic function to solve the water sorting puzzle, and implements the A * search algorithm, which achieves very good results.