#include //gcc -Wall sudoku.linux.c -g -lncurses -O2 int nbbit[512], // nbbit[128+16+2]=3 nbbit[64+8]=2 perm[81]; // perm[27*i+9*j+3*k+l]=27*j+9*l+3*i+k i,j,k,l in {0,1,2} int reduce9(int t[9]) { int tt[512], i,j,ii; // tt[128+16+2] = tt[128]|tt[16]|tt[2] = t[7]|t[4]|t[1] ii=1<=nbsolmax) return; // many enough solutions found for(i=81;i--;) u[i]=t[i]; if(!reduce81(u)) return; // dead end this t gives no solution for(i=10;i--;) p[i]=-1; for(i=81;i--;) p[nbbit[u[i]]]=i; if(p[0]>=0) return; // dead end u[p[0]]=0 nothing fits in cell number p[0] for(i=2;i<10 && p[i]<0;i++) ; if(i>9) { ++*nbsol; opxe2(u,lastsol); // for all i nbbit[u[i]]=1 u is a solution if(drawing) printf("%d\n",*nbsol), draw(lastsol); return; } i=p[i]; // e.g. p[3]=33, u[33]=16+64+128. We try u[33]=16 and then u[33]=64 and then u[33]=128 for(j=u[i];j;j&=j-1) u[i]=j&-j, cherchesol(u,nbsol,nbsolmax,drawing); } int countsol(int t[81],int nbsolmax) { int nbsol=0, u[81]; expo2(t,u); cherchesol(u,&nbsol,nbsolmax,0); return nbsol; } void pos(int x,int y){move(y+y/3,x*3+x/3);} int main() { int t[81],u[81],d[81],i,j,k,l,x=0,y=0,nbsol,c,p=0; for(nbbit[i=0]=0;i<512;i++) nbbit[i]=(i&1)+nbbit[i/2]; for(i=3;i--;) for(j=3;j--;) for(k=3;k--;) for(l=3;l--;) perm[27*i+9*j+3*k+l]=27*j+9*l+3*i+k; for(i=81;i--;) t[i]=0; initscr(); /* Start curses mode */ raw(); /* Line buffering disabled */ keypad(stdscr, TRUE); /* We get F1, F2 etc.. */ noecho(); /* Don't echo() while we do getch */ //if(ch != KEY_F(1)) printw("The pressed key is "), attron(A_BOLD), printw("%c", ch), attroff(A_BOLD); for(c='c';c!=3;pos(x,y),c=getch()) { if(c>='A' && c<='Z') c+=32; // 'Y' -> 'y' l=c>'0' && c<='9', i=y*9+x; if(l) addch(c|A_BOLD), t[i]=c-'0'; switch(c) { case KEY_DOWN : if(++y>=9) y=8; break; case KEY_UP : if(--y<0 ) y=0; break; case KEY_RIGHT: if(++x>=9) x=8; break; case KEY_LEFT : if(--x<0 ) x=0; break; case ' ': case '0': addch(' '), t[i]=0; l=1; break; case 'p': if(++p>3) p=3; l=1; break; case 'm': if(--p<0) p=0; l=1; break; case '+': case '-': j=t[i], t[i]=0, l=1; nbsol=countsol(t,2); t[i]=nbsol>1?j:nbsol?lastsol[i]:0; if(nbsol>1) do t[i]=(t[i]+'+'-c+9)%9+1, nbsol=countsol(t,2); while(!nbsol); if(nbsol) addch('0'+t[i]+A_BOLD); default: break; case 'r': for(;i--;t[i]=j) if(j=t[i],j) if(t[i]=0,countsol(t,2)<2) break; if(i<0) i=80; else l=1; x=i%9,y=i/9; } if(!l) continue; expo2(t,u), nbsol=p&&reduce81(u); if(nbsol && p>1 && (nbsol=countsol(t,2))) expo2(lastsol,d); if(0 && p==2 && nbsol==2) for(i=81;i--;u[i]|=d[i]) if(u[i]-=d[i]) if(nbbit[d[i]]==1) { if(j=0,cherchesol(u,&j,1,0),j) for(j=81;j--;) d[j]|=1<<(lastsol[j]-1); else u[i]=d[i],reduce81(u); } if(p==2 && nbsol==2) for(i=81;i--;) for(j=81;nbbit[u[i]]>1 && nbbit[d[i]]==1;j=(i+j)/2) { for(k=i;k1 && nbbit[d[k]]==1) u[k]-=d[k]; if(j==i) u[i]=d[i], reduce81(u); else if(k=0,cherchesol(u,&k,1,0),k) for(k=81;k--;) d[k]|=1<<(lastsol[k]-1); for(k=i;k1?d:u,u); pos(9,0), addch(p+'0'), addch(' '), printw("**\n"+2-nbsol); for(i=81;i--;) if(!t[i]) pos(i%9,i/9), j=u[i]?u[i]+'0':' ', addch(j); } refresh(); /* Print it on to the real screen */ getch(); /* Wait for user input */ endwin(); /* End curses mode */ return 0; } /* Ce programme résout les problèmes de sudoku et permet aussi d'en fabriquer. Il affiche une grille de sudoku, dans laquelle les cases peuvent être vides on contenir un chiffre qui peut être en gras. Les chiffres en gras sont les chiffres imposés, ils constituent le problème à résoudre. Les autres cases peuvent être vides ou contenir des nombres, selon le mode d'affichage choisi. mode 0 : Seuls les chiffres en gras sont affichés, les autres cases sont toutes vides. mode 1: Les cases dont le contenu se déduit facilement des autres cases sont remplies. mode 2: Toutes les cases dont le contenu se déduit des autres cases sont remplies. Ce mode est très lent, car il nécessite beaucoup de calcul. mode 3: S'il existe au moins une solution, elle est affichée. Le numéro du mode d'affichage est écrit à droite du jeu, suivi de zéro, une ou deux étoiles. Il y a deux étoiles si on est en mode 2 ou 3 et que le problème a plusieurs solutions. Il n'y a pas d'étoile si on est en mode 0, ou qu'il n'y a pas de solution. (En mode 1, l'abscence d'étoile signifie que des calculs simples prouvent qu'il n'y a pas de solution, mais s'il y a une étoile, il n'y a pas nécessairement de solution) On peut taper les commandes suivantes : 1, 2, ... 9 : ce chiffre est mis en gras dans la case où est le curseur. 0 ou espace : la case du curseur n'est plus en gras touche de déplacement du curseur : le curseur se déplace p : le mode d'affichage augmente de 1 m : le mode d'affichage diminue de 1 + : la valeur sous le curseur augmente jusqu'à la plus petite valeur permettant d'obtenir une solution - : la valeur sous le curseur diminue jusqu'à la plus grande valeur permettant d'obtenir une solution r : si le problème courant a exactement une solution, on supprime un nombre en gras, sans changer la solution du problème (quand c'est possible). ^C : fin Pour fabriquer des problèmes on peut se déplacer au hasard dans la grille et taper des + et des - dans les cases vides, jusqu'à ce qu'il n'y ait plus qu'une solution. On peut alors taper des r pour éliminer toutes les cases inutiles et rendre le problème plus difficile. Un problème est simple si sa solution s'affiche en mode 1. Il est difficile s'il faut passer en mode 2 ou 3 pour voir la solution. Il y a deux façons de représenter les données dans le programme : 1) un problème est un tableau de 81 entiers. Une case contient un nombre de 1 à 9 si cette valeur est imposée. Elle contient 0, sinon. 2) Pour résoudre les problèmes on utilise une autre représentation : pour chaque case on a 9 bits correspondant à chacun des 9 chiffres. Chaque bit vaut 1 ou 0 selon que ce chiffre peut se mettre dans cette case ou non. Les 9 bits sont regroupés dans un seul entier. Par exemple u[23]=16+4+1 si la case 23 peut contenir 5, 3 ou 1. expo2() et opxe2() sont les deux procédures qui permettent de passer d'une représentation à l'autre. Dans la procédure reduce9() le tableau int t[9] représente les chiffres que l'on peut mettre dans les neuf cases d'une même ligne, d'une même colonne ou d'un même bloc 3x3, c'est-à-dire neuf cases dans lesquelles on doit répartir les chiffres de 1 à 9. Pour chacun des 512 sous-ensembles i de ces neuf cases, on calcule l'ensemble tt[i] des chiffres qui peuvent se mettre dans au moins une des cases de i. Si tt[i] a moins d'éléments que i, on en déduit qu'il n'y a pas de solution. Si tt[i] a autant d'éléments que i, alors on en déduit que l'ensemble complémentaire de i (511-i) contiendra le complémentaire de tt[i] (511-tt[i]). Ainsi on réduit les possibilités pour certaines cases. La procédure reduce81() applique la procédure reduce9() à chacune des lignes, chacune des colonnes et chacun des blocs 3x3, et recommence jusqu'à ce que, ou bien on arrive à la conclusion qu'il y a pas de solution (reduce9() rend 0 et donc reduce81() aussi) ou bien les possiblités des cases ne diminuent plus. La procédure cherchesol(t,...) cherche toutes les solutions compatibles avec le tableau t, qui est d'abord copié dans u, puis réduit par reduce81(). Puis s'il existe une case dans laquelle on peut mettre plusieurs chiffres, on essaye successivement chacun de ces chiffres. Pour chaque essai, on recherche toutes les possibilités par un appel récursif à cherchesol(). En fait on s'arrête dès que le nombre de solutions trouvées atteint nbsolmax. This program solves sudoku problems and allow you to build your own problems. It diplayes a sudoku grid, in which cells may be empty or hold a digit which may be in bold face. Bold digits are forced digits, they build up the problem to solve. Other cells may be empty or hold digits, according to the chosen display mode. mode 0 : Only bold digits are displayed, all other cells are empty. mode 1: Cells whose contains may easily be inferred from other cells are filled. mode 2: All cells whose contains may be inferred from other cells are filled. This mode is very slow, since it needs a lot of computation. mode 3: If at least one solution exists, it is displayed. Display mode number is written on the right of the game, followed by zero, one or two stars. There are two stars when in mode 2 or 3 and problem has several solutions. There is no star when in mode 0 or when there is no solution. (In mode 1, lack of star means that a simple computation proves that there is no solution, but if there is a star, there is not necessarily a solution. The following commands may be typed : 1, 2, ... 9 : this digit is put in bold face in the cell where the cursor is. 0 or space : the cell where the cursor is, is no longer in bold face. cursor deplacement keys : the cursor moves. p : display mode increases by 1. m : display mode decreases by 1. + : the value under the cursor increases to the smallest value allowing a solution. - : the value under the cursor decreases to the largest value allowing a solution. r : if the current problem has exactly one solution, a bold digit is removed, with no alteration of problem solution (when possible). ^C : quit To build problems, you may move randomly in the grid and type + and - in empty cells, until there is only one solution left. Then you may type r to get rid of useless cells and make the problem harder to solve. A problem is easy when its solution displays in mode 1. It is hard if you need to be in mode 2 or 3 to see the solution. Data are stored in two different ways in this program. 1) a problem is an array of 81 integers. A cell holds a number between 1 and 9 if this value is forced. Otherwise it holds 0. 2) To solve problems another storage mode is used : for every cell there are 9 bits related to each of the 9 digits. Every bit is assigned to 1 or 0 depending on the ability to this digit to be put in this cell. These 9 bits are gathered into one single integer. E. g. u[23]=16+4+1 if cell 23 may hold 5, 3 or 1. expo2() and opxe2() are the two procedures allowing to change storage mode. In procedure reduce9() array int t[9] stands for the digits you can put into the nine cells of a same line or a same row or a same block 3x3, i. e. nine cells in which you must deal digits from 1 to 9. For every set i among the 512 subsets of this set of nine cells, the set tt[i] of the digits which can be put in at least one of the cells of i, is computed. If tt[i] has fewer elements than i, you can infer that there is no solution. If tt[i] has as many element as i, then you may infer that the coset of i (511-i) must hold the coset of tt[i] (511-tt[i]). Hence abilities of some cells are reduced. Procedure reduce81() applies reduce9() to every line, every row and every block 3x3 and starts again and again until either it concludes there is no solution (reduce9() returns 0 et so does reduces81() ) or no ability of any cell decreases any more. Procedure cherchesol(t,...) looks for all solutions fitting array t, which is first copied in u, and then reduced by reduce81(). Then if there is a cell in which several digits fit, every one of them is tried on turn. For every attempt, all the solutions are looked for by calling recursively cherchesol(). Actually computation stops as soon as the number of found solutions reaches nbsolmax. */