# 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.