# 三水桶等分8升水（javascript实现）

### 变量定义

``var FullBacket = [8,5,3]            //桶的最大容量 var states = [[8,0,0]];             //状态队列，js的数组已经已经有队列和堆栈的支持``

### 检测倒水操作是否可行

``function CanTakeDumpAction(curr,from,to){     if(from >= 0 && from < 3 && to >= 0 && to < 3){         if(from != to && curr[from] > 0 && curr[to] < FullBacket[to]){             return true;         }     }     return false; }``

### 倒水操作

``function DumpWater(curr,from,to){     var next = curr.slice();        //js对象为引用传值，这里要复制一份     var dump_water = FullBacket[to] - curr[to] > curr[from] ? curr[from] : FullBacket[to] - curr[to]            //倒水量的计算     next[from] -= dump_water;     next[to] += dump_water;     return next; }``

### 检测新状态是否已经出现过

``function IsStateExist(state){     for(var i = 0; i < states.length; i++){         if(state[0] == states[i][0] && state[1] == states[i][1] && state[2] == states[i][2]){             return true;         }     }     return false; }``

### 状态搜索主函数

``(function SearchState(states){     var curr = states[states.length - 1];     if(curr[0] == 4 && curr[1] == 4){            //找到正确解         var rs = ''         states.forEach(function(al){             rs += al.join(',') + ' -> ';         });         console.log(rs.substr(0,rs.length - 4))     }      for(var j = 0; j < 3; j++){                //所有的倒水方案即为桶编号的全排列         for(var i = 0; i < 3; i++){             if(i === 0 && j === 0)                 continue;             if(CanTakeDumpAction(curr,i,j)){                 var next = DumpWater(curr,i,j);                 if(!IsStateExist(next)){        //找到新状态                     states.push(next);                     SearchState(states);                     states.pop();                 }             }         }     } })(states);``

### 16组正确解

``8,0,0 -> 3,5,0 -> 0,5,3 -> 5,0,3 -> 5,3,0 -> 2,3,3 -> 2,5,1 -> 7,0,1 -> 7,1,0 -> 4,1,3 -> 4,4,0 8,0,0 -> 3,5,0 -> 3,2,3 -> 5,0,3 -> 5,3,0 -> 2,3,3 -> 2,5,1 -> 7,0,1 -> 7,1,0 -> 4,1,3 -> 4,4,0 8,0,0 -> 3,5,0 -> 3,2,3 -> 6,2,0 -> 6,0,2 -> 1,5,2 -> 0,5,3 -> 5,0,3 -> 5,3,0 -> 2,3,3 -> 2,5,1 -> 7,0,1 -> 7,1,0 -> 4,1,3 -> 4,4,0 8,0,0 -> 3,5,0 -> 3,2,3 -> 6,2,0 -> 6,0,2 -> 1,5,2 -> 1,4,3 -> 5,0,3 -> 5,3,0 -> 2,3,3 -> 2,5,1 -> 7,0,1 -> 7,1,0 -> 4,1,3 -> 4,4,0 8,0,0 -> 3,5,0 -> 3,2,3 -> 6,2,0 -> 6,0,2 -> 1,5,2 -> 1,4,3 -> 4,4,0 8,0,0 -> 3,5,0 -> 3,2,3 -> 6,2,0 -> 6,0,2 -> 1,5,2 -> 1,4,3 -> 0,5,3 -> 5,0,3 -> 5,3,0 -> 2,3,3 -> 2,5,1 -> 7,0,1 -> 7,1,0 -> 4,1,3 -> 4,4,0 8,0,0 -> 3,5,0 -> 3,2,3 -> 6,2,0 -> 6,0,2 -> 5,0,3 -> 5,3,0 -> 2,3,3 -> 2,5,1 -> 7,0,1 -> 7,1,0 -> 4,1,3 -> 4,4,0 8,0,0 -> 3,5,0 -> 3,2,3 -> 0,5,3 -> 5,0,3 -> 5,3,0 -> 2,3,3 -> 2,5,1 -> 7,0,1 -> 7,1,0 -> 4,1,3 -> 4,4,0 8,0,0 -> 5,0,3 -> 0,5,3 -> 3,5,0 -> 3,2,3 -> 6,2,0 -> 6,0,2 -> 1,5,2 -> 1,4,3 -> 4,4,0 8,0,0 -> 5,0,3 -> 5,3,0 -> 3,5,0 -> 3,2,3 -> 6,2,0 -> 6,0,2 -> 1,5,2 -> 1,4,3 -> 4,4,0 8,0,0 -> 5,0,3 -> 5,3,0 -> 2,3,3 -> 0,5,3 -> 3,5,0 -> 3,2,3 -> 6,2,0 -> 6,0,2 -> 1,5,2 -> 1,4,3 -> 4,4,0 8,0,0 -> 5,0,3 -> 5,3,0 -> 2,3,3 -> 2,5,1 -> 7,0,1 -> 7,1,0 -> 3,5,0 -> 3,2,3 -> 6,2,0 -> 6,0,2 -> 1,5,2 -> 1,4,3 -> 4,4,0 8,0,0 -> 5,0,3 -> 5,3,0 -> 2,3,3 -> 2,5,1 -> 7,0,1 -> 7,1,0 -> 4,1,3 -> 0,5,3 -> 3,5,0 -> 3,2,3 -> 6,2,0 -> 6,0,2 -> 1,5,2 -> 1,4,3 -> 4,4,0 8,0,0 -> 5,0,3 -> 5,3,0 -> 2,3,3 -> 2,5,1 -> 7,0,1 -> 7,1,0 -> 4,1,3 -> 4,4,0 8,0,0 -> 5,0,3 -> 5,3,0 -> 2,3,3 -> 2,5,1 -> 3,5,0 -> 3,2,3 -> 6,2,0 -> 6,0,2 -> 1,5,2 -> 1,4,3 -> 4,4,0 8,0,0 -> 5,0,3 -> 5,3,0 -> 2,3,3 -> 2,5,1 -> 0,5,3 -> 3,5,0 -> 3,2,3 -> 6,2,0 -> 6,0,2 -> 1,5,2 -> 1,4,3 -> 4,4,0``