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

Research output: Contribution to journalArticle

Abstract

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.
Original languageEnglish
Pages (from-to)904-908
JournalJournal of Communication and Computer
Volume10
Issue number7
Publication statusPublished - Jul 2013

Fingerprint

Water
Programming
Denote
Breadth-first Search
Depth-first Search
Neuroscience
Diophantine equation
Heuristic Method
Subtraction
Search Methods
Congruence
Artificial Intelligence
Simplicity
Upper bound
Psychology

Citation

Man, Y.-K. (2013). A non-heuristic approach to the general two water jugs problem. Journal of Communication and Computer, 10(7), 904-908.

Keywords

  • Two water jugs problem
  • Non-heuristic approach
  • Diophantine equation
  • Problem-solving
  • Artificial intelligence