Sudoku Programmers Forum Index

 
 FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups   RegisterRegister   ProfileProfile   Log inLog in          Games  Calendar

Log in to check your private messagesLog in to check your private messages   

short C-solver with source (exact-cover-algorithm)
Goto page 1, 2  Next
 
Post new topic   Reply to topic    Sudoku Programmers Forum Index -> Software
View previous topic :: View next topic  
Author Message
dukuso

Joined: 14 Jul 2005
Posts: 424
:
Location: germany

Items
PostPosted: Mon Jul 25, 2005 6:30 am    Post subject: short C-solver with source (exact-cover-algorithm) Reply with quote

Code:


// simple and short sudoku-solver based on an
// exact-cover-problem-solver
// by Guenter Stertenbrink,sterten@aol.com   compiled with GCC3.2
// some explanations are at : http://magictour.free.fr/suexco.txt
// Windows/DOS-executable is at : http://magictour.free.fr/suexco.exe

#include <stdio.h>
# define N 3
# define N2 N*N
# define N4 N2*N2
 int A[N2+1][N2+1],Rows[4*N4+1],Cols[N4*N2+1],Row[4*N4+1][N2+1];
 int Col[N4*N2+1][5],Ur[N4*N2+1],Uc[4*N4+1],C[N4+1],I[N4+1];
 int i,j,k,r,c,d,n=N4*N2,m=4*N4,x,y,s,Node[N4+1];
 int max,min,clues,match,sudokus=0;
 char l[36]="-123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";
 FILE *file;

int main(int argc,char*argv[]){
  if(argc<2){m5:printf("\nusage:suexco file\n\n");
  printf("     prints the number of solutions of the sudoku-puzzles in file\n");
  printf("      empty cells are -.* or 0 , other nondigit-characters are");
  printf(" ignored\n");exit(1);}

r=0;for(x=1;x<=N2;x++)for(y=1;y<=N2;y++)for(s=1;s<=N2;s++){
r++;Cols[r]=4;Col[r][1]=x*N2-N2+y;Col[r][2]=(N*((x-1)/N)+(y-1)/N)*N2+s+N4;
Col[r][3]=x*N2-N2+s+N4*2;Col[r][4]=y*N2-N2+s+N4*3;}
for(c=1;c<=m;c++)Rows[c]=0;
for(r=1;r<=n;r++)for(c=1;c<=Cols[r];c++){
  x=Col[r][c];Rows[x]++;Row[x][Rows[x]]=r;}

 if((file=fopen(argv[1],"rb"))==NULL)
    {fclose(file);printf("\nfile-error\n\n");goto m5;}
m8:i=0;for(x=1;x<=N2;x++)for(y=1;y<=N2;y++){
   m1:if(feof(file)){if(sudokus)exit(0);
      printf("\nonly %i entries found in file %s\n",i,argv[1]);goto m5;}
   c=fgetc(file);j=0;if(c=='-' || c=='.'|| c=='0' || c=='*')goto m7;
   while(l[j]!=c && j<=N2)j++;if(j>N2)goto m1;
   m7:A[x][y]=j;i++;}

 for(i=0;i<=n;i++)Ur[i]=0;for(i=0;i<=m;i++)Uc[i]=0;
 for(i=1;i<=N4;i++)Node[i]=0;clues=0;
 for(x=1;x<=N2;x++)for(y=1;y<=N2;y++)
   if(A[x][y]){clues++;r=x*N4-N4+y*N2-N2+A[x][y];
     for(j=1;j<=Cols[r];j++){d=Col[r][j];Uc[d]++;
       for(k=1;k<=Rows[d];k++){Ur[Row[d][k]]++;}}}

   i=clues;
m2:i++;I[i]=0;
  min=n+1;
  for(c=1;c<=m;c++){
    if(Uc[c]==0){match=0;for(r=1;r<=Rows[c];r++)
                        if(Ur[Row[c][r]]==0)match++;
      if(match<min){min=match;C[i]=c;}}}
  if(min==0 || min>n)goto m4;
m3:c=C[i];I[i]++;if(I[i]>Rows[c])goto m4;
   r=Row[c][I[i]];if(Ur[r])goto m3;
//x=(r-1)/N4+1;y=((r-1)%N4)/N2+1;s=(r-1)%(N2)+1;A[x][y]=s;
//if(i==N4)output;
   for(j=1;j<=Cols[r];j++){d=Col[r][j];Uc[d]++;
      for(k=1;k<=Rows[d];k++)Ur[Row[d][k]]++;}
   Node[i]++;goto m2;
m4:i--;c=C[i];r=Row[c][I[i]];
   for(j=1;j<=Cols[r];j++){d=Col[r][j];Uc[d]--;
      for(k=1;k<=Rows[d];k++){Ur[Row[d][k]]--;}}
   if(i>clues)goto m3;
   sudokus++;printf("%i solutions for sudoku #%i\n",Node[N4],sudokus);
goto m8;
}



Last edited by dukuso on Sun Oct 02, 2005 9:50 am; edited 4 times in total
Back to top
View user's profile Send private message Send e-mail Visit poster's website
jbum

Joined: 14 Aug 2005
Posts: 14
:
Location: Los Angeles

Items
PostPosted: Sun Aug 14, 2005 9:49 pm    Post subject: thanks Reply with quote

This program is quite fast, although a little tough to decipher, due to the formatting. Here's a version that is a bit more readable (to me).

Code:

#include <stdio.h>

# define N 3
# define N2 N*N
# define N4 N2*N2

int A[N2+1][N2+1],Rows[4*N4+1],Cols[N4*N2+1],Row[4*N4+1][N2+1];
int Col[N4*N2+1][5],Ur[N4*N2+1],Uc[4*N4+1],C[N4+1],I[N4+1],Node[N4+1];
int i,j,k,r,c,d,n=N4*N2,m=4*N4,x,y,s;
int max,min,clues,match;
char l[65]="-123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz#*~";
FILE *file;

int main(int argc,char*argv[])
{
   if(argc<2)
   {
m5:
      printf("\nusage:suexco file\n\n");

      printf(" prints the number of solutions of the sudoku-puzzle in file\n");
      printf(" empty cells are -.* or 0 , other nondigit-characters are");
      printf(" ignored\n");exit(1);
   }

   if((file=fopen(argv[1],"rb"))==NULL)
   {
      fclose(file);
      printf("\nfile-error\n\n");
      goto m5;
   }
   i=0;
   for (x=1;x<=N2;x++) {
      for (y=1;y<=N2;y++) {
m1:
         if (feof(file)) {
            printf("\nonly %i sudoku-entries found in file %s\n",i,argv[1]);
            goto m5;
         }
         c=fgetc(file);
         j=0;
         if (c=='-' || c=='.'|| c=='0' || c=='*')
            goto m7;
         while (l[j] != c && j<=N2)
            j++;
         if(j>N2)
            goto m1;
m7:
         A[x][y]=j;
         i++;
      }
   }

   r=0;
   for (x=1;x<=N2;x++) {
      for (y=1;y<=N2;y++) {
         for (s=1;s<=N2;s++) {
            r++;
            Cols[r]=4;
            Col[r][1]=x*N2-N2+y;
            Col[r][2]=(N*((x-1)/N)+(y-1)/N)*N2+s+N4;
            Col[r][3]=x*N2-N2+s+N4*2;
            Col[r][4]=y*N2-N2+s+N4*3;
         }
      }
   }
   for (c=1;c<=m;c++)
      Rows[c]=0;
   for (r=1;r<=n;r++) {
      for(c=1;c<=Cols[r];c++) {
         x=Col[r][c];
         Rows[x]++;
         Row[x][Rows[x]]=r;
      }
   }
   for (i=0; i<=n; i++)
      Ur[i]=0;
   for (i=0; i<=m; i++)
      Uc[i]=0;
   for (x=1;x<=N2;x++) {
      for (y=1;y<=N2;y++) {
         if(A[x][y]) {
            clues++;
            r=x*N4-N4+y*N2-N2+A[x][y];
            for(j=1;j<=Cols[r];   j++) {
               d=Col[r][j];
               Uc[d]++;
               for (k=1;k<=Rows[d];k++) {
                  Ur[Row[d][k]]++;
               }
            }
         }
      }
   }

   i=0;
m2:
   i++;
   I[i]=0;
   min=n+1;
   for (c=1;c<=m;c++) {
      if (Uc[c]==0) {
         match=0;
         for (r=1;r<=Rows[c];r++) {
            if (Ur[Row[c][r]]==0)
               match++;
         }
         if(match<min) {
            min=match;
            C[i]=c;
         }
      }
   }
   if (min==0 || min>n)
      goto m4;
m3:
   c=C[i];
   I[i]++;
   if (I[i] > Rows[c])
      goto m4;
   r=Row[c][I[i]];
   if (Ur[r])
      goto m3;
//x=(r-1)/N4+1;y=((r-1)%N4)/N2+1;s=(r-1)%(N2)+1;A[x][y]=s;if(clues+i==N4)output;
   for (j=1;j<=Cols[r];j++) {
      d=Col[r][j];
      Uc[d]++;
      for (k=1;k<=Rows[d];k++)
         Ur[Row[d][k]]++;
   }
   Node[i]++;
   goto m2;
m4:
   i--;
   c=C[i];
   r=Row[c][I[i]];
   for (j=1;j<=Cols[r];j++) {
      d=Col[r][j];
      Uc[d]--;
      for (k=1;k<=Rows[d];k++)
      {
         Ur[Row[d][k]]--;
      }
   }
   if(i>0)
      goto m3;
   printf("\n%i solutions\n",Node[N4-clues]);
}


_________________
http://www.krazydad.com/
Back to top
View user's profile Send private message Visit poster's website
dukuso

Joined: 14 Jul 2005
Posts: 424
:
Location: germany

Items
PostPosted: Mon Aug 15, 2005 5:59 am    Post subject: Reply with quote

OK,thanks.
I don't think your formatting is more readable but I'm
aware that many (most?) people prefer it your way and that's
reason enough to post it.
Mine is more compact,can be printed on one page, parts which belong
together logically are in one line or block and appear on one screen-page
when editing. I'll make some small changes,though by editing the old post.
I.e. post it as "code" since else the board-software messes
up the indentations at the start of lines.

I have one small but significant change, which makes it
about 5 times faster for average 9*9 sudokus, which I will
post in 2 weeks (or send by email on request) so not to spoil
the vb6-contest mentioned in another post by Merri.
The currently best entry there is still about 2-3 times faster than
my improved version but it's probably more complicated and can't be
easily adapted to 16*16 etc. All entries will be published there
in 2 weeks.

After the sudoku settings were made, the main backtracking routine
(starting with i=clues;) works for every exact-cover problem
like n-queens,pentominoes,QCP, etc. (see Knuth) but we can use
it here to do some lookahead to optimize and benchmark it for sudoku.
If someone has ideas how to improve it or has benchmarked the effect
of including some sudoku-rules, report it here !


idea:
keep and update a permutation P[N4*4] of the columns where the
short columns (those with only 1 or 2 unmarked matching rows)
come first, while columns which lead to long branches are put
towards the end
track back after another nested furcation (min>2) at nest level nl
and choose another branch at nested level nl-1



there must be some small piece of code which I could include into
above program, and which lets me handle a nested lookahead
dynamically !
The lookahead level will depend on the distance from
the root of the search-tree.


Guenter.
Back to top
View user's profile Send private message Send e-mail Visit poster's website
dildog

Joined: 29 Aug 2005
Posts: 1
:

Items
PostPosted: Mon Aug 29, 2005 11:01 pm    Post subject: Re: short C-solver with source (exact-cover-algorithm) Reply with quote

Nice code but at m2 can variable 'i' become 82 and then execute

I[i] = 0;

when array I indices run 0..81

I suppose the consequences depend on what exactly, in memory, lies next to I[81]
Back to top
View user's profile Send private message
dukuso

Joined: 14 Jul 2005
Posts: 424
:
Location: germany

Items
PostPosted: Tue Aug 30, 2005 3:06 am    Post subject: Reply with quote

thanks. That's easy to fix. Unfortunately C doesn't check
the array-bounds on execution and I don't know how to overcome it.
There is also a problem with the outcommented (//) output line,
where I divide by N4 but N4 is not of type int.

I have another change which gives about 5fold speed-increase,
bu then the source no longer fits on one printer page ;-(

I'll post the update soon.
Back to top
View user's profile Send private message Send e-mail Visit poster's website
Merri

Joined: 02 Aug 2005
Posts: 44
:

Items
PostPosted: Tue Aug 30, 2005 3:17 am    Post subject: Reply with quote

Make the comment area one line only and shrink the font size? Wink I guess there is no harm done to others if you post the longer source. Haven't spent time seeing how this code works, and I'm too tired even now.
Back to top
View user's profile Send private message
dukuso

Joined: 14 Jul 2005
Posts: 424
:
Location: germany

Items
PostPosted: Tue Aug 30, 2005 3:41 am    Post subject: Reply with quote

Merri wrote:
Make the comment area one line only and shrink the font size? ;) I guess there is no harm done to others if you post the longer source. Haven't spent time seeing how this code works, and I'm too tired even now.


I think I'll do it on 2 pages.
If with longer source you mean, what jbum posted, then I haven't it.
I worked with the program how it is posted.
There is already an updated faster version with more features
at http://magictour.free.fr/suexk.exe
source attached to the executable
but I want to include some more improvements before posting.
For an explanation of the exact-cover algorithm see
http://magictour.free.fr/suexco.txt
or Knuth's nice "dancing links" paper.

I also tried it on QWH instances now, it solves
qwhdec.order30.holes316.1.col GOM1
http://www.setbb.com/phpbb/viewtopic.php?p=1424&mforum=sudoku#1424
in a few seconds, but I had no luck yet with the larger instances.


-Guenter.
Back to top
View user's profile Send private message Send e-mail Visit poster's website
dseiler

Joined: 06 Sep 2005
Posts: 1
:

Items
PostPosted: Tue Sep 06, 2005 8:54 am    Post subject: Very fast Java Sudoku Solver using Knuths dancing links Reply with quote

Hi everybody,
Reading your interesting discussion about solving the exact cover problem, I wrote a little program in Java using the dancing links alogrithm proposed by Donald Knuth http://www-cs-faculty.stanford.edu/~knuth/preprints.html. I optimized the program as much as I could and I believe it is pretty fast now. Here is the source code. Enjoy!

Code:


import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;

/**
 * @author Daniel Seiler
 *
 */
public class ExactCoverSolver {

   // the matrix has the following forma
   // _______________________________________________________________________________________________
   //         |           1            |           2            |  |            n           |        |
   //         |r1r2..r9c1c2..c9b1b2..b9|r1r2..r9c1c2..c9b1b2..b9|..|r1r2..r9c1c2..c9b1b2..b9|123..n*n|
   // --------|------------------------|------------------------|--|------------------------|--------|
   // 1 -> 1,1|
   // 1 -> 1,2|
   //
   private Header root = null;
   private List solution = new ArrayList();
   private int solutionCounter = 0;
   private int b = 2; // number of blocks per row
   private int n; // number of columns/rows/blocks
   private int threeN;
   private int twoN;
   private int threeNsquare;
   private int nSquare;
   private int nPow3;
   
   public static void main(String[] args) {   
      // create all the solutions of a 4x4 Sudoku
      new ExactCoverSolver().run(null);
      
      // find the solution for this 4x4 Sudoku
      /*
       * |1|2| | |
       * | | | | |
       * | | | | |
       * |4| | |3|
       */
      new ExactCoverSolver().run(new int[][]{{1,2,0,0},
                                    {0,0,0,0},
                                    {0,0,0,0},
                                    {4,0,0,3}});
      
      // find the only solution this 9x9 Sudoku
      
      new ExactCoverSolver(3).run(new int[][]{
                              {8,0,0,6,0,0,5,0,1},
                                 {6,0,7,0,0,3,0,2,0},
                              {0,5,0,0,2,0,0,0,0},
                              {0,0,0,1,8,0,0,3,0},
                              {0,0,6,9,0,5,1,0,0},
                              {0,4,0,0,6,2,0,0,0},
                              {0,0,0,0,9,0,0,6,0},
                              {0,6,0,4,0,0,2,0,5},
                              {4,0,5,0,0,0,0,0,0}});

      
      /* only 17 filled in
      new ExactCoverSolver(3).run(new int[][]{
               {0,0,0,0,0,0,0,1,2},
               {0,0,0,0,3,5,0,0,0},
               {0,0,0,6,0,0,0,7,0},
               {7,0,0,0,0,0,3,0,0},
               {0,0,0,4,0,0,8,0,0},
               {1,0,0,0,0,0,0,0,0},
               {0,0,0,1,2,0,0,0,0},
               {0,8,0,0,0,0,0,4,0},
               {0,5,0,0,0,0,6,0,0}});*/
      

   }
   
   public ExactCoverSolver(int b) {
      this.b = b;
      init();
   }
   
   public ExactCoverSolver() {
      init();
   };
   
   private void init() {
      n = b * b;
      nSquare = n*n;
      twoN = 2*n;
      threeN = 3*n;
      threeNsquare = 3*nSquare;
      nPow3 = nSquare*n;
   }
   
   private void run(int[][] initialMatrix) {
      long start = System.currentTimeMillis();
      short[][] matrix = createMatrix(initialMatrix);
      //printMatrix(matrix);
      Header doubleLinkedList = createDoubleLinkedLists(matrix);      
      search(0);
      long end = System.currentTimeMillis();
      System.out.println("duration (ms): "+Long.toString(end-start));
   }
   
   private short[][] createMatrix(int[][] initialMatrix) {      
      // create the prefill array
      int[][] prefill = null;
      if(initialMatrix != null) {
         // sanitiy check
         if(initialMatrix.length != n) {
            throw new RuntimeException("dimension of initial matrix ("+initialMatrix.length+") does not match the given row/column number: "+n);
         }
         List prefillList = new ArrayList();
         int count = 0;
         for(int r = 0; r < n; r++) {
            for(int c = 0; c < n; c++) {
               if(initialMatrix[r][c] > 0) {
                  prefillList.add(new int[]{initialMatrix[r][c],r,c});
                  count++;
               }
            }
         }
         prefill = new int[count][];
         for(int i = 0; i < count; i++) {
            prefill[i] = (int[])prefillList.get(i);
         }
      }
      
      // the matrix has the following dimensions
      // rows: number of cells (n*n) multiplied by number of possible digits (n)
      // columns: number of columns plus number of rows plus number of blocks (3*n)
      //          multiplied bz number of different digits (n) plus number of cells (n*n)
      short[][] matrix = new short[nPow3][4*nSquare];
      
      // iterate over all the possible digits d
      for(int d = 0; d < n; d++) {
         // iterate over all the possible rows r
         for(int r = 0; r < n; r++) {
            // iterator over all the possible columns c
            for(int c = 0; c < n; c++) {
               if(!cellIsFilled(d,r,c,prefill)) {
                  int rowIndex = c + (n * r) + (n * n * d);
                  // there are for 1's in each row, one for each constraint
                  int blockIndex = ((c / b) + ((r / b) * b));
                  int colIndexRow = threeN*d+r;
                  int colIndexCol = threeN*d+n+c;
                  int colIndexBlock = threeN*d+twoN+blockIndex;
                  int colIndexSimple = threeN*n+(c+n*r);
                  // fill in the 1's
                  matrix[rowIndex][colIndexRow] = 1;
                  matrix[rowIndex][colIndexCol] = 1;
                  matrix[rowIndex][colIndexBlock] = 1;
                  matrix[rowIndex][colIndexSimple] = 1;
               }
            }
         }
      }
      return matrix;
   }
   
   /**
    * check if the cell that should be filled is allready prefilled
    * with a digit
    * the prefill two dimension array has the following format:
    * [{nr}][{digit,row,column}]
    * @param prefill
    * @return
    */
   private boolean cellIsFilled(int digit, int row, int col, int[][] prefill) {
      boolean cellIsFilled = false;
      if(prefill != null) {
         for(int i = 0; i < prefill.length; i++) {
            int d = prefill[i][0]-1;
            int r = prefill[i][1];
            int c = prefill[i][2];
            // calculate the block indices
            int blockStartIndexCol = (c/b)*b;
            int blockEndIndexCol = blockStartIndexCol + b;
            int blockStartIndexRow = (r/b)*b;
            int blockEndIndexRow = blockStartIndexRow + b;
            if(d != digit && row == r && col == c) {
               cellIsFilled = true;
            } else if((d == digit) && (row == r || col == c) && !(row == r && col == c)) {
               cellIsFilled = true;
            } else if((d == digit) && (row > blockStartIndexRow) && (row < blockEndIndexRow) && (col > blockStartIndexCol) && (col < blockEndIndexCol) && !(row == r && col == c)) {
               cellIsFilled = true;
            }
         }
      }
      return cellIsFilled;
   }
   
   private Header createDoubleLinkedLists(short[][] matrix) {
      root = new Header();
      // create the headers
      Header currentHeader = root;
      for(int col = 0; col < matrix[0].length; col++) {
         // create the header name
         HeaderInfo info = new HeaderInfo();
         if(col < threeNsquare) {
            // which digit this column covers?
            int digit = (col / (threeN)) + 1;
            info.digit = digit;
            // is it for a row, column or block?
            int index = col-(digit-1)*threeN;
            if(index < n) {
               info.type = HeaderInfo.TYPE_ROW;
               info.position = index;
            } else if(index < twoN) {
               info.type = HeaderInfo.TYPE_COL;
               info.position = index-n;
            } else {
               info.type = HeaderInfo.TYPE_BLOCK;
               info.position = index-twoN;
            }            
         } else {
            info.type = HeaderInfo.TYPE_CELL;
            info.position = col - threeNsquare;
         }
         currentHeader.right = new Header();
         currentHeader.right.left = currentHeader;
         currentHeader = (Header)currentHeader.right;
         currentHeader.info = info;
         currentHeader.header = currentHeader;
      }
      currentHeader.right = root;
      root.left = currentHeader;
      
      // iterate over all the rows
      for(int row = 0; row < matrix.length; row++) {
         // iterator over all the columns
         currentHeader = (Header)root.right;
         X lastCreatedElement = null;
         X firstElement = null;
         for(int col = 0; col < matrix[row].length; col++) {
            if(matrix[row][col] == 1) {
               // create a new data element and link it
               X colElement = currentHeader;
               while(colElement.down != null) {
                  colElement = colElement.down;
               }
               colElement.down = new X();
               if(firstElement == null) {
                  firstElement = colElement.down;
               }
               colElement.down.up = colElement;
               colElement.down.left = lastCreatedElement;
               colElement.down.header = currentHeader;
               if(lastCreatedElement != null) {
                  colElement.down.left.right = colElement.down;
               }
               lastCreatedElement = colElement.down;
               currentHeader.size++;
            }
            currentHeader = (Header)currentHeader.right;
         }
         // link the first and the last element
         if(lastCreatedElement != null) {
            lastCreatedElement.right = firstElement;
            firstElement.left = lastCreatedElement;
         }
      }
      currentHeader = (Header)root.right;
      // link the last column elements with the coresponding headers
      for(int i = 0; i < matrix[0].length; i++) {
         X colElement = currentHeader;
         while(colElement.down != null) {
            colElement = colElement.down;
         }
         colElement.down = currentHeader;
         currentHeader.up = colElement;
         currentHeader = (Header)currentHeader.right;
      }
      return root;
   }
   
   private void printMatrix(int[][] matrix) {
      for(int row = 0; row < matrix.length; row++) {
         for(int col = 0; col < matrix[row].length; col++) {
            System.out.print(matrix[row][col]);
         }
         System.out.println("");
      }
   }
   
   private void search(int k) {
      // Abbruchbedingung
      if(root.right == root) {
         return;
      }
      Header c = chooseColumn();
      coverColumn(c);
      X r = c.down;
      while(r != c) {
               
         if(k < solution.size()) {
            solution.remove(k);
         }         
         solution.add(k,r);
         
         X j = r.right;
         while(j != r) {
            coverColumn(j.header);
            j = j.right;
         }
         search(k+1);
         
         // are r and c realy overwritten here??
         X r2 = (X)solution.get(k);
         //c = r.header;
         X j2 = r2.left;
         while(j2 != r2) {
            uncoverColumn(j2.header);
            j2 = j2.left;
         }
         r = r.down;
         
         // here we can distinguis the different solutions
         if(k == n*n-1) {
            solutionCounter++;
            System.out.println("Solution: "+solutionCounter);
            printSolution();
            System.out.println("");
         }

      }
      uncoverColumn(c);
   }
   
   private void printSolution() {
      int[] result = new int[n*n];
      for(Iterator it = solution.iterator(); it.hasNext(); ) {
         int digit = -1;
         int cell = -1;
         X element = (X)it.next();
         X next = element;
         do {
            if(next.header.info.type == HeaderInfo.TYPE_ROW) {
               digit = next.header.info.digit;
            } else if(next.header.info.type == HeaderInfo.TYPE_CELL) {
               cell = next.header.info.position;
            }
            next = next.right;
         } while(element != next);
         result[cell] = digit;
      }
      // print the solution
      for(int i = 0; i<result.length;i++) {
         if(i > 0 && (i % n) == 0) {
            System.out.println("|");
         }
         System.out.print("|"+result[i]);
      }
      System.out.println("|");
   }
   
   private Header chooseColumn() {
      // its mostly efficient to always choose the column with the smales size      
      Header h = (Header)root.right;
      Header smalest = h;
      while(h.right != root) {
         h = (Header)h.right;
         if(h.size < smalest.size) {
            smalest = h;
         }         
      }      
      return smalest;
   }
   
   private void coverColumn(X column) {
      column.right.left = column.left;
      column.left.right = column.right;
      X i = column.down;
      while(i != column) {
         X j = i.right;
         while(j != i) {
            j.down.up = j.up;
            j.up.down = j.down;
            j.header.size--;
            j = j.right;
         }
         i = i.down;
      }
   }

   private void uncoverColumn(X column) {
      X i = column.up;
      while(i != column) {
         X j = i.left;
         while(j != i) {
            j.header.size++;
            j.down.up = j;
            j.up.down = j;
            j = j.left;
         }
         i = i.up;
      }
      column.right.left = column;
      column.left.right = column;
   }
   
   class X {
      X left;
      X right;
      X up;
      X down;
      Header header;
   }
   
   class Header extends X {
      int size = 0;
      HeaderInfo info;
   }
   
   class HeaderInfo {
      static final int TYPE_ROW = 0;
      static final int TYPE_COL = 1;
      static final int TYPE_BLOCK = 2;
      static final int TYPE_CELL = 3;
      
      int type = -1;
      int digit = -1;
      int position = -1;
      
      public String toString() {
         // create the header name
         StringBuffer name = new StringBuffer();
         if(type == TYPE_ROW) {
            name.append("Digit ");
            name.append(digit);
            name.append(" in row ");
         } else if(type == TYPE_COL) {
            name.append("Digit ");
            name.append(digit);
            name.append(" in column ");
         } else if(type == TYPE_BLOCK) {
            name.append("Digit ");
            name.append(digit);
            name.append(" in block ");
         } else if(type == TYPE_CELL) {
            name.append("Digit in cell ");
         }
         name.append(position+1);
         return name.toString();
      }
   }
}


Back to top
View user's profile Send private message
dukuso

Joined: 14 Jul 2005
Posts: 424
:
Location: germany

Items
PostPosted: Tue Sep 06, 2005 1:03 pm    Post subject: Re: Very fast Java Sudoku Solver using Knuths dancing links Reply with quote

dseiler wrote:
Hi everybody,
Reading your interesting discussion about solving the exact cover problem, I wrote a little program in Java using the dancing links alogrithm proposed by Donald Knuth http://www-cs-faculty.stanford.edu/~knuth/preprints.html. I optimized the program as much as I could and I believe it is pretty fast now. Here is the source code. Enjoy!

unfortunately I don't understand Java.
Can you post benchmarks ? E.g. for
http://magictour.free.fr/top95

I had a small improvement on the code above, which gave a factor
of 5. I'll post it later. Jim's program was faster than my new one
and as I can see he didn't use that trick, so I
was wondering if a factor of 3 is still lurking...
Well, Jim tried it and he say no.


Last edited by dukuso on Sun Sep 11, 2005 8:53 am; edited 1 time in total
Back to top
View user's profile Send private message Send e-mail Visit poster's website
dukuso

Joined: 14 Jul 2005
Posts: 424
:
Location: germany

Items
PostPosted: Tue Sep 06, 2005 1:19 pm    Post subject: Reply with quote

Code:


/* speed-optimized version of a
   simple and short sudoku-solver based on an exact-cover-problem-solver
   put into public domain by Guenter Stertenbrink,sterten@aol.com
   compiles well with GCC3.2
   some explanations are at : http://magictour.free.fr/suexco.txt
   a not speed-optimized DOS/Windows-executable with more features
   and attached source-code is at http://magictour.free.fr/suexk.exe
   Report errors,bugs,improvement suggestions,feedback to sterten@aol.com
   there are other programs here which are ~5 times faster, but
   they are not public domain and presumably more complicated ;-)
   This algo only searches for "naked single" and "hidden single"
   I'm not 100% sure, whether this version works correctly with
   the M1-array and rows-deletion before start
*/

#include <stdio.h>
#include <stdlib.h>
# include <time.h>
# define N 3     // change this for larger sudokus , N=4 for 16*16 etc.
# define N2 N*N
# define N4 N2*N2
int A[N2+1][N2+1],Rows[4*N4+1],Cols[N4*N2+1],Row[4*N4+1][N2+1],Col[N4*N2+1][5];
int Ur[N4*N2+1],Uc[4*N4+1],V[4*N4+1],C[N4+1],I[N4+9],Node[N4+1],M1[N4*N2];
int i,j,k,l,m0,m1,r,p,r1,c,c1,c2,n=N4*N2,m=4*N4,x,y,s,min,clues,nodes;
char L[66]=".123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz#*~";
FILE *file;


int main(int argc,char*argv[]){clock();
  if(argc<2){m5:printf("\nusage:suexf file [p] \n\n");
  printf(" solves the sudoku-puzzles in file\n");
  printf(" empty cells are -.* or 0 , other nondigit-characters are");
  printf(" ignored\n");
  printf(" p=1 prints the first solution , p>1 prints all , p=0 only counts\n");exit(1);}
  p=0;if(argc>1)sscanf(argv[2],"%i",&p);

r=0;for(x=1;x<=N2;x++)for(y=1;y<=N2;y++)for(s=1;s<=N2;s++){
r++;Cols[r]=4;Col[r][1]=x*N2-N2+y;Col[r][2]=(N*((x-1)/N)+(y-1)/N)*N2+s+N4;
Col[r][3]=x*N2-N2+s+N4*2;Col[r][4]=y*N2-N2+s+N4*3;}
for(c=1;c<=m;c++)Rows[c]=0;
for(r=1;r<=n;r++)for(c=1;c<=Cols[r];c++){
x=Col[r][c];Rows[x]++;Row[x][Rows[x]]=r;}

   if((file=fopen(argv[1],"rb"))==NULL)
     {fclose(file);printf("\nfile-error\n\n");goto m5;}
m6:i=0;for(x=1;x<=N2;x++)for(y=1;y<=N2;y++){
m1:if(feof(file)){if(p<3)printf("time:%i/%i\n",clock(),CLOCKS_PER_SEC);exit(1);}
   c=fgetc(file);j=0;if(c=='-' || c=='.'|| c=='0' || c=='*')goto m7;
   while(L[j]!=c && j<=N2)j++;if(j>N2)goto m1;
m7:A[x][y]=j;i++;}

for(i=1;i<=n;i++)Ur[i]=0;for(i=1;i<=m;i++)Uc[i]=0;for(i=1;i<=N4;i++)Node[i]=0;
clues=0;for(x=1;x<=N2;x++)for(y=1;y<=N2;y++)
if(A[x][y]){clues++;r=x*N4-N4+y*N2-N2+A[x][y];
for(j=1;j<=Cols[r];j++){c1=Col[r][j];if(Uc[c1]){printf("no solution\n");goto m6;}
Uc[c1]++;for(k=1;k<=9;k++){Ur[Row[c1][k]]++;}}}
for(c=1;c<=m;c++){V[c]=0;for(i=1;i<=9;i++)if(Ur[Row[c][i]]==0)
 {V[c]++;x=Row[c][i];Row[c][i]=Row[c][V[c]];Row[c][V[c]]=x;}Rows[c]=V[c];}

   m1=0;for(c=1;c<=m;c++)if(V[c]<2 && Uc[c]==0){m1++;M1[m1]=c;}
   i=clues;m0=0;nodes=0;
m2:i++;I[i]=0;min=n+1;if(i>N4 || m0)goto m4;
m22:if(m1==0)goto m21;if(Uc[M1[m1]]==0 && V[M1[m1]]==1){C[i]=M1[m1];m1--;goto m3;}
   m1--;goto m22;
m21:if(nodes&1) for(c=1;c<=m;c++){if(!Uc[c])if(V[c]<min){min=V[c];C[i]=c;}}
  if(!(nodes&1))for(c=m;c>=1;c--){if(!Uc[c])if(V[c]<min){min=V[c];C[i]=c;}}
//I don't like this very much. Better let c start at random position
   if(min==0 || min>n)goto m4;
m3:c=C[i];I[i]++;if(I[i]>Rows[c])goto m4;
   r=Row[c][I[i]];if(Ur[r])goto m3;m0=0;

   if(p){k=N4;j=N2;x=(r-1)/k+1;y=((r-1)%k)/j+1;s=(r-1)%j+1;A[x][y]=s;
     if(i==N4){for(x=1;x<=N2;x++)for(y=1;y<=N2;y++)printf("%c",L[A[x][y]]);printf("\n");if(p==1)goto m6;}}

   for(j=1;j<=Cols[r];j++){c1=Col[r][j];Uc[c1]++;}
   for(j=1;j<=Cols[r];j++){c1=Col[r][j];
     for(k=1;k<=Rows[c1];k++){r1=Row[c1][k];Ur[r1]++;if(Ur[r1]==1)
       for(l=1;l<=Cols[r1];l++){c2=Col[r1][l];V[c2]--;
         if(Uc[c2]+V[c2]<1)m0=c2;if(Uc[c2]==0 && V[c2]<2){m1++;M1[m1]=c2;}}}}

   nodes++;Node[i]++;goto m2;
m4:i--;c=C[i];r=Row[c][I[i]];if(i==clues){if(p==0)printf("%i\n",Node[N4]);goto m6;}
   for(j=1;j<=Cols[r];j++){c1=Col[r][j];Uc[c1]--;
     for(k=1;k<=Rows[c1];k++){r1=Row[c1][k];Ur[r1]--;
       if(Ur[r1]==0)for(l=1;l<=Cols[r1];l++){c2=Col[r1][l];V[c2]++;}}}
   goto m3;
}



Last edited by dukuso on Mon Oct 03, 2005 2:54 pm; edited 3 times in total
Back to top
View user's profile Send private message Send e-mail Visit poster's website
Bo

Joined: 02 Sep 2005
Posts: 27
:

Items
PostPosted: Sat Oct 01, 2005 9:21 pm    Post subject: Reply with quote

Hi,
there are 2 (minor) problems when compiling this program:
missing #include <stdlib.h> and that L[65] must be L[66].
Otherwise, no problems encountered.

One question though:
If a puzzle having several solutions is printed, only one solution
is presented.
Does the program stop searching after the 1st solution? If so, is there any simple modification that can be made to get more than 1 solution?

Regards
Bo
Back to top
View user's profile Send private message
dukuso

Joined: 14 Jul 2005
Posts: 424
:
Location: germany

Items
PostPosted: Sun Oct 02, 2005 5:20 am    Post subject: Reply with quote

thanks Bo.
I changed the message above yours with the source code.
That should also answer your question.
Can you report your compiler and the benchmark on
http://magictour.free.fr/top2365

?

-Guenter.
Back to top
View user's profile Send private message Send e-mail Visit poster's website
Bo

Joined: 02 Sep 2005
Posts: 27
:

Items
PostPosted: Sun Oct 02, 2005 7:04 am    Post subject: Reply with quote

Thanks for your prompt answer and making this nice
program available!
I have a celeron 2.4 GHz processor and use
the gcc version 3.4.2 (mingw). The program was
compiled with the -O option.

For the benchmark I made 10 runs, the result
centered around 2350/1000 with p=0.

Regards
Bo
Back to top
View user's profile Send private message
Bo

Joined: 02 Sep 2005
Posts: 27
:

Items
PostPosted: Mon Oct 03, 2005 9:48 pm    Post subject: Reply with quote

Hi,
here are some additions/modifications to Guenter's program
so it acts as a "Sudoku X" solver, i.e also the main diagonal cells
must each have a unique digit.
It was surprisingly easy to do, the program seems general enough
to include these kind of things.
The only thing needed was to initialize new columns (18) for the
diagonals, (see code between the comments), increase m by 18 and change the dimension of some arrays.
Hope this is of interest, the modified program is below, the changes are below the comments.

Regards
Bo

Code:

/* modified version for solving "Sudoku X", "Sudoku X"-modifications
made by Bo Haglund */
/* speed-optimized version of a
simple and short sudoku-solver based on an exact-cover-problem-solver
put into public domain by Guenter Stertenbrink,sterten@aol.com
compiles well with GCC3.2
some explanations are at : http://magictour.free.fr/suexco.txt
a not speed-optimized DOS/Windows-executable with more features
and attached source-code is at http://magictour.free.fr/suexk.exe
Report errors,bugs,improvement suggestions,feedback to sterten@aol.com
there are other programs here which are ~5 times faster, but
they are not public domain and presumably more complicated ;-)
This algo only searches for "naked single" and "hidden single"
I'm not 100% sure, whether this version works correctly with
the M1-array and rows-deletion before start
*/

#include <stdio.h>
#include <stdlib.h>
# include <time.h>
# define N 3 // change this for larger sudokus , N=4 for 16*16 etc.
# define N2 N*N
# define N4 N2*N2
/* For "Sudoku X", a few array dimensions have been increased and m is increased by 2*N2 */
int A[N2+1][N2+1],Rows[4*N4+2*N2+1],Cols[N4*N2+1],Row[4*N4+2*N2+1][N2+1],Col[N4*N2+1][7];
int Ur[N4*N2+1],Uc[4*N4+2*N2+1],V[4*N4+2*N2+1],C[N4+1],I[N4+9],Node[N4+1],M1[N4*N2];
int i,j,k,l,m0,m1,r,p,r1,c,c1,c2,n=N4*N2,m=4*N4+2*N2,x,y,s,min,clues,nodes;
char L[66]=".123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz#*~";
// char L[66] is needed here for some compilers
FILE *file;


int main(int argc,char*argv[]){clock();
if(argc<2){m5:printf("\nusage:suexf file [p] \n\n");
printf(" solves the sudoku-puzzles in file\n");
printf(" empty cells are -.* or 0 , other nondigit-characters are");
printf(" ignored\n");
printf(" p=1 prints the first solution , p>1 prints all , p=0 only counts\n");exit(1);}
p=0;if(argc>1)sscanf(argv[2],"%i",&p);

r=0;for(x=1;x<=N2;x++)for(y=1;y<=N2;y++)for(s=1;s<=N2;s++){
r++;Cols[r]=4;Col[r][1]=x*N2-N2+y;Col[r][2]=(N*((x-1)/N)+(y-1)/N)*N2+s+N4;
Col[r][3]=x*N2-N2+s+N4*2;Col[r][4]=y*N2-N2+s+N4*3;
/* Following is additional code for adding columns for "Sudoku X" */
if(x==y){Col[r][5]=s+N4*4;if(x==(1+N2-y)){Cols[r]=6;Col[r][6]=s+N2+N4*4;}else Cols[r]=5;}
else if(x==(1+N2-y)){Cols[r]=5;Col[r][5]=s+N2+N4*4;}
/* End of additions */

for(c=1;c<=m;c++)Rows[c]=0;
for(r=1;r<=n;r++)for(c=1;c<=Cols[r];c++){
x=Col[r][c];Rows[x]++;Row[x][Rows[x]]=r;}

if((file=fopen(argv[1],"rb"))==NULL)
{fclose(file);printf("\nfile-error\n\n");goto m5;}
m6:i=0;for(x=1;x<=N2;x++)for(y=1;y<=N2;y++){
m1:if(feof(file)){if(p<3)printf("time:%i/%i\n",clock(),CLOCKS_PER_SEC);exit(1);}
c=fgetc(file);j=0;if(c=='-' || c=='.'|| c=='0' || c=='*')goto m7;
while(L[j]!=c && j<=N2)j++;if(j>N2)goto m1;
m7:A[x][y]=j;i++;}

for(i=1;i<=n;i++)Ur[i]=0;for(i=1;i<=m;i++)Uc[i]=0;for(i=1;i<=N4;i++)Node[i]=0;
clues=0;for(x=1;x<=N2;x++)for(y=1;y<=N2;y++)
if(A[x][y]){clues++;r=x*N4-N4+y*N2-N2+A[x][y];
for(j=1;j<=Cols[r];j++){c1=Col[r][j];if(Uc[c1]){printf("no solution\n");goto m6;}
Uc[c1]++;for(k=1;k<=9;k++){Ur[Row[c1][k]]++;}}}
for(c=1;c<=m;c++){V[c]=0;for(i=1;i<=9;i++)if(Ur[Row[c][i]]==0)
{V[c]++;x=Row[c][i];Row[c][i]=Row[c][V[c]];Row[c][V[c]]=x;}Rows[c]=V[c];}

m1=0;for(c=1;c<=m;c++)if(V[c]<2 && Uc[c]==0){m1++;M1[m1]=c;}
i=clues;m0=0;nodes=0;
m2:i++;I[i]=0;min=n+1;if(i>N4 || m0)goto m4;
m22:if(m1==0)goto m21;if(Uc[M1[m1]]==0 && V[M1[m1]]==1){C[i]=M1[m1];m1--;goto m3;}
m1--;goto m22;
m21:if(nodes&1) for(c=1;c<=m;c++){if(!Uc[c])if(V[c]<min){min=V[c];C[i]=c;}}
if(!(nodes&1))for(c=m;c>=1;c--){if(!Uc[c])if(V[c]<min){min=V[c];C[i]=c;}}
//I don't like this very much. Better let c start at random position
if(min==0 || min>n)goto m4;
m3:c=C[i];I[i]++;if(I[i]>Rows[c])goto m4;
r=Row[c][I[i]];if(Ur[r])goto m3;m0=0;

if(p){k=N4;j=N2;x=(r-1)/k+1;y=((r-1)%k)/j+1;s=(r-1)%j+1;A[x][y]=s;
  if(i==N4){for(x=1;x<=N2;x++)for(y=1;y<=N2;y++)printf("%c",L[A[x][y]]);printf("\n");if(p==1)goto m6;}}

for(j=1;j<=Cols[r];j++){c1=Col[r][j];Uc[c1]++;}
for(j=1;j<=Cols[r];j++){c1=Col[r][j];
for(k=1;k<=Rows[c1];k++){r1=Row[c1][k];Ur[r1]++;if(Ur[r1]==1)
for(l=1;l<=Cols[r1];l++){c2=Col[r1][l];V[c2]--;
if(Uc[c2]+V[c2]<1)m0=c2;if(Uc[c2]==0 && V[c2]<2){m1++;M1[m1]=c2;}}}}

nodes++;Node[i]++;goto m2;
m4:i--;c=C[i];r=Row[c][I[i]];if(i==clues){if(p==0)printf("%i\n",Node[N4]);goto m6;}
for(j=1;j<=Cols[r];j++){c1=Col[r][j];Uc[c1]--;
for(k=1;k<=Rows[c1];k++){r1=Row[c1][k];Ur[r1]--;
if(Ur[r1]==0)for(l=1;l<=Cols[r1];l++){c2=Col[r1][l];V[c2]++;}}}
goto m3;
}
Back to top
View user's profile Send private message
codelieb

Joined: 23 Feb 2006
Posts: 6
:
Location: Costa Rica

Items
PostPosted: Mon Feb 27, 2006 4:06 pm    Post subject: Reply with quote

Guenter, I have been testing suexf against PSS to see if there is any correlation between the number of nodes generated by the DLX algorithm in solving a puzzle and whether or not PSS is able to solve it (answer: apparently not). Thanks for posting your amazingly well-optimized code! I noticed a minor bug and a couple possible others (see comments marked "MAG" in code, below). Note: I reformatted your code with Christophe Beaudet 's (open source freeware) GC beutifier.

codelieb

P.S. I also experimented with suexrate, to see if it's numerical difficulty rating correlated with PSS's ability to solve puzzles (again: apparently not). Thanks again for posting the code.

Code:
/*
 * speed-optimized version of a simple and short sudoku-solver based on an
 * exact-cover-problem-solver put into public domain by Guenter
 * Stertenbrink,sterten@aol.com compiles well with GCC3.2 some explanations are at
 * : http://magictour.free.fr/suexco.txt a not speed-optimized
 * DOS/Windows-executable with more features and attached source-code is at
 * http://magictour.free.fr/suexk.exe Report errors,bugs,improvement
 * suggestions,feedback to sterten@aol.com there are other programs here which are
 * ~5 times faster, but they are not public domain and presumably more complicated ;
 * -) This algo only searches for "naked single" and "hidden single" I'm not 100%
 * sure, whether this version works correctly with the M1-array and rows-deletion
 * before start
 */
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define N   3   /* change this for larger sudokus , N=4 for 16*16 etc. */
#define N2  N * N
#define N4  N2 * N2
int     A[N2 + 1][N2 + 1], Rows[4 * N4 + 1], Cols[N4 * N2 + 1], Row[4 * N4 + 1][N2 + 1], Col[N4 * N2 + 1][5];
int     Ur[N4 * N2 + 1], Uc[4 * N4 + 1], V[4 * N4 + 1], C[N4 + 1], I[N4 + 9], Node[N4 + 1], M1[N4 * N2];
int     i, j, k, l, m0, m1, r, p, r1, c, c1, c2, n = N4 * N2, m = 4 * N4, x, y, s, min, clues, nodes;
char    L[66] = ".123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz#*~";
FILE    *file;

/*
 =======================================================================================================================
 =======================================================================================================================
 */

int main(int argc, char *argv[])
{
    clock();
    if(argc < 2)
    {
m5:     printf("\nusage:suexf file [p] \n\n");
        printf(" solves the sudoku-puzzles in file\n");
        printf(" empty cells are -.* or 0 , other nondigit-characters are");
        printf(" ignored\n");
        printf(" p=1 prints the first solution , p>1 prints all , p=0 only counts\n");
        exit(1);
    }

    p = 0;
    if(argc > 1) sscanf(argv[2], "%i", &p);

    r = 0;
    for(x = 1; x <= N2; x++)
    {
        for(y = 1; y <= N2; y++)
        {
            for(s = 1; s <= N2; s++)
            {
                r++;
                Cols[r] = 4;
                Col[r][1] = x * N2 - N2 + y;
                Col[r][2] = (N * ((x - 1) / N) + (y - 1) / N) * N2 + s + N4;
                Col[r][3] = x * N2 - N2 + s + N4 * 2;
                Col[r][4] = y * N2 - N2 + s + N4 * 3;
            }
        }
    }

    for(c = 1; c <= m; c++) Rows[c] = 0;
    for(r = 1; r <= n; r++)
        for(c = 1; c <= Cols[r]; c++)
        {
            x = Col[r][c];
            Rows[x]++;
            Row[x][Rows[x]] = r;
        }

    if((file = fopen(argv[1], "rb")) == NULL)
    {
        fclose(file);   /* MAG It's not a good idea to fclose(NULL) as this will crash on many systems. */
        printf("\nfile-error\n\n");
        goto m5;
    }

m6:
    i = 0;
    for(x = 1; x <= N2; x++)
    {
        for(y = 1; y <= N2; y++)
        {
m1:
            if(feof(file))
            {
                if(p < 3) printf("time:%i/%i\n", clock(), CLOCKS_PER_SEC);
                exit(1);
            }

            c = fgetc(file);
            j = 0;
            if(c == '-' || c == '.' || c == '0' || c == '*') goto m7;
            while(L[j] != c && j <= N2) j++;
            if(j > N2) goto m1;
m7:
            A[x][y] = j;
            i++;
        }
    }

    for(i = 1; i <= n; i++) Ur[i] = 0;
    for(i = 1; i <= m; i++) Uc[i] = 0;
    for(i = 1; i <= N4; i++) Node[i] = 0;
    clues = 0;
    for(x = 1; x <= N2; x++)
    {
        for(y = 1; y <= N2; y++)
        {
            if(A[x][y])
            {
                clues++;
                r = x * N4 - N4 + y * N2 - N2 + A[x][y];
                for(j = 1; j <= Cols[r]; j++)
                {
                    c1 = Col[r][j];
                    if(Uc[c1])
                    {
                        printf("no solution\n");
                        goto m6;
                    }

                    Uc[c1]++;
                    for(k = 1; k <= 9; k++) /* MAG - should this 9 be N2 ? */
                    {
                        Ur[Row[c1][k]]++;
                    }
                }
            }
        }
    }

    for(c = 1; c <= m; c++)
    {
        V[c] = 0;
        for(i = 1; i <= 9; i++) /* MAG - should this 9 be N2 ? */
            if(Ur[Row[c][i]] == 0)
            {
                V[c]++;
                x = Row[c][i];
                Row[c][i] = Row[c][V[c]];
                Row[c][V[c]] = x;
            }

        Rows[c] = V[c];
    }

    m1 = 0;
    for(c = 1; c <= m; c++)
        if(V[c] < 2 && Uc[c] == 0)
        {
            m1++;
            M1[m1] = c;
        }

    i = clues;
    m0 = 0;
    nodes = 0;
m2:
    i++;
    I[i] = 0;
    min = n + 1;
    if(i > N4 || m0) goto m4;
m22:
    if(m1 == 0) goto m21;
    if(Uc[M1[m1]] == 0 && V[M1[m1]] == 1)
    {
        C[i] = M1[m1];
        m1--;
        goto m3;
    }

    m1--;
    goto m22;
m21:
    if(nodes & 1)
        for(c = 1; c <= m; c++)
        {
            if(!Uc[c])
                if(V[c] < min)
                {
                    min = V[c];
                    C[i] = c;
                }
        }

    if(!(nodes & 1))
        for(c = m; c >= 1; c--)
        {
            if(!Uc[c])
                if(V[c] < min)
                {
                    min = V[c];
                    C[i] = c;
                }
        }

    /* I don't like this very much. Better let c start at random position */
    if(min == 0 || min > n) goto m4;
m3:
    c = C[i];
    I[i]++;
    if(I[i] > Rows[c]) goto m4;
    r = Row[c][I[i]];
    if(Ur[r]) goto m3;
    m0 = 0;

    if(p)
    {
        k = N4;
        j = N2;
        x = (r - 1) / k + 1;
        y = ((r - 1) % k) / j + 1;
        s = (r - 1) % j + 1;
        A[x][y] = s;
        if(i == N4)
        {
            for(x = 1; x <= N2; x++)
                for(y = 1; y <= N2; y++) printf("%c", L[A[x][y]]);
            printf("\n");
            if(p == 1) goto m6;
        }
    }

    for(j = 1; j <= Cols[r]; j++)
    {
        c1 = Col[r][j];
        Uc[c1]++;
    }

    for(j = 1; j <= Cols[r]; j++)
    {
        c1 = Col[r][j];
        for(k = 1; k <= Rows[c1]; k++)
        {
            r1 = Row[c1][k];
            Ur[r1]++;
            if(Ur[r1] == 1)
            {
                for(l = 1; l <= Cols[r1]; l++)
                {
                    c2 = Col[r1][l];
                    V[c2]--;
                    if(Uc[c2] + V[c2] < 1) m0 = c2;
                    if(Uc[c2] == 0 && V[c2] < 2)
                    {
                        m1++;
                        M1[m1] = c2;
                    }
                }
            }
        }
    }

    nodes++;
    Node[i]++;
    goto m2;
m4:
    i--;
    c = C[i];
    r = Row[c][I[i]];
    if(i == clues)
    {
        if(p == 0) printf("%i\n", Node[N4]);
        goto m6;
    }

    for(j = 1; j <= Cols[r]; j++)
    {
        c1 = Col[r][j];
        Uc[c1]--;
        for(k = 1; k <= Rows[c1]; k++)
        {
            r1 = Row[c1][k];
            Ur[r1]--;
            if(Ur[r1] == 0)
                for(l = 1; l <= Cols[r1]; l++)
                {
                    c2 = Col[r1][l];
                    V[c2]++;
                }
        }
    }

    goto m3;
}
Back to top
View user's profile Send private message Visit poster's website AIM Address Yahoo Messenger
Display posts from previous:   
Post new topic   Reply to topic    Sudoku Programmers Forum Index -> Software All times are GMT
Goto page 1, 2  Next
Page 1 of 2

 
Jump to:  
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
Sudoku Programmers topic RSS feed 


Powered by phpBB © 2001, 2005 phpBB Group

Igloo Theme Version 1.0 :: Created By: Andrew Charron