Sudoku

[Puzzle]

Code: Selecteer alles

// File: ProfilerTerm.h
// Date: 17 December 2006.
// Version: 197 microseconds on PowerMac G3/233 MHz.
//
// Copyright (c) 2006 Cliff Huylebroeck. All Rights Reserved.
//
// Permission to use, copy, modify, and distribute this software
// and its documentation for NON-COMMERCIAL purposes and without
// fee is hereby granted provided that this copyright notice
// appears in all copies.
//
// Cliff Huylebroeck MAKES NO REPRESENTATIONS OR WARRANTIES ABOUT THE
// SUITABILITY OF THE SOFTWARE, EITHER EXPRESS OR IMPLIED, INCLUDING BUT
// NOT LIMITED TO THE IMPLIED WARRANTIES OF MERCHANTABILITY, FITNESS FOR
// a PARTICULAR PURPOSE, OR NON-INFRINGEMENT. Cliff Huylebroeck SHALL NOT
// BE LIABLE FOR ANY DAMAGES SUFFERED BY LICENSEE AS A RESULT OF USING,
// MODIFYING OR DISTRIBUTING THIS SOFTWARE OR ITS DERIVATIVES.

#pragma once

__declspec(dllimport) extern pascal void ProfilerTerm();

[Puzzle]

Code: Selecteer alles

// File: Progressie.cp
// Date: 10 Januari 2007.
// Version: 197 microseconds on PowerMac G3/233 MHz.
//
// Copyright (c) 2006 Cliff Huylebroeck. All Rights Reserved.
//
// Permission to use, copy, modify, and distribute this software
// and its documentation for NON-COMMERCIAL purposes and without
// fee is hereby granted provided that this copyright notice
// appears in all copies.
//
// Cliff Huylebroeck MAKES NO REPRESENTATIONS OR WARRANTIES ABOUT THE
// SUITABILITY OF THE SOFTWARE, EITHER EXPRESS OR IMPLIED, INCLUDING BUT
// NOT LIMITED TO THE IMPLIED WARRANTIES OF MERCHANTABILITY, FITNESS FOR
// a PARTICULAR PURPOSE, OR NON-INFRINGEMENT. Cliff Huylebroeck SHALL NOT
// BE LIABLE FOR ANY DAMAGES SUFFERED BY LICENSEE AS A RESULT OF USING,
// MODIFYING OR DISTRIBUTING THIS SOFTWARE OR ITS DERIVATIVES.

#include "Progressie.h"

#include "Debug.h"
#include "DrawString.h"
#include "ExitToShell.h"
#include "InitFonts.h"
#include "InitGraf.h"
#include "InitWindows.h"
#include "MoveTo.h"
#include "NewCWindow.h"
#include "nil.h"
#include "SetPort.h"
#include "TextMode.h"
#include "TickCount.h"

QDGlobals Progressie::s_qd;

p_GrafPort Progressie::s_venster=nil;

n4 Progressie::s_eerst;

n4 Progressie::s_laatst;

n4 Progressie::s_gemiddeld;

void Progressie::MaakGetal(n4 getal,
                           cp_n1 tekst)
{
    *tekst=0;
    n1 k;
    if (getal<10)
        {
        k=static_cast<n1>(48+getal);
        }
    else
        {
        n4 d=1000000000;
        n1 machtVan10=9;
        while (d>getal)
            {
            machtVan10--;
            d/=10;
            }
        while (machtVan10)
            {
            c_n1 q=static_cast<n1>(getal/d);
            getal%=d;
            c_n1 k=static_cast<n1>(48+q);
            tekst[0]++;
            tekst[tekst[0]]=k;
            machtVan10--;
            d/=10;
            }
        c_n1 q=static_cast<n1>(getal/d);
        getal%=d;
        k=static_cast<n1>(48+q);
        }
    tekst[0]++;
    tekst[tekst[0]]=k;
}

void Progressie::Init()
{
    InitGraf(&s_qd.thePort);
    InitFonts();
    InitWindows();
    c_Rect r=
        {
        50,
        10,
        100,
        100
        };
    s_venster=::NewCWindow(nil,
                           &r,
                           "\pSudoku",
                           true,
                           0,
                           reinterpret_cast<p_GrafPort>(-1),
                           false,
                           0);
    if (!s_venster)
        {
        Debug::Exit();
        }
    ::SetPort(s_venster);
    ::TextMode(0);
}

void Progressie::Herbegin()
{
    s_eerst=::TickCount();
    s_laatst=s_eerst;
    ::MoveTo(h,
             v1);
    ::DrawString("\p          ");
    ::MoveTo(h,
             v2);
    ::DrawString("\p          ");
}

bool Progressie::ErIsEenSecondeVoorbij()
{
    c_n4 nu=::TickCount();
    if (nu-s_laatst<60)
        {
        return false;
        }
    s_laatst=nu;
    return true;
}

void Progressie::Schrijf(n4 getal)
{
    n1 tekst[11];
    MaakGetal(getal,
              tekst);
    ::MoveTo(h,
             v1);
    ::DrawString(tekst);
    c_n4 verschil=s_laatst-s_eerst;
    if (!verschil)
        {
        return;
        }
    c_n4 gemiddelde=getal*60/verschil;
    MaakGetal(gemiddelde,
              tekst);
    tekst[0]++;
    tekst[tekst[0]]=32;
    ::MoveTo(h,
             v2);
    ::DrawString(tekst);
}

[Puzzle]

Code: Selecteer alles

// File: Progressie.h
// Date: 10 Januari 2007.
// Version: 197 microseconds on PowerMac G3/233 MHz.
//
// Copyright (c) 2006 Cliff Huylebroeck. All Rights Reserved.
//
// Permission to use, copy, modify, and distribute this software
// and its documentation for NON-COMMERCIAL purposes and without
// fee is hereby granted provided that this copyright notice
// appears in all copies.
//
// Cliff Huylebroeck MAKES NO REPRESENTATIONS OR WARRANTIES ABOUT THE
// SUITABILITY OF THE SOFTWARE, EITHER EXPRESS OR IMPLIED, INCLUDING BUT
// NOT LIMITED TO THE IMPLIED WARRANTIES OF MERCHANTABILITY, FITNESS FOR
// A PARTICULAR PURPOSE, OR NON-INFRINGEMENT. Cliff Huylebroeck SHALL NOT
// BE LIABLE FOR ANY DAMAGES SUFFERED BY LICENSEE AS A RESULT OF USING,
// MODIFYING OR DISTRIBUTING THIS SOFTWARE OR ITS DERIVATIVES.

#pragma once

#include "bool.h"
#include "GrafPort.h"
#include "Link.h"
#include "n4.h"
#include "QDGlobals.h"
#include "z2.h"

// opm: alle Progressie-aanroepen moeten in een "if (progressie)" staan.
// Herbegin mag alleen na Init.
// ErIsEenSecondeVoorbij mag alleen na Herbegin.
// Schrijf mag alleen na ErIsEenSecondeVoorbij.

c_bool progressie=PROGRESSIE;

class Progressie;
    typedef Progressie* p_Progressie;
    typedef const p_Progressie cp_Progressie;
typedef const Progressie c_Progressie;
    typedef c_Progressie* pc_Progressie;
    typedef const pc_Progressie cpc_Progressie;
typedef Progressie& r_Progressie;
typedef p_Progressie& rp_Progressie;
typedef cp_Progressie& rcp_Progressie;
typedef c_Progressie& rc_Progressie;
typedef pc_Progressie& rpc_Progressie;
typedef cpc_Progressie& rcpc_Progressie;

class Progressie
{
private:
    static c_z2 h=10;
    static c_z2 v1=20;
    static c_z2 v2=40;
    static QDGlobals s_qd;
    static p_GrafPort s_venster;
    static n4 s_eerst;
    static n4 s_laatst;
    static n4 s_gemiddeld;
    static void MaakGetal(n4 getal,
                          p_n1 tekst);
public:
    static void Init();
    static void Herbegin();
    static bool ErIsEenSecondeVoorbij();
    static void Schrijf(n4 getal);
};

[Puzzle]

Code: Selecteer alles

// File: Puzzel.cp
// Date: 17 December 2006.
// Version: 197 microseconds on PowerMac G3/233 MHz.
//
// Copyright (c) 2006 Cliff Huylebroeck. All Rights Reserved.
//
// Permission to use, copy, modify, and distribute this software
// and its documentation for NON-COMMERCIAL purposes and without
// fee is hereby granted provided that this copyright notice
// appears in all copies.
//
// Cliff Huylebroeck MAKES NO REPRESENTATIONS OR WARRANTIES ABOUT THE
// SUITABILITY OF THE SOFTWARE, EITHER EXPRESS OR IMPLIED, INCLUDING BUT
// NOT LIMITED TO THE IMPLIED WARRANTIES OF MERCHANTABILITY, FITNESS FOR
// a PARTICULAR PURPOSE, OR NON-INFRINGEMENT. Cliff Huylebroeck SHALL NOT
// BE LIABLE FOR ANY DAMAGES SUFFERED BY LICENSEE AS A RESULT OF USING,
// MODIFYING OR DISTRIBUTING THIS SOFTWARE OR ITS DERIVATIVES.

#include "Puzzel.h"

#include "BlockMove.h"
#include "Coordinaten.h"
#include "Debug.h"
#include "nil.h"
#include "RandomGenerator.h"

#if PROFILE_ALLES
    #pragma profile on
#endif

Coordinaten Puzzel::s_coordinaten[aVakken];

n1 Puzzel::s_rij[puzzelGrootte][puzzelGrootte];

n1 Puzzel::s_kolom[puzzelGrootte][puzzelGrootte];

n1 Puzzel::s_kot[puzzelGrootte][puzzelGrootte];

n2 Puzzel::s_cijferBit[aCijferBit];

n1 Puzzel::s_enige[aCombinaties];

n1 Puzzel::s_aCijfers[aCombinaties];

n1 Puzzel::s_cijfers[aCombinaties][puzzelGrootte];

n2 Puzzel::s_cijferBits[aCombinaties][puzzelGrootte];

n1 Puzzel::s_willekeurig[aCombinaties];

n2 Puzzel::s_willekeurigBit[aCombinaties];

Puzzel Puzzel::s_leeg(true);

void Puzzel::Init()
{
    Init_Coordinaten();
    Init_Indexen();
    Init_CijferBit();
    Init_Enige();
    Init_Cijfers();
    Init_Willekeurig();
    s_leeg.MaakLeeg();
}

void Puzzel::Init_Coordinaten()
{
    for (n1 index=0;index<aVakken;index++)
        {
        r_Coordinaten c=coordinaten[index];
        r_Coordinaten d=s_coordinaten[index];
        d.rij=c.rij;
        d.kolom=static_cast<n1>(offsetKolom+c.kolom);
        d.kot=static_cast<n1>(offsetKot+c.kot);
        }
}

void Puzzel::Init_Indexen()
{
    n1 aInRij[puzzelGrootte];
    n1 aInKolom[puzzelGrootte];
    n1 aInKot[puzzelGrootte];
    for (n1 i=0;i<puzzelGrootte;i++)
        {
        aInRij[i]=0;
        aInKolom[i]=0;
        aInKot[i]=0;
        }
    for (n1 kot_rij=0;kot_rij<aKot;kot_rij++)
        {
        for (n1 kot_kolom=0;kot_kolom<aKot;kot_kolom++)
            {
            c_n1 kot=MaakIndex(kot_rij,
                               kot_kolom);
            for (n1 kot_sub_r=0;kot_sub_r<kotGrootte;kot_sub_r++)
                {
                c_n1 rij=MaakIndex(kot_rij,
                                   kot_sub_r);
                for (n1 kot_sub_k=0;kot_sub_k<kotGrootte;kot_sub_k++)
                    {
                    c_n1 kolom=MaakIndex(kot_kolom,
                                         kot_sub_k);
                    c_n1 index=MaakIndex2(rij,
                                          kolom);
                    r_Coordinaten c=coordinaten[index];
                    s_rij[c.rij][aInRij[c.rij]++]=index;
                    s_kolom[c.kolom][aInKolom[c.kolom]++]=index;
                    s_kot[c.kot][aInKot[c.kot]++]=index;
                    }
                }
            }
        }
}

void Puzzel::Init_CijferBit()
{
    for (n1 cijfer=1;cijfer<=puzzelGrootte;cijfer++)
        {
        s_cijferBit[cijfer]=MaakCijferBit(cijfer);
        }
}

void Puzzel::Init_Enige()
{
    for (n2 j=0;j<aCombinaties;j++)
        {
        s_enige[j]=0;
        }
    n2 binairGetalMet1Bit=1;
    for (n1 cijfer=1;cijfer<=puzzelGrootte;cijfer++)
        {
        s_enige[binairGetalMet1Bit]=cijfer;
        binairGetalMet1Bit<<=1;
        }
}

void Puzzel::Init_Cijfers()
{
    for (n2 j=0;j<aCombinaties;j++)
        {
        s_aCijfers[j]=0;
        for (n1 cijfer=1;cijfer<=puzzelGrootte;cijfer++)
            {
            c_n2 cijferBit=s_cijferBit[cijfer];
            if (!(j&cijferBit))
                {
                continue;
                }
            s_cijfers[j][s_aCijfers[j]]=cijfer;
            s_cijferBits[j][s_aCijfers[j]]=cijferBit;
            s_aCijfers[j]++;
            }
        }
}

void Puzzel::Init_Willekeurig()
{
    for (n2 j=0;j<aCombinaties;j++)
        {
        s_willekeurig[j]=s_cijfers[j][0];
        s_willekeurigBit[j]=s_cijferBits[j][0];
        }
}

Puzzel::Puzzel(bool)
{
}

Puzzel::Puzzel()
{
    ::BlockMove(&s_leeg,
                this,
                sizeof(Puzzel));
}

Puzzel::Puzzel(rc_Puzzel v)
{
    ::BlockMove(&v,
                this,
                sizeof(Puzzel));
}

void Puzzel::operator=(rc_Puzzel v)
{
    ::BlockMove(&v,
                this,
                sizeof(Puzzel));
}

void Puzzel::MaakLeeg()
{
    m_leeg=geen;
    m_gewijzigd1=geen;
    m_gewijzigd2=geen;
    MaakLijstenLeeg();
    MaakVakkenLeeg();
    VoegToeAanLegeVakken();
}

void Puzzel::MaakLijstenLeeg()
{
    for (n1 i=0;i<puzzelGrootte;i++)
        {
        MaakRijLeeg(i);
        MaakKolomLeeg(i);
        MaakKotLeeg(i);
        }
}

void Puzzel::MaakLijstLeeg(r_Lijst lijst)
{
    lijst.aLeeg=puzzelGrootte;
    lijst.gewijzigd1=false;
    lijst.gewijzigd2=false;
    lijst.mogelijk=maxCombinaties;
}

void Puzzel::MaakRijLeeg(c_n1 i)
{
    r_Lijst rij=m_lijsten[i];
    rij.index=i;
    MaakLijstLeeg(rij);
    cp_n1 leeg=rij.leeg;
    for (n1 j=0;j<puzzelGrootte;j++)
        {
        c_n1 index=s_rij[i][j];
        leeg[j]=index;
        m_vakken[index].rijIndex=j;
        }
}

void Puzzel::MaakKolomLeeg(c_n1 i)
{
    r_Lijst kolom=m_lijsten[offsetKolom+i];
    kolom.index=static_cast<n1>(offsetKolom+i);
    MaakLijstLeeg(kolom);
    cp_n1 leeg=kolom.leeg;
    for (n1 j=0;j<puzzelGrootte;j++)
        {
        c_n1 index=s_kolom[i][j];
        leeg[j]=index;
        m_vakken[index].kolomIndex=j;
        }
}

void Puzzel::MaakKotLeeg(c_n1 i)
{
    r_Lijst kot=m_lijsten[offsetKot+i];
    kot.index=static_cast<n1>(offsetKot+i);
    MaakLijstLeeg(kot);
    cp_n1 leeg=kot.leeg;
    for (n1 j=0;j<puzzelGrootte;j++)
        {
        c_n1 index=s_kot[i][j];
        leeg[j]=index;
        m_vakken[index].kotIndex=j;
        }
}

void Puzzel::MaakVakkenLeeg()
{
    for (n1 index=0;index<aVakken;index++)
        {
        r_Vak vak=m_vakken[index];
        vak.index=index;
        vak.gekozen=0;
        }
}

void Puzzel::VoegToeAanLegeVakken()
{
    // opm: we voegen de lege vakken toe aan de lijst van lege vakken
    // zonder te overschrijven.
    r_Vak eerste=m_vakken[0];
    eerste.vorige=geen;
    eerste.volgende=1;
    m_leeg=0;
    for (n1 index=1;index<aVakken_1;index++)
        {
        r_Vak vak=m_vakken[index];
        vak.vorige=static_cast<n1>(index-1);
        vak.volgende=static_cast<n1>(index+1);
        }
    r_Vak laatste=m_vakken[aVakken_1];
    laatste.vorige=aVakken_2;
    laatste.volgende=geen;
}

n2 Puzzel::BerekenMogelijkeCijfers(rc_Vak vak) const
{
    rc_Coordinaten d=s_coordinaten[vak.index];
    rc_Lijst rij=m_lijsten[d.rij];
    rc_Lijst kolom=m_lijsten[d.kolom];
    rc_Lijst kot=m_lijsten[d.kot];
    c_n2 mogelijk=static_cast<n2>(rij.mogelijk
                                  &kolom.mogelijk
                                  &kot.mogelijk);
    return mogelijk;
}

void Puzzel::VulIn(n1 cijfer,
                   r_Vak vak)
{
    if (debug)
        {
        window.Schrijf("\pVul ");
        window.Schrijf(cijfer);
        window.Schrijf("\p in in vak ");
        window.Schrijf(vak.index);
        window.Schrijf("\p.");
        window.SchrijfLn();
        }
    vak.gekozen=cijfer;
    if (true)
        {
        // opm: ipv VerwijderUitLegeVakken(vak).
        c_n1 vorige=vak.vorige;
        c_n1 volgende=vak.volgende;
        if (vorige!=geen)
            {
            m_vakken[vorige].volgende=volgende;
            }
        else
            {
            m_leeg=volgende;
            }
        if (volgende!=geen)
            {
            m_vakken[volgende].vorige=vorige;
            }
        }
    c_n2 cijferBit=s_cijferBit[cijfer];
    rc_Coordinaten d=s_coordinaten[vak.index];
    cp_Lijst rij=m_lijsten+d.rij;
    if (true)
        {
        // opm: ipv VerminderMogelijkheden(cijfer,rij).
        rij->mogelijk&=~cijferBit;
        }
    if (true)
        {
        // opm: ipv VerwijderUitRij(vak,rij).
        if (!rij->gewijzigd1)
            {
            // opm: ipv PushLijst1(rij).
            rij->gewijzigd1=true;
            rij->volgende1=m_gewijzigd1;
            m_gewijzigd1=rij->index;
            }
        if (!rij->gewijzigd2)
            {
            // opm: ipv PushLijst2(rij).
            rij->gewijzigd2=true;
            rij->volgende2=m_gewijzigd2;
            m_gewijzigd2=rij->index;
            }
        c_n1 i=vak.rijIndex;
        c_n1 laatste=--rij->aLeeg;
        if (i!=laatste)
            {
            cp_n1 leeg=rij->leeg;
            c_n1 laatsteIndex=leeg[laatste];
            leeg[i]=laatsteIndex;
            r_Vak laatsteVak=m_vakken[laatsteIndex];
            laatsteVak.rijIndex=i;
            }
        }
    cp_Lijst kolom=m_lijsten+d.kolom;
    if (true)
        {
        // opm: ipv VerminderMogelijkheden(cijfer,rij).
        kolom->mogelijk&=~cijferBit;
        }
    if (true)
        {
        // opm: ipv VerwijderUitKolom(vak,kolom).
        if (!kolom->gewijzigd1)
            {
            // opm: ipv PushLijst1(kolom).
            kolom->gewijzigd1=true;
            kolom->volgende1=m_gewijzigd1;
            m_gewijzigd1=kolom->index;
            }
        if (!kolom->gewijzigd2)
            {
            // opm: ipv PushLijst2(kolom).
            kolom->gewijzigd2=true;
            kolom->volgende2=m_gewijzigd2;
            m_gewijzigd2=kolom->index;
            }
        c_n1 i=vak.kolomIndex;
        c_n1 laatste=--kolom->aLeeg;
        if (i!=laatste)
            {
            cp_n1 leeg=kolom->leeg;
            c_n1 laatsteIndex=leeg[laatste];
            leeg[i]=laatsteIndex;
            r_Vak laatsteVak=m_vakken[laatsteIndex];
            laatsteVak.kolomIndex=i;
            }
        }
    cp_Lijst kot=m_lijsten+d.kot;
    if (true)
        {
        // opm: ipv VerminderMogelijkheden(cijfer,rij).
        kot->mogelijk&=~cijferBit;
        }
    if (true)
        {
        // opm: ipv VerwijderUitKot(vak,kot).
        if (!kot->gewijzigd1)
            {
            // opm: ipv PushLijst1(kot).
            kot->gewijzigd1=true;
            kot->volgende1=m_gewijzigd1;
            m_gewijzigd1=kot->index;
            }
        if (!kot->gewijzigd2)
            {
            // opm: ipv PushLijst2(kot).
            kot->gewijzigd2=true;
            kot->volgende2=m_gewijzigd2;
            m_gewijzigd2=kot->index;
            }
        c_n1 i=vak.kotIndex;
        c_n1 laatste=--kot->aLeeg;
        if (i!=laatste)
            {
            cp_n1 leeg=kot->leeg;
            c_n1 laatsteIndex=leeg[laatste];
            leeg[i]=laatsteIndex;
            r_Vak laatsteVak=m_vakken[laatsteIndex];
            laatsteVak.kotIndex=i;
            }
        }
}

bool Puzzel::KiesCijfersDieMaar1KeerVoorkomenInEenVak()
{
    if (debug)
        {
        window.Schrijf("\pStart met cijfers te kiezen die maar 1 keer voorkomen in een vak.");
        window.SchrijfLn();
        }

    // opm: we doen een bewerking op een stack die gaat wijzigen,
    // dus moeten we hem eerst kopiëren en leegmaken.
    n1 aGewijzigd=0;
    p_Lijst gewijzigd[aLijsten];
    n1 index=m_gewijzigd1;
    while (index!=geen)
        {
        cp_Lijst lijst=m_lijsten+index;
        gewijzigd[aGewijzigd++]=lijst;
        lijst->gewijzigd1=false;
        index=lijst->volgende1;
        }
    m_gewijzigd1=geen;

    // opm: we controleren in elke gewijzigde lijst elk leeg vak
    // om te zien wat het aantal mogelijke cijfers is:
    // - als het 1 is, dan vullen we dat cijfer in,
    // - als het 0 is, dan hebben we verkeerd gegokt in de backtracking.

    for (n1 i=0;i<aGewijzigd;i++)
        {
        rc_Lijst lijst=*gewijzigd[i];
        c_n1 aLeeg=lijst.aLeeg;
        if (!aLeeg)
            {
            continue;
            }
        // opm: we doen een bewerking op een tabel die gaat wijzigen,
        // dus zouden we die eerst moeten kopiëren.
        // We kunnen dat vermijden door de tabel achterstevoren te
        // doorlopen.
        cpc_n1 teVer=lijst.leeg-1;
        cpc_n1 laatste=teVer+aLeeg;
        for (pc_n1 leeg=laatste;leeg>teVer;leeg--)
            {
            r_Vak vak=m_vakken[*leeg];
            c_n2 mogelijk=BerekenMogelijkeCijfers(vak);
            if (!mogelijk)
                {
                return false;
                }
            c_n1 enige=s_enige[mogelijk];
            if (!enige)
                {
                continue;
                }
            VulIn(enige,
                  vak);
            }
        }

    if (debug)
        {
        Debug_Dump("\pStop met cijfers te kiezen die maar 1 keer voorkomen in een vak.");
        }
    return true;
}

bool Puzzel::KiesCijfersDieMaar1KeerVoorkomenInEenLijst()
{
    if (debug)
        {
        window.Schrijf("\pStart met cijfers te kiezen die maar 1 keer voorkomen in een lijst.");
        window.SchrijfLn();
        }

    // opm: we doen een bewerking op een stack die gaat wijzigen,
    // dus moeten we hem eerst kopiëren en leegmaken.
    n1 aGewijzigd=0;
    p_Lijst gewijzigd[aLijsten];
    n1 index=m_gewijzigd2;
    while (index!=geen)
        {
        cp_Lijst lijst=m_lijsten+index;
        gewijzigd[aGewijzigd++]=lijst;
        lijst->gewijzigd2=false;
        index=lijst->volgende2;
        }
    m_gewijzigd2=geen;

    // opm: we controleren in elke gewijzigde lijst elk leeg vak
    // om te zien wat het aantal cijfers is:
    // - als het 1 is, dan vullen we dat cijfer in,
    // - als het 0 is, dan hebben we verkeerd gegokt in de backtracking.
    for (n1 i=0;i<aGewijzigd;i++)
        {
        r_Lijst lijst=*gewijzigd[i];
        c_n1 aLeeg=lijst.aLeeg;
        if (!aLeeg)
            {
            continue;
            }
        if (aLeeg==1)
            {
            r_Vak vak=m_vakken[lijst.leeg[0]];
            c_n2 mogelijk=BerekenMogelijkeCijfers(vak);
            if (!mogelijk)
                {
                return false;
                }
            c_n1 enige=s_enige[mogelijk];
            VulIn(enige,
                  vak);
            continue;
            }
        n1 aantallen[aCijferBit];
        c_n2 lijstMogelijk=lijst.mogelijk;
        c_n1 aLijstCijfers=s_aCijfers[lijstMogelijk];
        cpc_n1 eersteLijstCijfer=s_cijfers[lijstMogelijk];
        cpc_n1 teVerLijstCijfer=eersteLijstCijfer+aLijstCijfers;
        pc_n1 lijstCijfer;
        for (lijstCijfer=eersteLijstCijfer;
             lijstCijfer<teVerLijstCijfer;
             lijstCijfer++)
            {
            aantallen[*lijstCijfer]=0;
            }
        p_Vak gevonden[aCijferBit];
        cpc_n1 eerste=lijst.leeg;
        cpc_n1 teVer=eerste+aLeeg;
        for (pc_n1 leeg=eerste;leeg<teVer;leeg++)
            {
            c_n1 index=*leeg;
            p_Vak vak=m_vakken+index;
            c_n2 vakMogelijk=BerekenMogelijkeCijfers(*vak);
            if (!vakMogelijk)
                {
                return false;
                }
            c_n2 doorsnede=static_cast<n2>(vakMogelijk&lijstMogelijk);
            c_n1 aDoorsnedeCijfers=s_aCijfers[doorsnede];
            cpc_n1 eersteDoorsnedeCijfer=s_cijfers[doorsnede];
            cpc_n1 teVerDoorsnedeCijfer=eersteDoorsnedeCijfer+aDoorsnedeCijfers;
            for (pc_n1 doorsnedeCijfer=eersteDoorsnedeCijfer;
                 doorsnedeCijfer<teVerDoorsnedeCijfer;
                 doorsnedeCijfer++)
                {
                r_n1 aantal=aantallen[*doorsnedeCijfer];
                if (!aantal)
                    {
                    aantal=1;
                    gevonden[*doorsnedeCijfer]=vak;
                    }
                else if (aantal==1)
                    {
                    aantal=2;
                    }
                }
            }
        for (lijstCijfer=eersteLijstCijfer;
             lijstCijfer<teVerLijstCijfer;
             lijstCijfer++)
            {
            c_n1 cijfer=*lijstCijfer;
            c_n1 aantal=aantallen[cijfer];
            if (!aantal)
                {
                return false;
                }
            if (aantal==1)
                {
                VulIn(cijfer,
                      *gevonden[cijfer]);
                }
            }
        }

    if (debug)
        {
        Debug_Dump("\pStop met cijfers te kiezen die maar 1 keer voorkomen in een lijst.");
        }
    return true;
}

bool Puzzel::VulZoVeelMogelijkIn()
{
    if (debug)
        {
        window.Schrijf("\pStart met zoveel mogelijk in te vullen.");
        window.SchrijfLn();
        }
    while (m_gewijzigd1!=geen)
        {
        if (!KiesCijfersDieMaar1KeerVoorkomenInEenVak())
            {
            return false;
            }
        }
    while (m_gewijzigd2!=geen)
        {
        if (!KiesCijfersDieMaar1KeerVoorkomenInEenLijst())
            {
            return false;
            }
        while (m_gewijzigd1!=geen)
            {
            if (!KiesCijfersDieMaar1KeerVoorkomenInEenVak())
                {
                return false;
                }
            }
        }
    if (debug)
        {
        Debug_Dump("\pStop met zoveel mogelijk in te vullen.");
        }
    return true;
}

bool Puzzel::BackTrack(c_n1 niveau)
{
    if (debug)
        {
        window.Schrijf("\pStart backtrack niveau ");
        window.Schrijf(niveau);
        window.Schrijf("\p.");
        window.SchrijfLn();
        }
    Puzzel backup(*this);
    p_Vak besteVak;
    n1 besteScore=aCijferBit;
    n1 index=m_leeg;
    while (index!=geen)
        {
        cp_Vak vak=m_vakken+index;
        c_n2 mogelijk=BerekenMogelijkeCijfers(*vak);
        c_n1 aMogelijk=s_aCijfers[mogelijk];
        c_n1 score=aMogelijk;
        if (score<besteScore)
            {
            besteVak=vak;
            besteScore=score;
            if (score==2)
                {
                // opm: het is niet nodig om verder te zoeken.
                break;
                }
            }
        index=vak->volgende;
        }
    c_n2 mogelijk=BerekenMogelijkeCijfers(*besteVak);
    c_n1 aMogelijk=s_aCijfers[mogelijk];
    pc_n1 cijfers=s_cijfers[mogelijk];
    cpc_n1 cijfersTeVer=cijfers+aMogelijk;
    bool isOpgelost=false;
    while (cijfers<cijfersTeVer)
        {
        c_n1 probeer=*cijfers;
        if (debug)
            {
            window.Schrijf("\pProbeer ");
            window.Schrijf(probeer);
            window.Schrijf("\p in vak ");
            window.Schrijf(besteVak->index);
            window.Schrijf("\p.");
            window.SchrijfLn();
            Debug_DumpBackTrack("\pvoor");
            }
        VulIn(probeer,
              *besteVak);
        c_bool volledig=VulZoVeelMogelijkIn();
        if (debug)
            {
            Debug_DumpBackTrack("\pna");
            }
        if (volledig)
            {
            if (m_leeg==geen)
                {
                isOpgelost=true;
                break;
                }
            else if (BackTrack(static_cast<n1>(niveau+1)))
                {
                isOpgelost=true;
                break;
                }
            }
        *this=backup;
        cijfers++;
        }
    if (debug)
        {
        window.Schrijf("\pStop backtrack niveau ");
        window.Schrijf(niveau);
        window.Schrijf("\p.");
        window.SchrijfLn();
        }
    return isOpgelost;
}

bool Puzzel::LosOp(rc_Buffer buffer)
{
    if (debug)
        {
        window.Schrijf("\pStart oplossen.");
        window.SchrijfLn();
        window.Schrijf("\pStart lezen.");
        window.SchrijfLn();
        }
    for (n1 index=0;index<aVakken;index++)
        {
        c_n1 cijfer=buffer.m_byte[index];
        if (!cijfer)
            {
            continue;
            }
        r_Vak vak=m_vakken[index];
        VulIn(cijfer,
              vak);
        }
    if (debug)
        {
        Debug_Dump("\pStop lezen.");
        }
    if (!VulZoVeelMogelijkIn())
        {
        // opm: foute opgave.
        return false;
        }
    if (m_leeg!=geen)
        {
        if (!BackTrack(0))
            {
            // opm: foute opgave.
            return false;
            }
        }
    if (debug)
        {
        Debug_Dump("\pStop oplossen.");
        }
    return true;
}

void Puzzel::Schrijf(r_Buffer buffer) const
{
    for (n1 index=0;index<aVakken;index++)
        {
        rc_Vak vak=m_vakken[index];
        c_n1 gekozen=vak.gekozen;
        buffer.m_byte[index]=gekozen;
        }
}

void Puzzel::Debug_DumpBackTrack(cpc_n1 tekst) const
{
    window.Schrijf("\pBackTrack ");
    window.Schrijf(tekst);
    window.Schrijf("\p=");
    window.SchrijfLn();
    window.Schrijf("\p  {");
    window.SchrijfLn();
    Debug_DumpVakken();
    window.Schrijf("\p  }");
    window.SchrijfLn();
}

void Puzzel::Debug_Dump(cpc_n1 tekst) const
{
    window.Schrijf(tekst);
    window.SchrijfLn();
    window.Schrijf("\pPuzzel=");
    window.SchrijfLn();
    window.Schrijf("\p  {");
    window.SchrijfLn();
    Debug_DumpLegeVakken();
    Debug_DumpGewijzigdeLijsten1();
    Debug_DumpGewijzigdeLijsten2();
    Debug_DumpVakken();
    Debug_DumpLijsten();
    window.Schrijf("\p  }");
    window.SchrijfLn();
}

void Puzzel::Debug_DumpLegeVakken() const
{
    window.Schrijf("\p  m_leeg={");
    bool isEerste=true;
    n1 index=m_leeg;
    while (index!=geen)
        {
        if (isEerste)
            {
            isEerste=false;
            }
        else
            {
            window.Schrijf("\p,");
            }
        rc_Vak vak=m_vakken[index];
        window.Schrijf(vak.index);
        index=vak.volgende;
        }
    window.Schrijf("\p}");
    window.SchrijfLn();
}

void Puzzel::Debug_DumpGewijzigdeLijsten1() const
{
    window.Schrijf("\p  m_gewijzigd1={");
    bool isEerste=true;
    n1 index=m_gewijzigd1;
    while (index!=geen)
        {
        if (isEerste)
            {
            isEerste=false;
            }
        else
            {
            window.Schrijf("\p,");
            }
        rc_Lijst lijst=m_lijsten[index];
        n1 schrijf_index=lijst.index;
        if (schrijf_index>=offsetKot)
            {
            window.Schrijf("\pkot");
            schrijf_index-=offsetKot;
            }
        else if (schrijf_index>=offsetKolom)
            {
            window.Schrijf("\pkolom");
            schrijf_index-=offsetKolom;
            }
        else
            {
            window.Schrijf("\prij");
            }
        window.Schrijf(schrijf_index);
        index=lijst.volgende1;
        }
    window.Schrijf("\p}");
    window.SchrijfLn();
}

void Puzzel::Debug_DumpGewijzigdeLijsten2() const
{
    window.Schrijf("\p  m_gewijzigd2={");
    bool isEerste=true;
    n1 index=m_gewijzigd2;
    while (index!=geen)
        {
        if (isEerste)
            {
            isEerste=false;
            }
        else
            {
            window.Schrijf("\p,");
            }
        rc_Lijst lijst=m_lijsten[index];
        n1 schrijf_index=lijst.index;
        if (schrijf_index>=offsetKot)
            {
            window.Schrijf("\pkot");
            schrijf_index-=offsetKot;
            }
        else if (schrijf_index>=offsetKolom)
            {
            window.Schrijf("\pkolom");
            schrijf_index-=offsetKolom;
            }
        else
            {
            window.Schrijf("\prij");
            }
        window.Schrijf(schrijf_index);
        index=lijst.volgende2;
        }
    window.Schrijf("\p}");
    window.SchrijfLn();
}

void Puzzel::Debug_DumpCijfers(c_n2 cijfers) const
{
    bool isEerste=true;
    n2 cijferBit=1;
    for (n1 cijfer=1;cijfer<=puzzelGrootte;cijfer++)
        {
        if (cijfers&cijferBit)
            {
            if (isEerste)
                {
                isEerste=false;
                }
            else
                {
                window.Schrijf("\p,");
                }
            window.Schrijf(cijfer);
            }
        cijferBit<<=1;
        }
}

void Puzzel::Debug_DumpVakken() const
{
    window.Schrijf("\p  m_vakken=");
    window.SchrijfLn();
    window.Schrijf("\p    {");
    window.SchrijfLn();
    Debug_DumpLijn();
    for (n1 rij=0;rij<puzzelGrootte;rij++)
        {
        n1 kolom;
        window.Schrijf("\p    |");
        for (kolom=0;kolom<puzzelGrootte;kolom++)
            {
            c_n1 index=MaakIndex2(rij,
                                  kolom);
            rc_Vak vak=m_vakken[index];
            Debug_DumpMogelijk1(vak);
            }
        window.SchrijfLn();
        window.Schrijf("\p    |");
        for (kolom=0;kolom<puzzelGrootte;kolom++)
            {
            c_n1 index=MaakIndex2(rij,
                                  kolom);
            rc_Vak vak=m_vakken[index];
            Debug_DumpMogelijk2(vak);
            }
        window.SchrijfLn();
        window.Schrijf("\p    |");
        for (kolom=0;kolom<puzzelGrootte;kolom++)
            {
            c_n1 index=MaakIndex2(rij,
                                  kolom);
            rc_Vak vak=m_vakken[index];
            Debug_DumpMogelijk3(vak);
            }
        window.SchrijfLn();
        Debug_DumpLijn();
        }
    window.Schrijf("\p    }");
    window.SchrijfLn();
}

void Puzzel::Debug_DumpLijn() const
{
    window.Schrijf("\p    +");
    n1 i;
    for (i=0;i<puzzelGrootte;i++)
        {
        window.Schrijf("\p---+");
        }
    window.SchrijfLn();
}

void Puzzel::Debug_DumpMogelijk1(rc_Vak vak) const
{
    Debug_DumpMogelijk(vak,
                       1,
                       2,
                       3);
}

void Puzzel::Debug_DumpMogelijk2(rc_Vak vak) const
{
    Debug_DumpMogelijk(vak,
                       4,
                       5,
                       6);
}

void Puzzel::Debug_DumpMogelijk3(rc_Vak vak) const
{
    Debug_DumpMogelijk(vak,
                       7,
                       8,
                       9);
}

void Puzzel::Debug_DumpMogelijk(rc_Vak vak,
                                c_n1 cijfer1,
                                c_n1 cijfer2,
                                c_n1 cijfer3) const
{
    if (vak.gekozen)
        {
        if (cijfer1==4)
            {
            window.Schrijf("\p ");
            window.Schrijf(vak.gekozen);
            window.Schrijf("\p ");
            }
        else
            {
            window.Schrijf("\p   ");
            }
        }
    else
        {
        Debug_DumpMogelijkVoegToe(vak,
                                  cijfer1);
        Debug_DumpMogelijkVoegToe(vak,
                                  cijfer2);
        Debug_DumpMogelijkVoegToe(vak,
                                  cijfer3);
        }
    window.Schrijf("\p|");
}

void Puzzel::Debug_DumpMogelijkVoegToe(rc_Vak vak,
                                       c_n1 cijfer) const
{
    c_n2 mogelijk=BerekenMogelijkeCijfers(vak);
    c_n2 cijferBit=s_cijferBit[cijfer];
    if (mogelijk&cijferBit)
        {
        window.Schrijf(cijfer);
        }
    else
        {
        window.Schrijf("\p ");
        }
}

void Puzzel::Debug_DumpLijsten() const
{
    Debug_DumpRijen();
    Debug_DumpKolommen();
    Debug_DumpKottekens();
}

void Puzzel::Debug_DumpRijen() const
{
    for (n1 i=0;i<puzzelGrootte;i++)
        {
        Debug_DumpLijst("\pm_rij",
                        i,
                        m_lijsten[i]);
        }
}

void Puzzel::Debug_DumpKolommen() const
{
    for (n1 i=0;i<puzzelGrootte;i++)
        {
        Debug_DumpLijst("\pm_kolom",
                        i,
                        m_lijsten[offsetKolom+i]);
        }
}

void Puzzel::Debug_DumpKottekens() const
{
    for (n1 i=0;i<puzzelGrootte;i++)
        {
        Debug_DumpLijst("\pm_kot",
                        i,
                        m_lijsten[offsetKot+i]);
        }
}

void Puzzel::Debug_DumpLijst(cpc_n1 tekst,
                             c_n1 i,
                             rc_Lijst lijst) const
{
    window.Schrijf("\p  ");
    window.Schrijf(tekst);
    window.Schrijf("\p[");
    window.Schrijf(i);
    window.Schrijf("\p]=");
    window.SchrijfLn();
    window.Schrijf("\p    {");
    window.SchrijfLn();
    window.Schrijf("\p    aLeeg=");
    window.Schrijf(lijst.aLeeg);
    window.SchrijfLn();
    window.Schrijf("\p    leeg={");
    Debug_DumpLegeVakkenVanLijst(lijst.aLeeg,
                                 lijst.leeg);
    window.Schrijf("\p}");
    window.SchrijfLn();
    window.Schrijf("\p    gewijzigd1=");
    window.Schrijf(lijst.gewijzigd1);
    window.SchrijfLn();
    window.Schrijf("\p    gewijzigd2=");
    window.Schrijf(lijst.gewijzigd2);
    window.SchrijfLn();
    window.Schrijf("\p    mogelijk={");
    Debug_DumpCijfers(lijst.mogelijk);
    window.Schrijf("\p}");
    window.SchrijfLn();
    window.Schrijf("\p    }");
    window.SchrijfLn();
}

void Puzzel::Debug_DumpLegeVakkenVanLijst(c_n1 aantal,
                                          cpc_n1 leeg) const
{
    for (n1 i=0;i<aantal;i++)
        {
        if (i)
            {
            window.Schrijf("\p,");
            }
        window.Schrijf(leeg[i]);
        }
}

[Puzzle]

Code: Selecteer alles

// File: Puzzel.h
// Date: 17 December 2006.
// Version: 197 microseconds on PowerMac G3/233 MHz.
//
// Copyright (c) 2006 Cliff Huylebroeck. All Rights Reserved.
//
// Permission to use, copy, modify, and distribute this software
// and its documentation for NON-COMMERCIAL purposes and without
// fee is hereby granted provided that this copyright notice
// appears in all copies.
//
// Cliff Huylebroeck MAKES NO REPRESENTATIONS OR WARRANTIES ABOUT THE
// SUITABILITY OF THE SOFTWARE, EITHER EXPRESS OR IMPLIED, INCLUDING BUT
// NOT LIMITED TO THE IMPLIED WARRANTIES OF MERCHANTABILITY, FITNESS FOR
// A PARTICULAR PURPOSE, OR NON-INFRINGEMENT. Cliff Huylebroeck SHALL NOT
// BE LIABLE FOR ANY DAMAGES SUFFERED BY LICENSEE AS A RESULT OF USING,
// MODIFYING OR DISTRIBUTING THIS SOFTWARE OR ITS DERIVATIVES.

#pragma once

#include "bool.h"
#include "Buffer.h"
#include "Coordinaten.h"
#include "Lijst.h"
#include "Vak.h"

// opm: vroeger noemde deze klasse Rooster.
// Dat komt doordat in de Java-versie geen onderscheid werd
// gemaakt tussen data en interface.
// Puzzel zal voor de meeste mensen duidelijker zijn.
// In C++ worden functies binnen dezelfde klasse sneller
// uitgevoerd dan functies tussen verschillende klassen.
// Daarom is alle code die verband houdt met de oplossing verplaatst
// naar de klasse Puzzel.
// Om te voorkomen dat ik functies gebruik van andere klassen heb ik
// daar structs van gemaakt.
// Langs de andere kant wordt de klasse Puzzel daardoor ingewikkelder,
// moeilijker om te lezen en gemakkelijker om fouten te maken.

class Puzzel;
    typedef Puzzel* p_Puzzel;
    typedef const p_Puzzel cp_Puzzel;
typedef const Puzzel c_Puzzel;
    typedef c_Puzzel* pc_Puzzel;
    typedef const pc_Puzzel cpc_Puzzel;
typedef Puzzel& r_Puzzel;
typedef p_Puzzel& rp_Puzzel;
typedef cp_Puzzel& rcp_Puzzel;
typedef c_Puzzel& rc_Puzzel;
typedef pc_Puzzel& rpc_Puzzel;
typedef cpc_Puzzel& rcpc_Puzzel;

class Puzzel
{
private:

    // DEEL 1: globale variabelen ===================================================

    static c_n1 geen=255;

    // opm: m_rij[i][j] is het j-de vak in de i-de rij enz.
    static n1 s_rij[puzzelGrootte][puzzelGrootte];
    static n1 s_kolom[puzzelGrootte][puzzelGrootte];
    static n1 s_kot[puzzelGrootte][puzzelGrootte];

    static Coordinaten s_coordinaten[aVakken];

    // opm: als i een getal is van 1 tot 9,
    // dan is cijferBit(i) het binair getal met bit(i-1) = 1.
    static n2 s_cijferBit[aCijferBit];

    // opm: als j een binair getal is met alleen bit(i) = 1,
    // dan is enige(j) = i+1,
    // anders is enige(j) = 0.
    static n1 s_enige[aCombinaties];

    // opm: als j een binair getal is met x bits = 1,
    // dan is aCijfers(j) = x.
    static n1 s_aCijfers[aCombinaties];

    // opm: als j een binair getal is met x bits = 1,
    // dan is cijfers(j,i) = enige(bit(i) van j) voor i = 1 tot x.
    static n1 s_cijfers[aCombinaties][puzzelGrootte];

    // opm: als j een binair getal is met x bits = 1,
    // dan is cijferBits(j,i) = cijferBit(cijfers(j,i)) voor i = 1 tot x.
    static n2 s_cijferBits[aCombinaties][puzzelGrootte];

    // opm: als j een binair getal is met x bits = 1,
    // dan is willekeurig(j) = cijfers(j,0) voor i = 1 tot x.
    // Dat hoeft niet zo te zijn. Daarom moet naast s_cijfers ook
    // s_willekeurig gedefinieerd worden.
    static n1 s_willekeurig[aCombinaties];

    // opm: als j een binair getal is met x bits = 1,
    // dan is willekeurigBit(j,i) = cijferBit(willekeurig(j,i)) voor i = 1 tot x.
    static n2 s_willekeurigBit[aCombinaties];

    static Puzzel s_leeg;

    // DEEL 2: globale functies =====================================================

public:
    static void Init();
private:
    static void Init_Coordinaten();
    static void Init_Indexen();
    static void Init_CijferBit();
    static void Init_Enige();
    static void Init_Cijfers();
    static void Init_Willekeurig();

    // DEEL 3: lokale data ==========================================================

    n1 m_leeg;                //         1 byte nodig.
    n1 m_gewijzigd1;          //         1 byte nodig.
    n1 m_gewijzigd2;          //         1 byte nodig.
    Vak m_vakken[aVakken];    //  81*8=648 bytes nodig.
    Lijst m_lijsten[aLijsten];// 27*18=486 bytes nodig.
                              //      1134 bytes nodig in totaal.

    /// opm: vroeger was het zo:
    // Lijst m_rij[puzzelGrootte];
    // Lijst m_kolom[puzzelGrootte];
    // Lijst m_kot[puzzelGrootte];
    // Dan moest ik pointers gebruiken voor m_gewijzigd.
    // Dan was de puzzel groter voor BlockMoves.

    // DEEL 4: constructie/kopie ====================================================

    Puzzel(bool);
public:
    Puzzel();
    Puzzel(rc_Puzzel v);
    void operator=(rc_Puzzel v);

    // DEEL 5: initialisatie ========================================================

private:
    void MaakLeeg();
    void MaakLijstenLeeg();
    void MaakLijstLeeg(r_Lijst lijst);
    void MaakRijLeeg(n1 i);
    void MaakKolomLeeg(n1 i);
    void MaakKotLeeg(n1 i);
    void MaakVakkenLeeg();
    void VoegToeAanLegeVakken();

    // DEEL 6: oplossing ============================================================

    inline n2 BerekenMogelijkeCijfers(rc_Vak vak) const;
    void VulIn(n1 cijfer,
               r_Vak vak);
    bool KiesCijfersDieMaar1KeerVoorkomenInEenVak();
    bool KiesCijfersDieMaar1KeerVoorkomenInEenLijst();
    bool VulZoVeelMogelijkIn();
    bool BackTrack(n1 niveau);

    // DEEL 7: publieke operators.
public:
    bool LosOp(rc_Buffer buffer);
    void Schrijf(r_Buffer buffer) const;

    // DEEL 8: debug.
private:
    void Debug_DumpBackTrack(pc_n1 tekst) const;
    void Debug_Dump(pc_n1 tekst) const;
    void Debug_DumpLegeVakken() const;
    void Debug_DumpGewijzigdeLijsten1() const;
    void Debug_DumpGewijzigdeLijsten2() const;
    void Debug_DumpCijfers(n2 cijfers) const;
    void Debug_DumpVakken() const;
    void Debug_DumpLijn() const;
    void Debug_DumpMogelijk1(rc_Vak vak) const;
    void Debug_DumpMogelijk2(rc_Vak vak) const;
    void Debug_DumpMogelijk3(rc_Vak vak) const;
    void Debug_DumpMogelijk(rc_Vak vak,
                            n1 cijfer1,
                            n1 cijfer2,
                            n1 cijfer3) const;
    void Debug_DumpMogelijkVoegToe(rc_Vak vak,
                                   n1 cijfer) const;
    void Debug_DumpLijsten() const;
    void Debug_DumpRijen() const;
    void Debug_DumpKolommen() const;
    void Debug_DumpKottekens() const;
    void Debug_DumpLijst(pc_n1 tekst,
                         n1 i,
                         rc_Lijst lijst) const;
    void Debug_DumpLegeVakkenVanLijst(c_n1 aantal,
                                      pc_n1 leeg) const;
};

[Puzzle]

Code: Selecteer alles

// File: QDGlobals.h
// Date: 10 Januari 2007.
// Version: 197 microseconds on PowerMac G3/233 MHz.
//
// Copyright (c) 2006 Cliff Huylebroeck. All Rights Reserved.
//
// Permission to use, copy, modify, and distribute this software
// and its documentation for NON-COMMERCIAL purposes and without
// fee is hereby granted provided that this copyright notice
// appears in all copies.
//
// Cliff Huylebroeck MAKES NO REPRESENTATIONS OR WARRANTIES ABOUT THE
// SUITABILITY OF THE SOFTWARE, EITHER EXPRESS OR IMPLIED, INCLUDING BUT
// NOT LIMITED TO THE IMPLIED WARRANTIES OF MERCHANTABILITY, FITNESS FOR
// a PARTICULAR PURPOSE, OR NON-INFRINGEMENT. Cliff Huylebroeck SHALL NOT
// BE LIABLE FOR ANY DAMAGES SUFFERED BY LICENSEE AS A RESULT OF USING,
// MODIFYING OR DISTRIBUTING THIS SOFTWARE OR ITS DERIVATIVES.

#pragma once

#include "GrafPort.h"

struct QDGlobals;
    typedef QDGlobals* p_QDGlobals;
    typedef const p_QDGlobals cp_QDGlobals;
typedef const QDGlobals c_QDGlobals;
    typedef c_QDGlobals* pc_QDGlobals;
    typedef const pc_QDGlobals cpc_QDGlobals;
typedef QDGlobals& r_QDGlobals;
typedef p_QDGlobals& rp_QDGlobals;
typedef cp_QDGlobals& rcp_QDGlobals;
typedef c_QDGlobals& rc_QDGlobals;
typedef pc_QDGlobals& rpc_QDGlobals;
typedef cpc_QDGlobals& rcpc_QDGlobals;

// opm: hoe QDGlobals er uitzien interesseert ons hier niet.

struct QDGlobals
    {
    n1 x[202];
    p_GrafPort thePort;
    };

[Puzzle]

Code: Selecteer alles

// File: RandomGenerator.cp
// Date: 17 December 2006.
// Version: 197 microseconds on PowerMac G3/233 MHz.
//
// Copyright (c) 2006 Cliff Huylebroeck. All Rights Reserved.
//
// Permission to use, copy, modify, and distribute this software
// and its documentation for NON-COMMERCIAL purposes and without
// fee is hereby granted provided that this copyright notice
// appears in all copies.
//
// Cliff Huylebroeck MAKES NO REPRESENTATIONS OR WARRANTIES ABOUT THE
// SUITABILITY OF THE SOFTWARE, EITHER EXPRESS OR IMPLIED, INCLUDING BUT
// NOT LIMITED TO THE IMPLIED WARRANTIES OF MERCHANTABILITY, FITNESS FOR
// a PARTICULAR PURPOSE, OR NON-INFRINGEMENT. Cliff Huylebroeck SHALL NOT
// BE LIABLE FOR ANY DAMAGES SUFFERED BY LICENSEE AS A RESULT OF USING,
// MODIFYING OR DISTRIBUTING THIS SOFTWARE OR ITS DERIVATIVES.

#include "RandomGenerator.h"

#include "Debug.h"
#include "GetDateTime.h"
#include "TickCount.h"
#include "z4.h"

// opm: max=1ULL<<64=18446744073709551616.
c_n8 RandomGenerator::deler=47294967263;// opm: priem.
c_n8 RandomGenerator::quotient=390036089;// opm: max/deler, priem.
c_n8 RandomGenerator::rest=13065997209;// opm: max%deler, (= 3 x 101 x 43122103).

RandomGenerator::RandomGenerator()
{
    if (debug)
        {
        Feed(1234);
        }
    else
        {
        RandomGetal seed;
        ::GetDateTime(&seed.N4.N0);
        seed.N4.N1=::TickCount();
        Feed(seed.N8.N);
        }
    Feed(1234);
}

void RandomGenerator::Feed(c_n8 seed)
{
    m_volgende.N8.N=seed;
}

void RandomGenerator::BerekenVolgende()
{
    if (!m_volgende.N8.N)
        {
        m_volgende.N8.N=1;
        return;
        }
    c_n8 a=m_volgende.N8.N/quotient;
    c_n8 b=m_volgende.N8.N%quotient;
    c_n8 c=m_volgende.N8.N/deler;
    m_volgende.N8.N=(rest*a)+(deler*b)+c;
}

n1 RandomGenerator::Geef_random()
{
    BerekenVolgende();
    c_z4 x=m_volgende.N1.N000
           ^m_volgende.N1.N001
           ^m_volgende.N1.N010
           ^m_volgende.N1.N011
           ^m_volgende.N1.N100
           ^m_volgende.N1.N101
           ^m_volgende.N1.N110
           ^m_volgende.N1.N111;
    c_n1 y=static_cast<n1>(x);
    return y;
}

bool RandomGenerator::Geef_randomBool()
{
    BerekenVolgende();
    c_bool b=static_cast<bool>(m_volgende.N8.N>0x7FFFFFFFFFFFFFFF);
    return b;
}

void RandomGenerator::Geef_random012(r_n1 i0,
                                     r_n1 i1,
                                     r_n1 i2)
{
    c_n1 x=Geef_random(0,
                       5);
    static c_n1 tabel[6][3]={{0,1,2},{0,2,1},{1,0,2},{1,2,0},{2,0,1},{2,1,0}};
    cpc_n1 tabel_x=tabel[x];
    i0=tabel_x[0];
    i1=tabel_x[1];
    i2=tabel_x[2];
}

n1 RandomGenerator::Geef_random(c_n1 min,
                                c_n1 max)
{
    c_n1 lengte=static_cast<n1>(max-min+1);
    c_n1 r=static_cast<n1>(255/lengte);
    c_n1 m=static_cast<n1>(r*lengte);
    n1 test;
    do
        {
        test=Geef_random();
        }
    while (test>m);
    c_n1 n=static_cast<n1>(min+(test%lengte));
    return n;
}

RandomGenerator rg;

[Puzzle]

Code: Selecteer alles

// File: RandomGenerator.h
// Date: 17 December 2006.
// Version: 197 microseconds on PowerMac G3/233 MHz.
//
// Copyright (c) 2006 Cliff Huylebroeck. All Rights Reserved.
//
// Permission to use, copy, modify, and distribute this software
// and its documentation for NON-COMMERCIAL purposes and without
// fee is hereby granted provided that this copyright notice
// appears in all copies.
//
// Cliff Huylebroeck MAKES NO REPRESENTATIONS OR WARRANTIES ABOUT THE
// SUITABILITY OF THE SOFTWARE, EITHER EXPRESS OR IMPLIED, INCLUDING BUT
// NOT LIMITED TO THE IMPLIED WARRANTIES OF MERCHANTABILITY, FITNESS FOR
// A PARTICULAR PURPOSE, OR NON-INFRINGEMENT. Cliff Huylebroeck SHALL NOT
// BE LIABLE FOR ANY DAMAGES SUFFERED BY LICENSEE AS A RESULT OF USING,
// MODIFYING OR DISTRIBUTING THIS SOFTWARE OR ITS DERIVATIVES.

#pragma once

#include "n1.h"
#include "n4.h"
#include "n8.h"

// opm: dit is een Pseudo-random number generator met periode 2^64
// (een reeks van 2^64 verschillende waarden die herhaald wordt).

class RandomGenerator;
    typedef RandomGenerator* p_RandomGenerator;
    typedef const p_RandomGenerator cp_RandomGenerator;
typedef const RandomGenerator c_RandomGenerator;
    typedef c_RandomGenerator* pc_RandomGenerator;
    typedef const pc_RandomGenerator cpc_RandomGenerator;
typedef RandomGenerator& r_RandomGenerator;
typedef p_RandomGenerator& rp_RandomGenerator;
typedef cp_RandomGenerator& rcp_RandomGenerator;
typedef c_RandomGenerator& rc_RandomGenerator;
typedef pc_RandomGenerator& rpc_RandomGenerator;
typedef cpc_RandomGenerator& rcpc_RandomGenerator;

class RandomGenerator
{
private:
    static c_n8 deler;
    static c_n8 quotient;
    static c_n8 rest;
private:
    union RandomGetal
        {
        struct
            {
            n1 N000;
            n1 N001;
            n1 N010;
            n1 N011;
            n1 N100;
            n1 N101;
            n1 N110;
            n1 N111;
            } N1;
        struct
            {
            n4 N0;
            n4 N1;
            } N4;
        struct
            {
            n8 N;
            } N8;
        };
    RandomGetal m_volgende;
public:
    RandomGenerator();
private:
    void Feed(n8 seed);
    void BerekenVolgende();
    n1 Geef_random();
public:
    bool Geef_randomBool();

    // opm: random permutatie van 0, 1 en 2.
    void Geef_random012(r_n1 i0,
                        r_n1 i1,
                        r_n1 i2);

    // opm: random getal in het interval [min,max].
    n1 Geef_random(n1 min,
                   n1 max);
};

extern RandomGenerator rg;

[Puzzle]

Code: Selecteer alles

// File: Rect.h
// Date: 10 Januari 2007.
// Version: 197 microseconds on PowerMac G3/233 MHz.
//
// Copyright (c) 2006 Cliff Huylebroeck. All Rights Reserved.
//
// Permission to use, copy, modify, and distribute this software
// and its documentation for NON-COMMERCIAL purposes and without
// fee is hereby granted provided that this copyright notice
// appears in all copies.
//
// Cliff Huylebroeck MAKES NO REPRESENTATIONS OR WARRANTIES ABOUT THE
// SUITABILITY OF THE SOFTWARE, EITHER EXPRESS OR IMPLIED, INCLUDING BUT
// NOT LIMITED TO THE IMPLIED WARRANTIES OF MERCHANTABILITY, FITNESS FOR
// a PARTICULAR PURPOSE, OR NON-INFRINGEMENT. Cliff Huylebroeck SHALL NOT
// BE LIABLE FOR ANY DAMAGES SUFFERED BY LICENSEE AS A RESULT OF USING,
// MODIFYING OR DISTRIBUTING THIS SOFTWARE OR ITS DERIVATIVES.

#pragma once

#include "z2.h"

struct Rect;
    typedef Rect* p_Rect;
    typedef const p_Rect cp_Rect;
typedef const Rect c_Rect;
    typedef c_Rect* pc_Rect;
    typedef const pc_Rect cpc_Rect;
typedef Rect& r_Rect;
typedef p_Rect& rp_Rect;
typedef cp_Rect& rcp_Rect;
typedef c_Rect& rc_Rect;
typedef pc_Rect& rpc_Rect;
typedef cpc_Rect& rcpc_Rect;

// opm: opgelet, Mac-rect. Win-rect is {left,top,right,bottom}.

struct Rect
    {
    z2 top;
    z2 left;
    z2 bottom;
    z2 right;
    };

[Puzzle]

Code: Selecteer alles

// File: SetPort.h
// Date: 10 Januari 2007.
// Version: 197 microseconds on PowerMac G3/233 MHz.
//
// Copyright (c) 2006 Cliff Huylebroeck. All Rights Reserved.
//
// Permission to use, copy, modify, and distribute this software
// and its documentation for NON-COMMERCIAL purposes and without
// fee is hereby granted provided that this copyright notice
// appears in all copies.
//
// Cliff Huylebroeck MAKES NO REPRESENTATIONS OR WARRANTIES ABOUT THE
// SUITABILITY OF THE SOFTWARE, EITHER EXPRESS OR IMPLIED, INCLUDING BUT
// NOT LIMITED TO THE IMPLIED WARRANTIES OF MERCHANTABILITY, FITNESS FOR
// a PARTICULAR PURPOSE, OR NON-INFRINGEMENT. Cliff Huylebroeck SHALL NOT
// BE LIABLE FOR ANY DAMAGES SUFFERED BY LICENSEE AS A RESULT OF USING,
// MODIFYING OR DISTRIBUTING THIS SOFTWARE OR ITS DERIVATIVES.

#pragma once

#include "GrafPort.h"

__declspec(dllimport) extern pascal void SetPort(p_GrafPort port);