A non-heuristic approach to the general two water jugs problem

The two water jugs problem is a famous problem in recreational mathematics, problem-solving, artificial intelligence, neuroscience, computer programming and cognitive psychology. The methods of solutions are usually based on heuristics or search methods such as BFS (breadth first search) or DFS (depth first search), which could be time and memory consuming. In this paper, we present a non-heuristic approach to solve this problem, which can be modeled by the Diophantine equation mx + ny = d, where m, n denote the capacities of the jugs and d denotes the amount of water to be determined, with 0 < m < n and 0 < d < n. By simple additions and subtractions only, the special solutions (x, y) can be found very easily by using the non-Heuristic approach, which correspond to the number of times of the water jugs being fully filled in the whole water pouring process. Also, a simple formula for determining an upper bound on the total number of pouring steps involved is derived, namely 2(m + n – 2), based on the method of linear congruence. Due to its simplicity and novelty, this approach is suitable for either hand calculation or computer programming. Some illustrative examples are provided. Copyright © 2013 Journal of Communication and Computer.