Quelltext /~heha/hs/Kalenderpuzzle.zip/src/solver.cpp

#include "kp.h"

static const Bitmap4x4 pieces[8] = {
 {7,7},		// als Bitmap, oben links = Byte 0, Bit 0
 {3,7},		// So gedreht dass die Holzmaserung senkrecht ist und die helle Seite oben.
 {14,3},	// Geraten: Oberseite Eichholz, Unterseite Kirschholz
 {3,1,3},
 {3,2,6},
 {1,1,7},
 {1,3,1,1},
 {1,1,1,3}};

bool Field::prepare(int monat, int tag) {
 static const Field cf={
  63,63,		// Monate Jan..Dez: 6 Spalten, 2 Zeilen
  127,127,127,127,7};	// Tage 1..31: 7 Spalten, 5 Zeilen
 if (monat<1 || monat>12) return false;
 if (tag<1 || tag>31) return false;
 *this=cf;
 int y=--monat/6;
 int x=monat%6;
 bm.b[y]&=~(1<<x);	// Monatsfeld besetzen
 y=2+--tag/7;
 x=tag%7;
 bm.b[y]&=~(1<<x);	// Tagfeld besetzen
 return true;
}


inline byte bitswap(byte b, int xe) {
 byte r=0;
 do{
  r=(r<<1)+(b&1);
  b>>=1;
 }while(--xe);
 return r;
}

void Piece::operator=(Bitmap4x4 data) {
 byte ored=0;
 ye=0;
 for (int i=0; i<4; i++) {
  byte b=data.b[i];
  if (!b) break;
  ++ye;	// Zeilen zählen
  ored|=b;
 }
 xe=0;
 while (ored) {
  ++xe;	// Spalten zählen
  ored>>=1;
 }
 bm.ull=data.u;
}

void Piece::transposeFrom(const Piece&p) {
 xe=p.ye;
 ye=p.xe;
 bm.ull=0;
 for (int y=0; y<p.ye; y++)
 for (int x=0; x<p.xe; x++)
 if (p.bm.b[y]&1<<x)	// Quellbit gesetzt?
   bm.b[x]|=1<<y;
}

void Piece::mirrorFrom(const Piece&p) {
 xe=p.xe;
 ye=p.ye;
 bm.ull=0;
 for (int y=0; y<p.ye; y++) bm.b[y] = bitswap(p.bm.b[y],xe);
}

void Piece::flipFrom(const Piece&p) {
 xe=p.xe;
 ye=p.ye;
 bm.ull=0;
 for (int y=0; y<p.ye; y++) bm.b[y] = p.bm.b[ye-1-y];
}

Solver solver;

bool Solver::puzzle() {
 Koord&kd = k[depth];
 const Piece*c=cache[depth];
 for (kd.d=0; kd.d<8; kd.d++) if (c[kd.d]) {	// Alle 4 Drehungen und 2 Seiten, sofern nicht vorher ausgefiltert
  Piece s = c[kd.d];	// Echte Kopie
  int xmax = 8-s.xe, ymax = 8-s.ye;
  for (kd.y=0; kd.y<ymax; kd.y++) {	// Alle Y-Positionen
   for (kd.x=0; kd.x<xmax; kd.x++) {	// Alle X-Positionen
    if (f.add(s)) {
     if (++depth==Piece::N) return true;
     if (puzzle()) return true;	// Rekursion!
     --depth;
     f.remove(s);
    }
    s.shift(1);
   }
   s.shift(8-xmax);
  }
 }
 return false;
}

// Nur für Debug
static int count(const Piece*c) {
 int r=0;
 for (int i=0; i<8; i++) if (*c++) ++r;
 return r;
}

bool Solver::solve(int monat,int tag,WORD flags) {
 if (!f.prepare(monat,tag)) return false;
 DWORD tic=GetTickCount();
 for (int t=0; t<Piece::N; t++) {
  Piece*c=cache[t];
  c[0]=pieces[t];
  c[7].transposeFrom(c[0]);
  c[4].   mirrorFrom(c[0]);
  c[6].     flipFrom(c[0]);
  c[2].   mirrorFrom(c[6]);
  c[1].   mirrorFrom(c[7]);
  c[3].     flipFrom(c[7]);
  c[5].   mirrorFrom(c[3]);
  for (int a=0; a<7; a++)
  for (int b=a+1; b<8; b++)
  if (c[b].bm.ull==c[a].bm.ull) {
   c[b].xe=0;
  }
  if (!(flags&1)) for (int b=4; b<8; b++) c[b].xe=0;
 }
 depth=0;
 bool r=puzzle();
 DebugPrintf(r?"Fertig nach %d ms\n":"Keine Lösung nach %d ms\n",GetTickCount()-tic);
 return r;
}

static const COLORREF colors[8]={
 RGB(100,57,30),
 RGB(28,240,220),
 RGB(200,40,120),
 RGB(200,200,80),
 RGB(100,200,100),
 RGB(250,200,0),
 RGB(60,120,240),
 RGB(40,200,250),
};

enum{
 RX=32,
 RY=RX,
};

static void paintRect(HDC dc,int x, int y, int ci) {
 HBRUSH hbr=CreateSolidBrush(colors[ci]);
 RECT r;
 SetRect(&r,x*RX,y*RY,(x+1)*RX,(y+1)*RY);
 FillRect(dc,&r,hbr);
 DeleteBrush(hbr);
}

static void paintPiece(HDC dc,const Piece&p,Koord k,int ci) {
 for (int y=0; y<8; y++) {
  for (int x=0; x<8; x++) {
   if (p.bm.b[y]&1<<x) paintRect(dc,k.x+x,k.y+y,ci);
  }
 }
}

void Solver::paint(HDC dc) const{
 for (int ci=0; ci<Piece::N; ci++) {
  paintPiece(dc,cache[ci][k[ci].d],k[ci],ci);
 }
}
Vorgefundene Kodierung: UTF-80