Sudoku solving in c++

2019-06-11 17:32发布

站内文章 / C++
13 0 0

问题:

I've recently been working on a sudoku game in c++. I've made a graphic version of it using SFML and it works just fine. However, I need to implement an algorithm which will solve the sudoku, whilst not being a brute-force algorithm (so backtracking doesn't work for me ;/). I've read about many ways to solve it and I've come across different algorithm names (such as Dancing Links), as well as algorithms which only describe how the search works without giving any specific pieces of information on how to implement it in c++. (i.e. assigning a table or a list of possible numbers to each single "bucket" and searching for the solution, also someone mentioned so-called A* algorithm?)

So here is my question, what kind of algorithm is fairly easy to implement and is not the backtracking one? And where to find specific pieces of information on how to use it in c++? Thanks in advance. My program works on a two-dimensional array, but I could somehow make the buckets into structures if needed.

回答1:

Peter Norvig recommends using process of elimination (constraint propagation) followed by search. His article here provides a very thorough explanation.

In constraint propagation you use the following strategy:

(1) If a square has only one possible value, then eliminate that value from the square's peers. 
(2) If a unit has only one possible place for a value, then put the value there.

Now, it's easy to find in O(N) time the initially-filled squares in the puzzle. Put them all in a queue. If their neighbours, after propagating the constraint, have only a single value, add that to the queue. Repeat until the queue is empty.

The puzzle is now either solved or no further progress can be made by propagating constraints.

If the puzzle is not solved, you could either use a fancier algorithm or, as Norvig recommends, employ backtracking. Since the backtracking is being performed on a typically-small subset of the puzzle space, you're not using brute-force.



回答2:

Description

Mine Sudoku is stored in form of 2D array 9x9 of 32 bit unsigned integers where each bit has its own purpose. low 10 bits are reserved for placed numbers (9 bits are used) next 10 bits are reserved for possible numbers (which can be placed there... which have not been ruled out yet) and finally one bit telling its a fixed cell and one telling if an error is present (conflict with another cell(s)).

As you can imagine my code boils down to bunch of binary operations ... which brings some problems on its own but solves others ...

Solver

As mentioned in the comments I am using rules and deterministic approach for this (no backtracking). The algo is like this:

  1. compute checksum of sudoku
  2. apply rules
  3. compute checksum of sudoku
  4. while the checksum is different than the last one loop to #2
  5. check for errors

Terminology and conventions

the board is addressed by:

x = <0,9)
y = <0,9)

Now the rules:

  1. singleton must be unique along row/col/sqr

    so if we got cell with only single placed value then there is no chance another such value will appear in the same row/col/sqr so clear it like in this example:

  2. if we got cell with only one possible number left place it

    that is simple if we cleared enough possible numbers from other rules sometimes we will be left with only one choice. Once detected place it and the cell is done ...

  3. the same possible number only in single row/col for single square

    if found clear the row/col for other squares as they can not have another placement of such number.

  4. same pair found in single row/col/sqr

    if detected clear the rest. Beware the pair must be exactly the same (no other possible numbers may be present in the cell)

    this rule can be expanded to 3 triplets etc but never saw any opportunity to do so as the basic rules solve them before and their probability is low ...

Here small C++/VCL code for this (rule #4 is not implemented yet):

//---------------------------------------------------------------------------
#ifndef _sudoku_h
#define _sudoku_h
//---------------------------------------------------------------------------
// set numbers
const DWORD _sudoku_1     =(1<< 0); // set numbers (used)
const DWORD _sudoku_a1    =(1<<10); // possible numbers (unused)
const DWORD _sudoku_fix   =(1<<20); // read only?
const DWORD _sudoku_err   =(1<<21); // error?
const DWORD _sudoku_2=(_sudoku_1<<1);
const DWORD _sudoku_3=(_sudoku_1<<2);
const DWORD _sudoku_4=(_sudoku_1<<3);
const DWORD _sudoku_5=(_sudoku_1<<4);
const DWORD _sudoku_6=(_sudoku_1<<5);
const DWORD _sudoku_7=(_sudoku_1<<6);
const DWORD _sudoku_8=(_sudoku_1<<7);
const DWORD _sudoku_9=(_sudoku_1<<8);
const DWORD _sudoku_n=_sudoku_1|_sudoku_2|_sudoku_3|_sudoku_4|_sudoku_5|_sudoku_6|_sudoku_7|_sudoku_8|_sudoku_9;
const DWORD _sudoku_a2=(_sudoku_a1<<1);
const DWORD _sudoku_a3=(_sudoku_a1<<2);
const DWORD _sudoku_a4=(_sudoku_a1<<3);
const DWORD _sudoku_a5=(_sudoku_a1<<4);
const DWORD _sudoku_a6=(_sudoku_a1<<5);
const DWORD _sudoku_a7=(_sudoku_a1<<6);
const DWORD _sudoku_a8=(_sudoku_a1<<7);
const DWORD _sudoku_a9=(_sudoku_a1<<8);
const DWORD _sudoku_an=_sudoku_a1|_sudoku_a2|_sudoku_a3|_sudoku_a4|_sudoku_a5|_sudoku_a6|_sudoku_a7|_sudoku_a8|_sudoku_a9;
//---------------------------------------------------------------------------
class sudoku
    {
public:
    DWORD map[9][9];
    Graphics::TBitmap *bmp;
    bool _redraw,_render_an;

    int x0,y0;          // grid start
    int x1,y1;          // grid end
    int sz;             // grid size
    int yb;             // y of buttons panel
    int selx,sely,selb; // mouse selection
    TShiftState sh0;

    int _debug_N;

    sudoku();
    sudoku(sudoku& a)   { *this=a; }
    ~sudoku();
    sudoku* operator = (const sudoku *a) { *this=*a; return this; }
//  sudoku* operator = (const sudoku &a) { ...copy... return this; }

    // GUI/interface
    void init(int *S);              // init with linear mapped 1D array 0 is empty space, 1..9 is fixed cell
    void draw();
    void resize(int xs,int ys);
    void mouse(int mx,int my,TShiftState sh);
    void key(WORD key,TShiftState sh);
    void load(AnsiString filename);
    void save(AnsiString filename);
    void set(int x,int y,DWORD m);  // set map[x][y]|=m
    void rst(int x,int y,DWORD m);  // clear map[x][y]-=m
    void xor(int x,int y,DWORD m);  // xor map[x][y]^=m
    // solver
    void s_init();                  // reset/init state from fixed cells only
    void s_check();                 // check for errors
    void solve();                   // solve the puzzle from scratch
    };
//---------------------------------------------------------------------------
sudoku::sudoku()
    {
    int i,j;
    _render_an=false;
    _redraw=false;
    selx=-1;
    sely=-1;
    selb=-1;
    bmp=new Graphics::TBitmap;
    for (i=0;i<9;i++)
     for (j=0;j<9;j++)
      map[i][j]=0;
    }
//---------------------------------------------------------------------------
sudoku::~sudoku()
    {
    if (bmp) delete bmp; bmp=NULL;
    }
//---------------------------------------------------------------------------
void sudoku::init(int *S)
    {
    int x,y,a;
    for (a=0,y=0;y<9;y++)
     for (x=0;x<9;x++,a++)
      if (S[a]) map[x][y]=(_sudoku_1<<(S[a]-1))|_sudoku_fix;
       else map[x][y]=0;
    s_init();
    _debug_N=0;
    }
//---------------------------------------------------------------------------
void sudoku::draw()
    {
    if (bmp==NULL) return;
    AnsiString s;
    int i,j,k,x,y;
    DWORD a;
    // clear
    bmp->Canvas->Brush->Color=clLtGray;
    bmp->Canvas->Brush->Style=bsSolid;
    bmp->Canvas->FillRect(Rect(0,0,bmp->Width,bmp->Height));
    bmp->Canvas->Brush->Color=clWhite;
    bmp->Canvas->FillRect(Rect(x0,y0,x1,y1));
    // selection
    if ((selx>=0)&&(selx<9))
     if ((sely>=0)&&(sely<9))
        {
        x=x0+(selx*sz);
        y=y0+(sely*sz);
        bmp->Canvas->Brush->Color=clSilver;
        bmp->Canvas->FillRect(Rect(x,y,x+sz,y+sz));
        }
    // buttons
    bmp->Canvas->Pen  ->Width=2;
    bmp->Canvas->Brush->Color=clWhite;
    bmp->Canvas->FillRect(Rect(x0,yb,x1,yb+sz));
    if ((selb>=0)&&(selb<9))
        {
        x=x0+(selb*sz);
        bmp->Canvas->Brush->Color=clDkGray;
        bmp->Canvas->FillRect(Rect(x,yb,x+sz,yb+sz));
        }
    for (j=0,i=0;i<=9;i++,j+=sz)
        {
        bmp->Canvas->MoveTo(x0+j,yb);
        bmp->Canvas->LineTo(x0+j,yb+sz);
        }
    bmp->Canvas->MoveTo(x0,yb);
    bmp->Canvas->LineTo(x1,yb);
    bmp->Canvas->MoveTo(x0,yb+sz);
    bmp->Canvas->LineTo(x1,yb+sz);
    // major grid
    bmp->Canvas->Pen  ->Color=clBlack;
    for (j=0,i=0;i<=3;i++,j+=3*sz)
        {
        bmp->Canvas->MoveTo(x0,y0+j);
        bmp->Canvas->LineTo(x1,y0+j);
        bmp->Canvas->MoveTo(x0+j,y0);
        bmp->Canvas->LineTo(x0+j,y1);
        }
    // minor grid
    bmp->Canvas->Pen  ->Width=1;
    for (j=0,i=0;i<9;i++,j+=sz)
        {
        bmp->Canvas->MoveTo(x0,y0+j);
        bmp->Canvas->LineTo(x1,y0+j);
        bmp->Canvas->MoveTo(x0+j,y0);
        bmp->Canvas->LineTo(x0+j,y1);
        }
    // big numbers
    bmp->Canvas->Brush->Style=bsClear;
    bmp->Canvas->Font->Height=sz-4;
    for (i=0;i<9;i++)
     for (j=0;j<9;j++)
        {
        a=map[i][j]; if (_render_an) a>>=10; a&=_sudoku_n; if (!a) continue;
             if (DWORD(map[i][j]&_sudoku_err)!=0) bmp->Canvas->Font->Color=clRed;
        else if (DWORD(map[i][j]&_sudoku_fix)!=0) bmp->Canvas->Font->Color=clBlack;
        else                                      bmp->Canvas->Font->Color=clBlue;
        for (k=0;k<9;k++)
         if (a==(_sudoku_1<<k))
            {
            s=k+1;
            x=x0+(i*sz)+((sz-bmp->Canvas->TextWidth (s))>>1);
            y=y0+(j*sz)+((sz-bmp->Canvas->TextHeight(s))>>1);
            bmp->Canvas->TextOutA(x,y,s);
            break;
            }
        }
    // small numbers
    bmp->Canvas->Brush->Style=bsClear;
    i=(sz-4)/3;
    const int dx[9]={-i,0,+i,-i,0,+i,-i,0,+i};
    const int dy[9]={+i,+i,+i,0,0,0,-i,-i,-i};
    bmp->Canvas->Font->Height=i;
    for (i=0;i<9;i++)
     for (j=0;j<9;j++)
        {
        a=map[i][j]; if (_render_an) a>>=10; a&=_sudoku_n; if (!a) continue;
        for (k=0;k<9;k++) if (a==(_sudoku_1<<k)) { k=-1; break; } if (k<0) continue;
             if (DWORD(map[i][j]&_sudoku_fix)!=0) bmp->Canvas->Font->Color=clBlack;
        else if (DWORD(map[i][j]&_sudoku_err)!=0) bmp->Canvas->Font->Color=clRed;
        else                                      bmp->Canvas->Font->Color=clBlue;
        for (k=0;k<9;k++)
         if (DWORD(a&(_sudoku_1<<k))!=0)
            {
            s=k+1;
            x=x0+(i*sz)+((sz-bmp->Canvas->TextWidth (s))>>1)+dx[k];
            y=y0+(j*sz)+((sz-bmp->Canvas->TextHeight(s))>>1)+dy[k];
            bmp->Canvas->TextOutA(x,y,s);
            }
        }
    // info
    x=5; y=5; i=20; y-=i;
    bmp->Canvas->Font->Color=clBlack;
    bmp->Canvas->TextOutA(x,y+=i,AnsiString().sprintf("N:%i",_debug_N));
    bmp->Canvas->TextOutA(x,y+=i,AnsiString().sprintf("%ix%i",selx,sely));
    if (_render_an) bmp->Canvas->TextOutA(x,y+=i,"an");

    // button numbers
    bmp->Canvas->Font->Height=sz-4;
    a=0;
    if ((selx>=0)&&(selx<9))
     if ((sely>=0)&&(sely<9))
      a=map[selx][sely]&_sudoku_n;
    for (i=0;i<9;i++)
        {
        s=i+1;
        x=x0+(i*sz)+((sz-bmp->Canvas->TextWidth (s))>>1);
        y=yb       +((sz-bmp->Canvas->TextHeight(s))>>1);
        if (DWORD(a&(_sudoku_1<<i))!=0) bmp->Canvas->Font->Color=clBlack;
        else                            bmp->Canvas->Font->Color=clLtGray;
        bmp->Canvas->TextOutA(x,y,s);
        }
    bmp->Canvas->Brush->Style=bsSolid;
    }
//---------------------------------------------------------------------------
void sudoku::resize(int xs,int ys)
    {
    bmp->SetSize(xs,ys);
    _redraw=true;
    int w=8;
    x0=(xs-w-w  )/ 9;
    y0=(ys-w-w-w)/10;
    sz=x0; if (sz>y0) sz=y0;
    x0=(xs-( 9*sz))/2;
    y0=(ys-(10*sz)-w)/2;
    x1=x0+(9*sz);
    y1=y0+(9*sz);
    yb=y1+w;
    }
//---------------------------------------------------------------------------
void sudoku::mouse(int mx,int my,TShiftState sh)
    {
    int q0=sh0.Contains(ssLeft);
    int q1=sh .Contains(ssLeft);
    if ((mx< x0)||(mx>=x1)) return;
    if ((my>=y0)&&(my< y1))
     if ((!q0)&&(q1))
        {
        selx=(mx-x0)/sz;
        sely=(my-y0)/sz;
        _redraw=true;
        }
    if ((my>=yb)&&(my< yb+sz))
        {
        selb=(mx-x0)/sz;
        _redraw=true;
        if ((!q0)&&(q1))
         if ((selx>=0)&&(selx<9))
          if ((sely>=0)&&(sely<9))
           xor(selx,sely,_sudoku_1<<selb);
        }
    else{
        _redraw|=selb!=-1;
        selb=-1;
        }
    sh0=sh;
    }
//---------------------------------------------------------------------------
void sudoku::key(WORD key,TShiftState sh)
    {
    // toggle (un)used number
    int a=-1;
    if ((key>='1')&&(key<='9')) a=key-'1';                  // 0..9
    if ((key>=97)&&(key<=105)) a=key-97;                    // num0..num9
    if (a>=0)
     if ((selx>=0)&&(selx<9))
      if ((sely>=0)&&(sely<9))
        {
        if (_render_an) a+=10;
        xor(selx,sely,_sudoku_1<<(a));
        }
    // navigate selection cell
    if ((key>=37)&&(key<=40))                               // arrows
        {
        if (key==37) { selx--; _redraw=true; }
        if (key==39) { selx++; _redraw=true; }
        if (key==38) { sely--; _redraw=true; }
        if (key==40) { sely++; _redraw=true; }
        if (selx<0) selx=0; if (selx>8) selx=8;
        if (sely<0) sely=0; if (sely>8) sely=8;
        }
    if (key== 27) { _redraw=true; selx=-1; sely=-1; }       // esc      clear selection
    if (key== 32) { solve(); }                              // space    apply solving rules
    if (key==112) { _redraw=true; _render_an=!_render_an; } // F1       used/unused numbers mode
    if (key==113) { _redraw=true; save("map000.dat"); }     // F2       save
    if (key==116) { _redraw=true; load("map000.dat"); }     // F5       load
    if (key==119) { _redraw=true; s_init();  }              // F8       restart
    // debug
    if (key==107) { _debug_N++; solve(); }                  // num+
    if (key==109) { _debug_N--; solve(); }                  // num-
    }
//---------------------------------------------------------------------------
void sudoku::load(AnsiString filename)
    {
    int hnd,x,y;
    hnd=FileOpen(filename,fmOpenRead);
    if (hnd<0) return;
    for (x=0;x<9;x++)
     for (y=0;y<9;y++)
      FileRead(hnd,&map[x][y],sizeof(map[0][0]));
    FileClose(hnd);
    _redraw=true;
    }
//---------------------------------------------------------------------------
void sudoku::save(AnsiString filename)
    {
    int hnd,x,y;
    hnd=FileCreate(filename);
    if (hnd<0) return;
    for (x=0;x<9;x++)
     for (y=0;y<9;y++)
      FileWrite(hnd,&map[x][y],sizeof(map[0][0]));
    FileClose(hnd);
    }
//---------------------------------------------------------------------------
void sudoku::set(int x,int y,DWORD m)
    {
    if ((x<0)||(x>=9)||(y<0)||(y>=9)) return;
    if (DWORD(map[x][y]&m)!=0) return;
    if (DWORD(map[x][y]&_sudoku_fix)!=0) return;
    map[x][y]|=m;
    s_check();
    _redraw=true;
    }
//---------------------------------------------------------------------------
void sudoku::rst(int x,int y,DWORD m)
    {
    if ((x<0)||(x>=9)||(y<0)||(y>=9)) return;
    if (DWORD(map[x][y]&m==0)) return;
    if (DWORD(map[x][y]&_sudoku_fix)!=0) return;
    map[x][y]|=m;
    map[x][y]^=m;
    s_check();
    _redraw=true;
    }
//---------------------------------------------------------------------------
void sudoku::xor(int x,int y,DWORD m)
    {
    if ((x<0)||(x>=9)||(y<0)||(y>=9)) return;
    if (DWORD(map[selx][sely]&m)==0) set(selx,sely,m);
     else                            rst(selx,sely,m);
    }
//---------------------------------------------------------------------------
void sudoku::s_init()
    {
    int x,y;
    DWORD a,b;
    for (x=0;x<9;x++)
     for (y=0;y<9;y++)
        {
        a=map[x][y];
        if (DWORD(a&_sudoku_fix)==0) a =_sudoku_an;
         else                      { a&=_sudoku_n|_sudoku_fix; a|=(a<<10)&_sudoku_an; }
        map[x][y]=a;
        }
    s_check();
    _redraw=true;
    }
//---------------------------------------------------------------------------
void sudoku::s_check()
    {
    int x,y,_x,_y,xx,yy,k,n[10];
    DWORD a,b,m[9][9];
    // iterate xx,yy through adjacent cells to x,y (included)
    #define row(y) for (yy=y,xx=0;xx<9;xx++)
    #define col(x) for (xx=x,yy=0;yy<9;yy++)
    #define sqr(x,y) for (_x=(x/3)*3,_y=(y/3)*3,xx=_x;xx<_x+3;xx++) for (yy=_y;yy<_y+3;yy++)
    // init m[][] with singleton used numbers from map[][] and clear error
    for (x=0;x<9;x++ ) for (y=0;y<9;y++ ){ m[x][y]=0; a=map[x][y]&_sudoku_n; map[x][y]&=0xFFFFFFFF^_sudoku_err; for (b=_sudoku_1,k=1;k<=9;k++,b<<=1)  if (a==b) m[x][y]=k; }
                                         // compute histogram n[]                                  // check for error (count>1) and flag it for rendering
                       for (y=0;y<9;y++ ){ for (xx=0;xx<=9;xx++) n[xx]=0; row(  y) n[m[xx][yy]]++; n[0]=0; row(  y) if (n[m[xx][yy]]>1) map[xx][yy]|=_sudoku_err; }
    for (x=0;x<9;x++ )                   { for (xx=0;xx<=9;xx++) n[xx]=0; col(x  ) n[m[xx][yy]]++; n[0]=0; col(x  ) if (n[m[xx][yy]]>1) map[xx][yy]|=_sudoku_err; }
    for (x=0;x<9;x+=3) for (y=0;y<9;y+=3){ for (xx=0;xx<=9;xx++) n[xx]=0; sqr(x,y) n[m[xx][yy]]++; n[0]=0; sqr(x,y) if (n[m[xx][yy]]>1) map[xx][yy]|=_sudoku_err; }
    #undef row
    #undef col
    #undef sqr
    }
//---------------------------------------------------------------------------
void sudoku::solve()
    {
    int k,n[9],nx[9],ny[9];
    DWORD a,b;

    int x,y,_x,_y,xx,yy;
    DWORD checksum0,checksum;
    // is a single bit set from _sudoku1.._sudoku_9?
    #define single(a) for (b=_sudoku_1;b<=_sudoku_9;b<<=1) if (a==b)
    // iterate xx,yy through adjacent cells to x,y (included)
    #define row(y) for (yy=y,xx=0;xx<9;xx++)
    #define col(x) for (xx=x,yy=0;yy<9;yy++)
    #define sqr(x,y) for (_x=(x/3)*3,_y=(y/3)*3,xx=_x;xx<_x+3;xx++) for (yy=_y;yy<_y+3;yy++)

    s_init();

    // solve main loop
    for (checksum0=0,_debug_N=0;;_debug_N++)
        {
        // compute checksum and stop if not changed
        for (checksum=0,a=1,x=0;x<9;x++)
         for (y=0;y<9;y++,a++)
          checksum+=map[x][y]&(_sudoku_n|_sudoku_an)*a;
        if (checksum==checksum0) break;
        checksum0=checksum;

        // #1 clear singleton used numbers in (un)used numbers of adjacent cells
        for (x=0;x<9;x++)
         for (y=0;y<9;y++)
            {
            a=map[x][y]&_sudoku_n;
            single(a)
                {
                b=a<<10;
                map[x][y]&=0xFFFFFFFF^_sudoku_an;
                map[x][y]|=b;
                b^=0xFFFFFFFF;
                row(  y) if  (xx!=x)           map[xx][yy]&=b;
                col(x  ) if           (yy!=y)  map[xx][yy]&=b;
                sqr(x,y) if ((xx!=x)||(yy!=y)) map[xx][yy]&=b;
                break;
                }
            }

        // #2 find if just single occurence in adjacent cells
                                             // clear histogram n[]        compute histogram n[]                                                                                                                       // handle single occurence by clearing all other adjacent cells
                           for (y=0;y<9;y++ ){ for (xx=0;xx<9;xx++) n[xx]=0; row(  y) { a=map[xx][yy]; a=(a|(a>>10))&_sudoku_n; for (b=0;b<9;b++) if (DWORD(a&(_sudoku_1<<b))!=0) { n[b]++; nx[b]=xx; ny[b]=yy; }} for (b=_sudoku_1|_sudoku_a1,k=0;k<9;k++,b<<=1) if (n[k]==1) row(  y) if (DWORD(map[xx][yy]&_sudoku_fix)==0) if ((xx==nx[k])&&(yy==ny[k])) map[xx][yy]&=0xFFFFFFFF^(_sudoku_n|_sudoku_an)^b; else map[xx][yy]&=0xFFFFFFFF^b; }
        for (x=0;x<9;x++ )                   { for (xx=0;xx<9;xx++) n[xx]=0; col(x  ) { a=map[xx][yy]; a=(a|(a>>10))&_sudoku_n; for (b=0;b<9;b++) if (DWORD(a&(_sudoku_1<<b))!=0) { n[b]++; nx[b]=xx; ny[b]=yy; }} for (b=_sudoku_1|_sudoku_a1,k=0;k<9;k++,b<<=1) if (n[k]==1) col(x  ) if (DWORD(map[xx][yy]&_sudoku_fix)==0) if ((xx==nx[k])&&(yy==ny[k])) map[xx][yy]&=0xFFFFFFFF^(_sudoku_n|_sudoku_an)^b; else map[xx][yy]&=0xFFFFFFFF^b; }
        for (x=0;x<9;x+=3) for (y=0;y<9;y+=3){ for (xx=0;xx<9;xx++) n[xx]=0; sqr(x,y) { a=map[xx][yy]; a=(a|(a>>10))&_sudoku_n; for (b=0;b<9;b++) if (DWORD(a&(_sudoku_1<<b))!=0) { n[b]++; nx[b]=xx; ny[b]=yy; }} for (b=_sudoku_1|_sudoku_a1,k=0;k<9;k++,b<<=1) if (n[k]==1) sqr(x,y) if (DWORD(map[xx][yy]&_sudoku_fix)==0) if ((xx==nx[k])&&(yy==ny[k])) map[xx][yy]&=0xFFFFFFFF^(_sudoku_n|_sudoku_an)^b; else map[xx][yy]&=0xFFFFFFFF^b; }

        // #3 if the same number only in single row/col for single square clear the row/col for other squares
        for (x=0;x<9;x+=3)
         for (y=0;y<9;y+=3)
            {
            // nx[],ny[] = histogram of x,y per each number
            for (xx=0;xx<9;xx++) { nx[xx]=0; ny[xx]=0; } sqr(x,y) for (a=map[xx][yy],b=_sudoku_1|_sudoku_a1,k=0;k<9;k++,b<<=1) if (DWORD(a&b)!=0) { nx[k]|=1<<xx; ny[k]|=1<<yy; }
            // check row/col for exclusive occurence and clear the rest if found
            for (yy=y;yy<y+3;yy++) for (b=_sudoku_1|_sudoku_a1,k=0;k<9;k++,b<<=1) if (ny[k]==1<<yy) for (xx=0;xx<9;xx++) if ((xx<x)||(xx>=x+3)) map[xx][yy]&=0xFFFFFFFF^b;
            for (xx=x;xx<x+3;xx++) for (b=_sudoku_1|_sudoku_a1,k=0;k<9;k++,b<<=1) if (nx[k]==1<<xx) for (yy=0;yy<9;yy++) if ((yy<y)||(yy>=y+3)) map[xx][yy]&=0xFFFFFFFF^b;
            }

        // #4 same pair only found in single row/col/sqr (clear the rest)
        // [***ToDo***]

        // set singleton unused numbers as used
        for (x=0;x<9;x++)
         for (y=0;y<9;y++)
            {
            a=(map[x][y]>>10)&_sudoku_n;
            single(a)
                {
                map[x][y]&=0xFFFFFFFF^_sudoku_n;
                map[x][y]|=a;
                break;
                }
            }
        }
    s_check();      
    _redraw=true;
    #undef single
    #undef row
    #undef col
    #undef sqr
    }
//---------------------------------------------------------------------------
//---------------------------------------------------------------------------
#endif
//---------------------------------------------------------------------------

And usage:

//$$---- Form CPP ----
//---------------------------------------------------------------------------
#include <vcl.h>
#pragma hdrstop
#include "Unit1.h"
#include "sudoku.h"
//---------------------------------------------------------------------------
#pragma package(smart_init)
#pragma resource "*.dfm"
TForm1 *Form1;
sudoku gam;
//---------------------------------------------------------------------------
void TForm1::draw()
    {
    if (gam._redraw) gam.draw();
    Canvas->Draw(0,0,gam.bmp);
    }
//---------------------------------------------------------------------------
__fastcall TForm1::TForm1(TComponent* Owner):TForm(Owner)
    {
    int S[9*9]=
        {
        8,0,0, 0,2,4, 0,0,3,
        0,0,0, 0,0,0, 0,0,0,
        0,4,0, 3,6,0, 0,0,0,

        0,0,0, 0,0,0, 0,0,0,
        4,6,0, 0,5,9, 0,0,8,
        2,0,9, 0,0,8, 1,0,0,

        3,0,0, 0,0,0, 6,0,0,
        0,5,1, 7,0,0, 0,0,4,
        0,9,0, 0,0,1, 3,0,0,
        };
    gam.init(S);
    }
//---------------------------------------------------------------------------
void __fastcall TForm1::FormPaint(TObject *Sender) { draw(); }
void __fastcall TForm1::FormResize(TObject *Sender) { gam.resize(ClientWidth,ClientHeight); }
void __fastcall TForm1::tim_updTimer(TObject *Sender) { if (gam._redraw) draw(); }
void __fastcall TForm1::FormKeyDown  (TObject *Sender, WORD &Key, TShiftState Shift){ gam.key(Key,Shift); }
void __fastcall TForm1::FormMouseMove(TObject *Sender,                      TShiftState Shift, int X, int Y){ gam.mouse(X,Y,Shift); }
void __fastcall TForm1::FormMouseDown(TObject *Sender, TMouseButton Button, TShiftState Shift, int X, int Y){ gam.mouse(X,Y,Shift); }
void __fastcall TForm1::FormMouseUp  (TObject *Sender, TMouseButton Button, TShiftState Shift, int X, int Y){ gam.mouse(X,Y,Shift); }
//---------------------------------------------------------------------------

Its the code form my VCL app (single form with single timer on it) so just port the events to your environment and ignore the rest. The sudoku class uses VCL encapsulated GDI so that is the stuff that is need to be ported (just lines rectangles and text).

The solver is fully enclosed within sudoku::solve() and hope its commented enough (does exactly what I described above). Here screenshot after solving (space key):

the _debug_N (N:7) holds the count of iterations needed for solution. Also I did not do any optimizations yet (do not see any point as the solver is done sooner than i release the key). Hope this helps someone a bit.

There are quite a few other rules to implement:

  • Sudoku Solving Strategies
  • Sudoku Solving Techniques


标签： c++ algorithm sudoku
举报

收藏的人(0)

Ta的文章 更多文章
登录 后发表评论
0条评论
还没有人评论过~