Problemas lógicos de cajas en ¿Cómo se llama este libro?

Índice

1. Problemas de cajas de Porcia
2. Motor lógico
3. Cofres
4. Solucionador
5. Problemas resueltos

Todo el código al que se hace referencia en esta entrada está disponible en un repositorio Github

1. Problemas de cajas de Porcia

El libro ¿Cómo se llama este libro?, de Raymond Smullyan es un clásico de las matemáticas recreativas. Entre sus numerosos problemas, hay un tipo relativo a cajas con inscripciones ciertas o falsas, y se debe encontrar la caja que contiene un retrato (o una daga) utilizando sólo la lógica. Este es el primero de esos problemas:

En El mercader de Venecia, de Shakespeare, Porcia tenia tres cofres ---uno de oro, otro de plata y otro de plomo---, dentro de uno de los cuales estaba el retrato de Porcia. El pretendiente tenía que elegir uno de los cofres y si tenía suerte (o inteligencia) elegiría el que tenía el retrato, pudiendo así pedir a Porcia por esposa. En la tapa de cada cofre había una inscripción para ayudar al pretendiente a elegir sabiamente.

Pero supongamos que Porcia quisiera elegir marido, no por su bondad, sino por su inteligencia. Tendría las siguientes inscripciones en los cofres:

Oro

EL RETRATO ESTÁ EN ESTE COFRE

Plata

EL RETRATO NO ESTÁ AQUÍ

Plomo

EL RETRATO NO ESTÁ EN EL COFRE DE ORO

Porcia explicó al pretendiente que de los tres enunciados, a lo sumo uno era verdad. ¿Cuál cofre debe de elegir el pretendiente?

Este problema puede resolverse utilizando como motor lógico el ya implementado para resolver el cluedo.

2. Motor lógico

Motor: El motor de programación por restricciones se encarga de crear y almacenar las variables y las restricciones
```
  const manager = new CPManager();
```
Variables booleanas: almacenan el dominio de una variable booleana, con nombre. Empiezan con los valores posibles true y false, estando en un valor indefinido. Si pierden un solo valor posible, su valor es el restante. Si pierden los dos valores, tienen un dominio vacío, lo que indica una configuración de variables y restricciones imposibles.
Listado de programa 1 Ejemplo de uso de una variable booleana
```
  const manager = new CPManager();
  const a = manager.Boolean("Variable a");
  console.log( a.canBeTrue() ); // true
  console.log( a.defined() ); // false
  a.remove(true);
  console.log( a.canBeTrue() ); // false
  console.log( a.defined() ); // true
  a.remove(false);
  console.log( a.defined() ); // false
  console.log( a.impossible() ); // true
```
Expresiones booleanas: pueden definirse entre variables y otras expresiones booleanas. Como las variables, tienen un dominio de valores true y false. Los componentes de una expresión afectan al dominio de la expresión. Además, si se restringe el dominio de una expresión, afecta al dominio de sus componentes.
Listado de programa 2 Las expresiones se ven afectadas por sus componentes
```
  const manager = new CPManager();
  const a = manager.Boolean("Variable a");
  const b = manager.Boolean("Variable b");
  const ayb = manager.And([a,b]);
  console.log( ayb.canBeTrue() ); // true
  a.remove(true);
  console.log( ayb.canBeTrue() ); // false
```
Listado de programa 3 Las expresiones afectan a sus componentes
```
  const manager = new CPManager();
  const a = manager.Boolean("Variable a");
  const b = manager.Boolean("Variable b");
  const aob = manager.Or([a,b]);
  a.remove(true);
  aob.remove(false);
  console.log( b.canBeFalse() ); // false
```
Entre las expresiones implementadas, se encuentran:
- And: true si todos los componentes son true.
- Or: true si algún componente es true.
- IfThen(a,b): true si a implica b.
- Iff(a,b): true si a y b tienen el mismo valor.
- SomeTrue(componentes,n): true si entre sus compnentes hay n variables (ni más, ni menos) con valor true.

3. Cofres

Cada cofre tiene un nombre y una variable booleana que indica si contiene o no algo. Posteriormente a su creación se le pueden añadir varias inscripciones.

Listado de programa 4 Inicio de la clase Cofre

class Cofre{
    constructor(manager,nombre){
        this._manager = manager;
        this._nombre = nombre;
        this._cofreLleno = manager.Boolean( "El cofre " + this._nombre + " está lleno" );
    }

    get nombre(){
        return this._nombre;
    }

    set inscripciones(ins){
        if( typeof this._inscripciones != "undefined" ){
            throw new Error("No se pueden cambiar las inscripciones de un cofre");
        }
   
        this._inscripciones = ins.slice(0);
    }

    get inscripciones(){
        return this._inscripciones.slice(0);
    }
    

    get cofreLleno(){
        return this._cofreLleno;
    }

    get manager(){
        return this._manager;
    }

    ....

Los cofres se crean todos juntos. Al crearse, una restricción se asegura que solo uno de ellos está lleno.

Listado de programa 5 Continuación de la clase Cofre

    ....

    static soloUnCofreLleno(cofres){
        var llenos = cofres.map( c => c.cofreLleno );
        let manager = cofres[0].manager;
        var soloUnoLleno = manager.SomeTrue(llenos,1).
            rename("Solo un cofre lleno en total").
            asTrue();
        return soloUnoLleno;
    }

    static creaCofres(CP,nombres){
        var ret = nombres.map( n => new Cofre(CP,n) );
        Cofre.soloUnCofreLleno(ret);
        return ret;
    }

}

El problema de Porcia descrito anteriormente se expresaría así:

    let CP = new CPManager();
    let cofres = Cofre.creaCofres(CP,["Oro","Plata","Plomo"]);
    let [cofreOro,cofrePlata,cofrePlomo] = cofres;

    cofreOro.inscripciones = [cofreOro.cofreLleno];
    cofrePlata.inscripciones = [CP.Not(cofrePlata.cofreLleno)];
    cofrePlomo.inscripciones = [CP.Not(cofreOro.cofreLleno)];

    CP.SomeTrue(cofres.map(c=>c.inscripciones[0]),0,1).
        rename( "Como mucho una inscripcion es cierta").
        asTrue();

En El mercader de Venecia, de Shakespeare, Porcia tenia tres cofres ---uno de oro, otro de plata y otro de plomo---, dentro de uno de los cuales estaba el retrato de Porcia. El pretendiente tenía que elegir uno de los cofres y si tenía suerte (o inteligencia) elegiría el que tenía el retrato, pudiendo así pedir a Porcia por esposa. En la tapa de cada cofre había una inscripción para ayudar al pretendiente a elegir sabiamente.

Pero supongamos que Porcia quisiera elegir marido, no por su bondad, sino por su inteligencia. Tendría las siguientes inscripciones en los cofres:

Oro

EL RETRATO ESTÁ EN ESTE COFRE

Plata

EL RETRATO NO ESTÁ AQUÍ

Plomo

EL RETRATO NO ESTÁ EN EL COFRE DE ORO

Porcia explicó al pretendiente que de los tres enunciados, a lo sumo uno era verdad. ¿Cuál cofre debe de elegir el pretendiente?

4. Solucionador

Para solucionar los problemas de cajas, debemos tener en cuenta que:

Los cofres pueden tener más de una inscripción. Las inscripciones pueden ser ciertas o falsas.
Puede interesar encontrar la caja que contiene el objeto, o encontrar una caja que esté vacía.

Hay dos formas de resolución:

Se puede intentar determinar si el problema es coherente llenando solo una caja. Para ello, se prueba a asignar a true la variable cofreLleno de cada cofre, y se observa si solo una de esas asignaciones es posible.
Se pueden probar todas las posiblidades cierto-falso de las inscripciones. Si para cualquier combinación posible la caja llena es siempre la misma (o la caja vacía, si es lo que se busca), esa es la solución.

La función CPAllPosibilies da valor a las variables pasadas, y devuelve un array con todas las combinaciones que no han resultado incoherentes (dejando alguna variable o expresión con el dominio vacío)

Listado de programa 6 Solucionador general de los problemas de Porcia

function porcia(cofres,buscarCofreLleno){
    const CP = cofres[0].manager;

    // POSIBILIDADES DE LLENADO DE CAJAS
    const llenos = cofres.map( c=> c.cofreLleno);
    const posibilidadesLlenos = CPAllPosibilities(llenos);
    if( posibilidadesLlenos.length == 1 ){
        const indice = posibilidadesLlenos[0].indexOf(buscarCofreLleno);
        if( indice < 0 ){
            return { error: "No se encuentra el cofre en la única combinación posible", cofre: undefined };
        }
        return {error: undefined, cofre: cofres[indice] };
    }

    // POSIBILIDADES DE INSCRIPCIONES CIERTAS
    const inscripciones = cofres.
          map(c=>c.inscripciones).
          reduce( (accum,value) => accum.concat(value) );
    const posibilidadesInscripciones = CPAllPosibilities(inscripciones,llenos);
    if( posibilidadesInscripciones.length < 1 ){
        return { error: "No hay ninguna posibilidad en las inscripciones", cofre: undefined };
    }
    for( let indice = 0 ; indice < cofres.length ; indice++ ){
        const lleno = posibilidadesInscripciones.map( p => p[indice] );
        if( lleno.every( b => b == buscarCofreLleno ) ){
            return {error: undefined, cofre: cofres[indice] };
        }
    }
    return { error: "No hay ninguna posibilidad válida en las inscripciones", cofre: undefined };
}

5. Problemas resueltos

5.1. Primer problema

Pero supongamos que Porcia quisiera elegir marido, no por su bondad, sino por su inteligencia. Tendría las siguientes inscripciones en los cofres:

Oro

EL RETRATO ESTÁ EN ESTE COFRE

Plata

EL RETRATO NO ESTÁ AQUÍ

Plomo

EL RETRATO NO ESTÁ EN EL COFRE DE ORO

Porcia explicó al pretendiente que de los tres enunciados, a lo sumo uno era verdad. ¿Cuál cofre debe de elegir el pretendiente?

function porciaI(){
    let CP = new CPManager();
    let cofres = Cofre.creaCofres(CP,["Oro","Plata","Plomo"]);
    let [cofreOro,cofrePlata,cofrePlomo] = cofres;

    cofreOro.inscripciones = [cofreOro.cofreLleno];
    cofrePlata.inscripciones = [CP.Not(cofrePlata.cofreLleno)];
    cofrePlomo.inscripciones = [CP.Not(cofreOro.cofreLleno)];

    CP.SomeTrue(cofres.map(c=>c.inscripciones[0]),0,1).
        rename( "Como mucho una inscripcion es cierta").
        asTrue();

    const solucion = porcia(cofres,true);
    console.log("Se debe elegir el cofre:" + solucion.cofre.nombre);
}

Se debe elegir el cofre:Plata

5.2. Segundo problema

El pretendiente eligió correctamente, así que se casaron y vivieron bastante felices... por lo menos durante algún tiempo. Pero un día Porcia pensó: «Aunque mi marido demostró una cierta inteligencia al elegir el cofre bueno, en realidad el problema no era tan difícil. Sin duda podía haber puesto un problema más difícil y haber conseguido un marido realmente inteligente.» Así pues se divorció inmediatamente de su marido decidida a casarse con otro más listo.

Esta vez en los tres consabidos cofres aparecían las siguientes inscripciones:

Oro

EL RETRATO NO ESTÁ EN EL COFRE DE PLATA

Plata

EL RETRATO NO ESTÁ EN ESTE COFRE

Plomo

EL RETRATO ESTÁ EN ESTE COFRE

Porcia explicó al pretendiente que por lo menos uno de los tres enunciados era verdadero y que por lo menos otro era falso.

¿En cuál de los cofres está el retrato?

function porciaII(){
    var CP = new CPManager();

    let cofres = Cofre.creaCofres(CP,["Oro","Plata","Plomo"]);
    let [cofreOro,cofrePlata,cofrePlomo] = cofres;

    cofreOro.inscripciones = [CP.Not(cofrePlata.cofreLleno)];
    cofrePlata.inscripciones = [CP.Not(cofrePlata.cofreLleno)];
    cofrePlomo.inscripciones = [cofrePlomo.cofreLleno];


    CP.SomeTrue(cofres.map(c=>c.inscripciones[0]),1,2).
        rename( "Al menos una inscripción verdad y otra mentira" ).
        asTrue();

    const solucion = porcia(cofres,true);
    console.log("Se debe elegir el cofre:" + solucion.cofre.nombre);
    
}

Se debe elegir el cofre:Oro

5.3. Tercer problema

Este problema incluye una novedad: los cofres tienen más de una inscripción. Además, se incluye una variable externa en dos de las inscripciones, no relativa a los cofres.

En ésta las tapas de los cofres tenían dos enunciados, y Porcia explicó que ninguna de ellas tenía más que un enunciado falso.

Oro

(1) EL RETRATO NO ESTÁ AQUÍ

(2) EL ARTISTA QUE HIZO EL RETRATO ES VENECIANO

Plata

(1) EL RETRATO NO ESTÁ EN EL DE ORO

(2) EL ARTISTA QUE HIZO EL RETRATO SÍ ES FLORENTINO

Plomo

(1) EL RETRATO NO ESTÁ AQUÍ

(2) EL RETRATO SÍ QUE ESTÁ EN EL COFRE DE PLATA

¿En qué cofre está el retrato?

function porciaIII(){
    let CP = new CPManager();
    let cofres = Cofre.creaCofres(CP,["Oro","Plata","Plomo"]);
    let [cofreOro,cofrePlata,cofrePlomo] = cofres;

    let veneciano = CP.Boolean( "El autor es veneciano");
    
    cofreOro.inscripciones = [CP.Not(cofreOro.cofreLleno), veneciano];
    cofrePlata.inscripciones = [CP.Not(cofreOro.cofreLleno), CP.Not(veneciano)];
    cofrePlomo.inscripciones = [CP.Not(cofrePlomo.cofreLleno), cofrePlata.cofreLleno];

    CP.Or(cofreOro.inscripciones).asTrue().rename("Al menos una frase verdadera en oro");
    CP.Or(cofrePlata.inscripciones).asTrue().rename("Al menos una frase verdadera en plata");
    CP.Or(cofrePlomo.inscripciones).asTrue().rename("Al menos una frase verdadera en plomo");

    const solucion = porcia(cofres,true);
    console.log("Se debe elegir el cofre:" + solucion.cofre.nombre);
}

Se debe elegir el cofre:Plata

5.4. Cuarto problema

Si el pretendiente pasaba la primera prueba era conducido a otra habitación en la cual había otros tres cofres, que también tenían dos inscripciones en la tapa. Porcia explicó que en una de las tapas los dos enunciados eran verdaderos; en otra ambos eran falsos, y en la tercera uno era verdadero y otro falso:

Oro

(1) EL RETRATO NO ESTÁ EN ESTE COFRE

(2) ESTÁ EN EL DE PLATA

Plata

(1) EL RETRATO NO ESTÁ EN EL DE ORO

(2) ESTÁ EN EL DE PLOMO

Plomo

(1) EL RETRATO NO ESTÁ EN ESTE COFRE

(2) ESTÁ EN EL DE ORO

¿En qué cofre estaba el retrato?

function porciaIV(){
    const CP = new CPManager();
    const cofres = Cofre.creaCofres(CP,["Oro","Plata","Plomo"]);
    const [cofreOro,cofrePlata,cofrePlomo] = cofres;

    
    cofreOro.inscripciones = [CP.Not(cofreOro.cofreLleno), cofrePlata.cofreLleno];
    cofrePlata.inscripciones = [CP.Not(cofreOro.cofreLleno), cofrePlomo.cofreLleno];
    cofrePlomo.inscripciones = [CP.Not(cofrePlomo.cofreLleno), cofreOro.cofreLleno];


    const posibilidades = permutaciones([
        cofreOro.inscripciones,
        cofrePlata.inscripciones,
        cofrePlomo.inscripciones
    ]).map(p => CP.And([
        CP.SomeTrue(p[0],0),
        CP.SomeTrue(p[1],1),
        CP.SomeTrue(p[2],2)
    ]));

    CP.SomeTrue(posibilidades,1).asTrue().rename("Una caja cierta, otra caja falsa, y otra caja a medias");
    
    const solucion = porcia(cofres,true);
    console.log("Se debe elegir el cofre:" + solucion.cofre.nombre);
}

function permutaciones(array){
    if( !array.length ){
        return [];
    }
    if( array.length == 1 ){
        return [array];
    }
    const head = array[0];
    const tail = array.slice(1);

    const subpermutaciones = permutaciones(tail);
    
    const ret = [];
    for( let i = 0 ; i < subpermutaciones.length ; i += 1 ){
        const subpermutacion = subpermutaciones[i];
        for( let p = 0 ; p < array.length ; p += 1 ){
            const nuevaPermutacion =
                  subpermutacion.slice(0,p).
                  concat([head]).
                  concat(subpermutacion.slice(p))
            ret.push(nuevaPermutacion)
        }
    }

    return ret;
}

Se debe elegir el cofre:Plomo

5.5. Quinto problema

En este problema una inscripción es auto-referente, ya que habla de la verdad de las propias inscripciones. En la implementación, se ha creado una variable booleana adicional, ya que una vez asignadas las inscripciones de los cofres no pueden cambiarse. Para enganchar esta variable con las inscripciones, se ha utilizado CPManager.Bind(a,b), que se asegura que los dominios de las variables a y b es el mismo (se implementa como un CPManager.Iff(a,b).asTrue()).

El pretendiente del cuento anterior pasó ambas pruebas y, muy contento, pidió a Porcia por esposa. Se casaron, vivieron felices y tuvieron una bellísima hija. Porcia III, a la que de aquí en adelante llamaremos simplemente Porcia. Ésta creció hasta convertirse en una bella e inteligente jovencita, exactamente igual que su mamá y que su abuelita, y que también decidió elegir marido por el método del cofre. ¡El enamorado tendría que pasar tres pruebas para conseguir su mano! Las tales pruebas eran bastante ingeniosas. Volvió a la técnica de su abuela de poner una sola inscripción en cada cofre, pero añadió un nuevo truco: explicaba al pretendiente que cada uno de los cofres lo había hecho uno de dos afamados artistas florentinos ---o Cellini o Bellini. Todos los cofres de Cellini tenían inscripción falsa mientras que Bellini siempre les ponía una inscripción verdadera.

En esta original prueba, el pretendiente (si contestaba a ciegas) tendría dos posibilidades sobre tres de acertar, en vez de una sobre tres. En vez de un retrato, Porcia metía una daga en uno de los cofres y dejaba los otros dos vacíos. Si el pretendiente conseguía evitar el cofre de la daga, podía pasar a la prueba siguiente. Las inscripciones rezaban así:

Oro

LA DAGA ESTÁ AQUÍ

Plata

ESTE COFRE ESTÁ VACÍO

Plomo

TODO LO MÁS UNO DE ESTOS COFRES LO HIZO BELLINI

¿Qué cofre tenía que elegir?

function porciaV(){
    const CP = new CPManager();
    const cofres = Cofre.creaCofres(CP,["Oro","Plata","Plomo"]);
    const [cofreOro,cofrePlata,cofrePlomo] = cofres;

    const comoMuchoUnCofreDiceLaVerdad = CP.Boolean("Como mucho un cofre lo hizo Bellini");
    cofreOro.inscripciones = [cofreOro.cofreLleno];
    cofrePlata.inscripciones = [CP.Not(cofrePlata.cofreLleno)];
    cofrePlomo.inscripciones = [comoMuchoUnCofreDiceLaVerdad];

    const inscripciones =
          cofreOro.inscripciones.
          concat(cofrePlata.inscripciones).
          concat(cofrePlomo.inscripciones);

    CP.Bind(
        comoMuchoUnCofreDiceLaVerdad,
        CP.SomeTrue(inscripciones,0,1)
    );

    const solucion = porcia(cofres,false);
    console.log( "Se debe abrir el cofre:" + solucion.cofre.nombre );
}

Se debe elegir el cofre:Plomo

5.6. Sexto problema

En ésta el pretendiente (si contestara sin pensar) tendría un cincuenta por ciento de posibilidades de acertar. Porcia le ponía sólo dos cofres, el de oro y el de plata; uno de ellos contenía su retrato (en esta prueba no utilizaba daga). Los cofres eran obra o de Cellini o de Bellini y en ellos se leía:

Oro

EL RETRATO NO ESTÁ AQUÍ

Plata

UNO Y NADA MÁS QUE UNO DE ESTOS DOS COFRES ES OBRA DE BELLINI

¿Cuál tenía que elegir el pretendiente para hallar el retrato?

function porciaVI(){
    var CP = new CPManager();

    const cofres = Cofre.creaCofres(CP,["Oro","Plata"]);
    const [cofreOro,cofrePlata] = cofres;

    const unoYSoloUnoEsDeBellini = CP.Boolean("Un cofre y solo uno es de Bellini");
    
    cofreOro.inscripciones = [ cofrePlata.cofreLleno ];
    cofrePlata.inscripciones = [ unoYSoloUnoEsDeBellini ];

    const todasLasInscripciones = cofreOro.inscripciones.concat(cofrePlata.inscripciones);
    
    CP.Bind( unoYSoloUnoEsDeBellini, CP.SomeTrue(todasLasInscripciones,1) );

    const solucion = porcia(cofres,true);
    console.log( "Se debe abrir el cofre:" + solucion.cofre.nombre );
}

Se debe elegir el cofre:Oro

5.7. Séptimo problema

Suponiendo que el pretendiente pasara las dos primeras pruebas, se le conducía a otra habitación en la que había de nuevo tres cofres, uno de oro, otro de plata y otro de plomo, hechos también o por Bellini o por Cellini. En esta prueba las oportunidades de acertar del pretendiente (en caso de que contestara a ciegas) eran una de cada tres. Porcia colocaba su retrato en uno de los tres y el pretendiente había de (1) elegir el cofre que tuviera el retrato y (2) adivinar el autor de cada uno de los cofres. Las inscripciones decían:

Oro

EL RETRATO ESTÁ AQUÍ

Plata

EL RETRATO ESTÁ AQUÍ

Plomo

POR LO MENOS DOS DE ESTOS TRES COFRES SON OBRA DE CELLINI

¿Cuál es la solución?

function porciaVII(){
    var CP = new CPManager();
    const cofres = Cofre.creaCofres(CP,["Oro","Plata", "Plomo"]);
    const [cofreOro,cofrePlata,cofrePlomo] = cofres;

    const alMenosDosCofresDeCellini = CP.Boolean( "Por lo menos dos cofres son de Cellini");

    cofreOro.inscripciones = [ cofreOro.cofreLleno ];
    cofrePlata.inscripciones = [ cofrePlata.cofreLleno ];
    cofrePlomo.inscripciones = [ alMenosDosCofresDeCellini ];

    const inscripciones = cofreOro.inscripciones.
          concat( cofrePlata.inscripciones ).
          concat(cofrePlomo.inscripciones);
    CP.Bind( alMenosDosCofresDeCellini, CP.SomeTrue(inscripciones,0,1));

    const solucion = porcia(cofres,true);
    console.log( "Se debe abrir el cofre:" + solucion.cofre.nombre );
}

Se debe elegir el cofre:Plomo