unit Unit1;
logigram puzzel oplossing
--------------------------------
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 |
--------------------------------------------------------
0 mary huiswerk taal 3 |
1 wim examen rekenen 5 |
2 peter proefwerk aardrijkskunde 6 |
3 anne tentamen geschiedenis 7 |
4 corrie overhoring biologie 9 |
--------------------------------------------------------
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, bijvoorbeeld: 2,0,4,3,1
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], enzovoorts.
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.
Die tabel bevat dus 120 rijtjes met alle permutaties van de cijfers 0..4
}
interface
uses
Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,
Dialogs, Grids, StdCtrls, Buttons, shellapi, ExtCtrls;
type
TForm1 = class(TForm)
BitBtn1: TBitBtn;
BitBtn2: TBitBtn;
StaticText1: TStaticText;
StringGrid1: TStringGrid;
Image1: TImage;
procedure FormCreate(Sender: TObject);
procedure BitBtn1Click(Sender: TObject);
procedure BitBtn2Click(Sender: TObject);
procedure Image1Click(Sender: TObject);
private
{ Private declarations }
public
{ Public declarations }
end;
var
Form1: TForm1;
implementation
{$R *.dfm}
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
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
k := 0;
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
result := 0;
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 := (cijfer(persoon(tentamen)) > cijfer(persoon(rekenen))) and //1a
(cijfer(persoon(tentamen)) < cijfer(corrie)) and //1b
(persoon(rekenen) <> corrie) and //1c
(persoon(huiswerk) <> peter) and //2a
(cijfer(peter) > cijfer(anne)) and //2b
(persoon(examen) <> peter) and //2c
(cijfer(peter) < cijfer(persoon(geschiedenis))) and //2d
(cijfer(peter) <> cijfer(persoon(examen)) + 6) and //2e
(cijfer(peter) <> cijfer(persoon(examen)) + 4) and //2f
(cijfer(persoon(examen)) + 6 <= 9) and //2g
(cijfer(persoon(proefwerk)) > cijfer(mary)) and //3a
(persoon(taal) <> mary) and //3b
(cijfer(persoon(proefwerk)) < cijfer(persoon(biologie))) and//3c
(persoon(proefwerk)<>wim) and (persoon(proefwerk)<>peter) and //3d
(wim = persoon(aardrijkskunde)) and //4a
(cijfer(wim) > cijfer(persoon(taal))) and //4b
(cijfer(wim) < cijfer(persoon(overhoring))) //4c
end;
procedure TForm1.FormCreate(Sender: TObject);
//delphi roept deze procedure aan bij opstarten
begin
makepermuts;
SetBeginstand;
end;
function Increment : boolean;
//verhoog de teller permutNr[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
begin;
statictext1.caption := 'computer zoekt...';
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;
procedure TForm1.Image1Click(Sender: TObject);
//davdata website link
begin
ShellExecute(0,'open','http://www.davdata.nl', nil, nil, SW_SHOWNORMAL);
end;
end.
