unit Unit1;
{
   --------------------------------
   |  David E. Dirkse              |
   |  Castricum                    |
   |  the Netherlands              |
   |  e-mail: david.math@hccnet.nl |
   --------------------------------
  logigram:
---------------------------------------------------------------------------
5 personen: Mary, Wim, Peter, Anne en Corry,
5 opdrachten: huiswerk, examen, proefwerk, tentamen en overhoring
5 vakken: taal, rekenen, aardrijkskunde, geschiedenis en biologie
5 cijfers: 3,5,6,7 en 9
De voorwaarden zijn:
1) De persoon die het tentamen maakte, kreeg een hoger cijfer
   dan degene die moest rekenen, maar een lager cijfer dan Corry.
2) Peter is niet degene die huiswerk moest maken. Hij heeft echter
   een hoger cijfer dan Anne, maar een lager cijfer dan degene die
   geschiedenis deed. We weten ook dat Peter geen 4 en ook geen 6 punten
   meer kreeg dan de persoon die examen deed.
3) De leerlinge die het proefwerk maakte, kreeg een hoger cijfer
   dan Mary die geen taal deed, maar een lager cijfer dan degene
   die biologie deed.
4) Wim deed aardrijkskunde en kreeg een hoger cijfer dan degene
   die taal deed. Hij kreeg echter een lager cijfer dan de persoon
   die een overhoring had.
----------------------------------------------------------------------------
Welke opdracht, vak, cijfer hoort bij wie?

Dit programma berekent oplossingen.

Uitgangspunt is deze tabel:

--------------------------------------------------------------
                             kolom                            |
--------------------------------------------------------------
    0           1             2                3              |
persoon |   opdracht  |      vak        |   cijfer  |     rij |
--------------------------------------------------------------
mary      huiswerk       taal                 3     |      0  |
wim       examen         rekenen              5     |      1  |
peter     proefwerk      aardrijkskunde       6     |      2  |
anne      tentamen       geschiedenis         7     |      3  |
corrie    overhoring     biologie             9     |      4  |
--------------------------------------------------------------

Bij het zoekem maar oplossingen blijven de personen in kolom 0
op hun plaats staan.
De rijen in kolommen 1 t/m 3 verwisselen echter, tot een combinatie
is gevonden zonder conflicten.

De opdrachten, vakken, personen en cijfers worden in het programma
aangeduid met hun rij in de tabel hierboven, dus als 0,1,2,3 of 4.
Omdat de personen niet van plaats wisselen, vormen die tevens het
nummer van een rij.

Per kolom zijn er 5! = 120 volgorden van de opdrachten,vakken of cijfers.
Een volgorde wordt met een getal van 0..119 aangegeven.
Er zijn dus 3 van die getallen nodig, ze staan in array permNr[1..3].
(permNr staat voor permutatie nummer)
PermNr[2] geeft de permutatie aan van kolom 2.

In de tabel hierboven is van elke kolom permutatie 0 weergegeven.

De getallen permutNr[1], permutNr[2] en permutNr[3] vormen een telwerk.
Elke teller telt van 0..119, bij 120 gaat de teller over de kop naar 0
en verhoogt de volgende teller.
PermutNr[1] van 120 naar 0 verhoogt PermuNr[2], enzovoort.
Zo worden alle tellerstanden systematisch doorlopen.

Bij elke stand 0..119 hoort een volgorde van de elementen
in een kolom.

De omzetting van tellerstand naar permutatie (volgorde) gaat zo:
(stel dat we permutatie nummer 88 willen berekenen)

   maak eerst permutatie 0 , dat is 0 1 2 3 4
   deel 88 door 24 = 3  (88 div 24 = 3)    opm. 24 = 4!
   pak het 3e element uit de rij, dat is de -3-
   de rest bij deling van 88 door 24 = 16   (88 mod 24 = 16)
   haal de 3 weg uit de rij, dat levert de nieuwe rij 0 1 2 4 x
   deel 16 door  6 , 16 div 6 = 2
   neem het 2e element uit de rij, dat is de -2-
   16 mod 6 = 4   opm. 6 = 3!
   haal de 2 weg uit de rij, dat levert 0 1 4 x x
   4 div 2 = 2
   neem 2e getal uit de rij, dat is de -4-
   4 mod 2 = 0
   haal de 4 weg uit de rij, dat levert 0 1 x x x
   0 div 1 = 0
   neem 0e getal uit de rij, dat is de -0-
   de nieuwe rij wordt 1 x x x x
   pak nu het overgebleven getal, de -1-
   De volgorde nummer 88 is dus 3 2 4 0 1

Wordt deze volgorde toegepast op de kolom "opdracht" dan wordt die kolom:

   tentamen
   examen
   overhoring
   huiswerk
   examen

Maar de volgorde kan natuurlijk ook op andere kolommen slaan.

Dat achtereenvolgens wordt gedeeld door 24, 6, 3 en 1 zit zo:
er zijn 24 permutaties van 4 elementen. Deze kunnen als modulo 24
teller worden beschouwd.
Bij de eerste 24 permutaties zal de -0- voorop staan.
Bij permutaties 24..47 zal de 1 voorop staan. Enzovoort.

getal div 24 bepaalt dus het meest linkse element.
We verwijderen dit cijfer uit de rij 0 1 2 3 4, want het mag niet
opnieuw worden gekozen.
getal mod 24 is de rest bij deling en met dit getal gaan we verder.
Er zijn nu nog 4 cijfers te bepalen.
De laagste 3 vormen een modulo 3! = 6 teller zodat het hoogste cijfer
wordt bepaald door rest div 6.
En rest = rest mod 6 is wat overblijft.
Elk gevonden getal verwijderen we uit de rij.
Tenslotte wordt het laatste, overgebleven, getal aan de volgorde toegevoegd.

Om niet steeds dezelfde permutaties te hoeven berekenen wordt de tabel
permuts[0..4,0..119] bij het starten van het programma gevuld.

}

interface

uses
  Windows, Messages, SysUtils, Classes, Graphics, Controls, Forms, Dialogs,
  StdCtrls, Buttons, Grids;

{door Delphi gedefinieerde typen en variabelen}

type
  TForm1 = class(TForm)
    StringGrid1: TStringGrid;
    StaticText1: TStaticText;
    BitBtn1: TBitBtn;
    BitBtn2: TBitBtn;
    Button1: TButton;
    procedure FormCreate(Sender: TObject);
    procedure Button1Click(Sender: TObject);
    procedure BitBtn2Click(Sender: TObject);
    procedure BitBtn1Click(Sender: TObject);
  private
    { Private declarations }
  public
    { Public declarations }
  end;

var
  Form1: TForm1;

implementation

{$R *.DFM}

{door programmeur ingevoerde typen en variabelen}

type Tstring5 =  array[0..4] of string;
     Tactivity = record
                  rij : byte;           //plaats in de tabel hierboven
                  kolom : byte;
                 end;

const Spersonen   : Tstring5 =          //inhoud van de velden in tabel
                   ('mary','wim','peter','anne','corrie');
      Svakken     : Tstring5 =
                   ('taal','rekenen','aardrijkskunde','geschiedenis','biologie');
      Sopdrachten : Tstring5 =
                   ('huiswerk','examen','proefwerk','tentamen','overhoring');
      Scijfers    : Tstring5 =
                   ('3','5','6','7','9');

      huiswerk      : Tactivity = (rij:0; kolom:1); //plaats in de tabel
      examen        : Tactivity = (rij:1; kolom:1);
      proefwerk     : Tactivity = (rij:2; kolom:1);
      tentamen      : Tactivity = (rij:3; kolom:1);
      overhoring    : Tactivity = (rij:4; kolom:1);
      taal          : Tactivity = (rij:0; kolom:2);
      rekenen       : Tactivity = (rij:1; kolom:2);
      aardrijkskunde: Tactivity = (rij:2; kolom:2);
      geschiedenis  : Tactivity = (rij:3; kolom:2);
      biologie      : Tactivity = (rij:4; kolom:2);

      mary = 0;     //plaats in de kolom
      wim = 1;
      peter = 2;
      anne = 3;
      corrie = 4;

var permutNr : array[1..3] of byte; //hold permutation-index of columns
    permuts  : array[0..4,0..119] of byte;

    getal : byte = 0;   //alleen voor testen van permutaties
    opl   : byte;       //nummer van de oplossing

{oplossing
 persoon - vak - opdracht - cijfer .....vormen een telwerk
 verhoog steeds het telwerk (= volgende permutatie) en test voor conflicten
}

procedure makepermuts;
//maak alle permutaties in array permuts[0..4,0..119]
const delers : array[0..3] of byte = (24,6,2,1);
var i,j,k,rest,quot : byte;
    pel : array[0..4] of byte; //pel : permutatie van elementen 01234
begin
 for j := 0 to 119 do
  begin
   for i := 0 to 4 do pel[i] := i;//set permutatie 0 = 01234
   rest := j;
   for i := 0 to 3 do
    begin                         //maak permutatie j
     quot := rest div delers[i];
     rest:= rest mod delers[i];
     permuts[i,j] := pel[quot];
     for k := quot to 3 do pel[k] := pel[k+1]; //shift elements down
     pel[4] := 0;
    end;
   permuts[4,j] := pel[0];//overblijvende getal
  end;//for j
end;

procedure setCells;
//vul de tabel volgens permtNr[1..3]
var i,j,k : byte;
begin
 with form1.stringgrid1 do
  for i := 0 to 3 do        //kolommen
   begin
     if i <> 0 then k := permutNr[i];
     for j := 0 to 4 do     //rijen
     case i of
      0 : cells[i,j] := Spersonen[j];
      1 : cells[i,j] := Sopdrachten[permuts[j,k]];
      2 : cells[i,j] := Svakken[permuts[j,k]];
      3 : cells[i,j] := Scijfers[permuts[j,k]];
     end;//case
    end;
end;

procedure setBeginstand;
var i : byte;
begin
 for i := 1 to 3 do permutNr[i] := 0;
 setCells;
 form1.statictext1.caption := 'beginstand';
 opl := 0;
end;

function cijfer(n : byte) : byte;
//n: 0..4
//bepaal cijfer in rij n
var k : byte;
begin
 k := permuts[n,permutNr[3]];
 result := strtoint(Scijfers[k]);
end;

function persoon(a : Tactivity) : byte;
//bepaal persoon van activiteit a
var i,kolom,rij,k : byte;
begin
 kolom := a.kolom;
 rij := a.rij;

//--zoek rij nr in kolom

 k := permutNr[kolom];
 for i := 0 to 4 do
  if permuts[i,k] = rij then result := i
end;

function checkOK : boolean;
//test of aan voorwaarden is voldaan
begin
 result := true;

//voorwaarde 1a

 if cijfer(persoon(tentamen)) <= cijfer(persoon(rekenen)) then
  begin
   result := false; exit;
  end;

//voorwaarde 1b

  if cijfer(persoon(tentamen)) >= cijfer(corrie) then
   begin
    result := false; exit;
   end;

//voorwaarde 2a

  if persoon(huiswerk) = peter then
   begin
    result := false; exit;
   end;

//voorwaarde 2b

  if cijfer(peter) <= cijfer(anne) then
   begin
    result := false; exit;
   end;

//voorwaarde 2b

 if cijfer(peter) >= cijfer(persoon(geschiedenis)) then
  begin
   result := false; exit;
  end;

//voorwaarde 2c

 if cijfer(peter) = cijfer(persoon(examen)) + 6 then
  begin
   result := false; exit;
  end;

//voorwaarde 2d

 if cijfer(peter) = cijfer(persoon(examen)) + 4 then
  begin
   result := false; exit;
  end;

//voorwaarde 3a

 if cijfer(persoon(proefwerk)) <= cijfer(mary) then
  begin
   result := false; exit;
  end;

//voorwaarde 3b

 if persoon(taal) = mary then
  begin
   result := false; exit;
  end;

//voorwaarde 3c

 if cijfer(persoon(proefwerk)) >= cijfer(persoon(biologie)) then
  begin
   result := false; exit;
  end;

//voorwaarde 3d

 if (persoon(proefwerk) = wim) or (persoon(proefwerk) = peter) then
  begin
   result := false; exit;
  end;
  
//voorwaarde 4a

 if wim <> persoon(aardrijkskunde) then
  begin
   result := false; exit;
  end;

//voorwaarde 4b

 if cijfer(wim) <= cijfer(persoon(taal)) then
  begin
   result := false; exit;
  end;

//voorwaarde 4c

 if cijfer(wim) >= cijfer(persoon(overhoring)) then
  begin
   result := false; exit;
  end;
//---------------
end;

procedure TForm1.FormCreate(Sender: TObject);
//delphi roept deze procedure aan bij opstarten
begin
 makepermuts;
 SetBeginstand;
end;

procedure TForm1.Button1Click(Sender: TObject);
//debugging only
begin
 getal := 0;
 repeat
  showmessage(inttostr(permuts[0,getal])+inttostr(permuts[1,getal])+
              inttostr(permuts[2,getal])+inttostr(permuts[3,getal])+
              inttostr(permuts[4,getal]));
  inc(getal);
 until getal = 120;
end;

function Increment : boolean;
//verhoog de teller permutNt[1..3]
//carry = overdracht, verhogen volgende positie
var carry : boolean;
    i : byte;
begin
  carry := true;
  for i := 1 to 3 do
   begin
    if carry then inc(permutNr[i]);
    if permutNr[i] = 120 then permutNr[i] := 0
    else carry := false;
   end;//for
 result := carry;
end;

procedure TForm1.BitBtn2Click(Sender: TObject);
//aanroep bij klikken op knop "oplossen"
//zoeken naar oplossingen
var i : byte;
    carry : boolean;
begin;
 statictext1.caption := 'computer zoekt...';
 carry := false;
 repeat
  if checkOK then
   begin
    inc(opl);
    statictext1.caption := 'oplossing gevonden'+' : '+inttostr(opl);
    setCells;
    increment;
    exit;
   end;
 until increment;//until overflow
 statictext1.caption := 'einde';
 setbeginstand;
end;

procedure TForm1.BitBtn1Click(Sender: TObject);
//aanroep bij klokken op knop "beginstand" 
begin
 setbeginstand;
end;

end.