Problema das três casas

O chamado problema das três casas, conhecido também como água, gás e eletricidade ou problema das três utilidades, é um clássico, que pode ser declarado como segue: Suponha que haja três casas em um plano (ou superfície de uma esfera) e cada uma precisa ser ligada às empresas de gás, água e eletricidade. O uso de uma terceira dimensão ou o envio de qualquer uma das conexões através de outra empresa ou casa não é permitido. Existe uma maneira de fazer todos os nove ligações sem qualquer uma das linhas que se cruzam? O problema é um quebra-cabeça matemático abstrato que impõe restrições que não existiriam em uma situação prática de engenharia.