[MN-dev] [mndiff]: r214 - in trunk/sudokoso: . H1 H2 H3 H4 H5 h1 h2 sudokoso.c test0.sud test1.sud test2.sud test3.sud test5.sud
michael
subversion at mplayerhq.hu
Wed Dec 1 00:31:06 CET 2010
Author: michael
Date: Wed Dec 1 00:31:05 2010
New Revision: 214
Log:
Yet another sudoko solver
Added:
trunk/sudokoso/
trunk/sudokoso/H1
trunk/sudokoso/H2
trunk/sudokoso/H3
trunk/sudokoso/H4
trunk/sudokoso/H5
trunk/sudokoso/h1
trunk/sudokoso/h2
trunk/sudokoso/sudokoso.c
trunk/sudokoso/test0.sud
trunk/sudokoso/test1.sud
trunk/sudokoso/test2.sud
trunk/sudokoso/test3.sud
trunk/sudokoso/test5.sud
Added: trunk/sudokoso/H1
==============================================================================
--- /dev/null 00:00:00 1970 (empty, because file is newly added)
+++ trunk/sudokoso/H1 Wed Dec 1 00:31:05 2010 (r214)
@@ -0,0 +1,11 @@
+1 . . | . . . | . . 2
+. 9 . | 4 . . | . 5 .
+. . 6 | . . . | 7 . .
+------+-------+------
+. 5 . | 9 . 3 | . . .
+. . . | . 7 . | . . .
+. . . | 8 5 . | . 4 .
+------+-------+------
+7 . . | . . . | 6 . .
+. 3 . | . . 9 | . 8 .
+. . 2 | . . . | . . 1
\ No newline at end of file
Added: trunk/sudokoso/H2
==============================================================================
--- /dev/null 00:00:00 1970 (empty, because file is newly added)
+++ trunk/sudokoso/H2 Wed Dec 1 00:31:05 2010 (r214)
@@ -0,0 +1,11 @@
+. . 1 | . . 4 | . . .
+. . . | . 6 . | 3 . 5
+. . . | 9 . . | . . .
+------+-------+------
+8 . . | . . . | 7 . 3
+. . . | . . . | . 2 8
+5 . . | . 7 . | 6 . .
+------+-------+------
+3 . . | . 8 . | . . 6
+. . 9 | 2 . . | . . .
+. 4 . | . . 1 | . . .
Added: trunk/sudokoso/H3
==============================================================================
--- /dev/null 00:00:00 1970 (empty, because file is newly added)
+++ trunk/sudokoso/H3 Wed Dec 1 00:31:05 2010 (r214)
@@ -0,0 +1,11 @@
+. . 1 | . . 4 | . . .
+. . . | . 6 . | 3 . 5
+. . . | 9 . . | . . .
+------+-------+------
+8 . . | . . . | 7 . 3
+. . . | . . . | . 2 8
+5 . . | . 7 . | 6 . .
+------+-------+------
+3 . . | . 8 . | . . 6
+. . 9 | 2 . . | . . .
+. 4 . | . . 1 | . . .
\ No newline at end of file
Added: trunk/sudokoso/H4
==============================================================================
--- /dev/null 00:00:00 1970 (empty, because file is newly added)
+++ trunk/sudokoso/H4 Wed Dec 1 00:31:05 2010 (r214)
@@ -0,0 +1,11 @@
+. . . | . . . | . 3 9
+. . . | . . 1 | . . 5
+. . 3 | . 5 . | 8 . .
+------+-------+------
+. . 8 | . 9 . | . . 6
+. 7 . | . . 2 | . . .
+1 . . | 4 . . | . . .
+------+-------+------
+. . 9 | . 8 . | . 5 .
+. 2 . | . . . | 6 . .
+4 . . | 7 . . | . . .
Added: trunk/sudokoso/H5
==============================================================================
--- /dev/null 00:00:00 1970 (empty, because file is newly added)
+++ trunk/sudokoso/H5 Wed Dec 1 00:31:05 2010 (r214)
@@ -0,0 +1,11 @@
+. 2 . | 4 . 3 | 7 . .
+. . . | . . . | . 3 2
+. . . | . . . | . . 4
+------+-------+------
+. 4 . | 2 . . | . 7 .
+8 . . | . 5 . | . . .
+. . . | . . 1 | . . .
+------+-------+------
+5 . . | . . . | 9 . .
+. 3 . | 9 . . | . . 7
+. . 1 | . . 8 | 6 . .
Added: trunk/sudokoso/h1
==============================================================================
--- /dev/null 00:00:00 1970 (empty, because file is newly added)
+++ trunk/sudokoso/h1 Wed Dec 1 00:31:05 2010 (r214)
@@ -0,0 +1,9 @@
+..1.8.6.4
+.376.....
+5........
+.....5...
+..6.1.8..
+...4.....
+........3
+.....752.
+8.2.9.7..
\ No newline at end of file
Added: trunk/sudokoso/h2
==============================================================================
--- /dev/null 00:00:00 1970 (empty, because file is newly added)
+++ trunk/sudokoso/h2 Wed Dec 1 00:31:05 2010 (r214)
@@ -0,0 +1,9 @@
+.....3.6.
+.......1.
+.975...8.
+....9.2..
+..8.7.4..
+..3.6....
+.1...289.
+.4.......
+.5.1.....
\ No newline at end of file
Added: trunk/sudokoso/sudokoso.c
==============================================================================
--- /dev/null 00:00:00 1970 (empty, because file is newly added)
+++ trunk/sudokoso/sudokoso.c Wed Dec 1 00:31:05 2010 (r214)
@@ -0,0 +1,182 @@
+//GPL Copyright Michael Niedermayer michaelni at gmx.at 2010
+
+#include <inttypes.h>
+#include <stdio.h>
+#include <string.h>
+
+#undef NDEBUG
+#include <assert.h>
+
+#define ICOUNT 81
+#define VCOUNT 9
+#define GSIZE 3
+
+typedef struct Context{
+ uint8_t bitmap[ICOUNT][VCOUNT];
+ uint8_t gcounts[27][VCOUNT];
+ uint8_t icounts[ICOUNT];
+}Context;
+
+static uint8_t i2g[ICOUNT][4];
+static uint8_t g2i[27][16];
+
+static int max_solutions=2;
+
+static int findval(uint8_t bitmap[ICOUNT][VCOUNT], int idx){
+ int val;
+ for(val=0; val<VCOUNT; val++)
+ if(bitmap[idx][val])
+ return val;
+ return -1;
+}
+
+static int findidx(uint8_t bitmap[ICOUNT][VCOUNT], int group, int val){
+ int i;
+ for(i=0; i<9; i++)
+ if(bitmap[ g2i[group][i] ][val])
+ return g2i[group][i];
+ return -1;
+}
+
+static void check(Context *s){
+ int i, j;
+ for(i=0; i<ICOUNT; i++){
+ int c=0;
+ for(j=0; j<VCOUNT; j++){
+ c+= s->bitmap[i][j];
+ }
+ if(c!= s->icounts[i]){
+ fprintf(stderr, "icount missmatch idx=%d real=%d icount=%d\n", i, c, s->icounts[i]);
+ }
+ }
+}
+
+static int rem(Context *s, int idx, int val);
+
+static int fix(Context *s, int idx, int val){
+ int i, j;
+ assert(idx>=0);
+
+ if(s->icounts[idx]>1)
+ for(i=0; i<VCOUNT; i++)
+ if(i!=val && s->bitmap[idx][i] && rem(s, idx, i)<0)
+ return -1;
+
+ for(i=0; i<3; i++){
+ if(s->gcounts[ i2g[idx][i] ][val]>1)
+ for(j=0; j<9; j++){
+ int idx2= g2i[ i2g[idx][i] ][j];
+ if(idx2 != idx && s->bitmap[idx2][val] && rem(s, idx2, val)<0)
+ return -1;
+ }
+ }
+
+ return 0;
+}
+
+static int rem(Context *s, int idx, int val){
+ int i, c[4];
+ int idxs[3];
+ assert(s->bitmap[idx][val]);
+
+ s->bitmap[idx][val]= 0;
+ c[0]= --s->icounts[idx];
+ if(c[0]==0)
+ return -1;
+ for(i=0; i<3; i++){
+ c[1+i]= --s->gcounts[ i2g[idx][i] ][val];
+ if(c[1+i]==0){
+ return -1;
+ }else if(c[1+i]==1)
+ idxs[i]= findidx(s->bitmap, i2g[idx][i], val);
+ }
+ if(c[0]==1){
+ assert(idx>=0);
+ if(fix(s, idx, findval(s->bitmap, idx)) < 0)
+ return -1;
+ }
+ for(i=0; i<3; i++)
+ if(c[1+i]==1){
+ assert(idxs[i]>=0);
+ if(fix(s, idxs[i], val) < 0)
+ return -1;
+ }
+ return 1;
+}
+
+static int checkNsplit(Context *s){
+ int i, j;
+ int bestidx=-1;
+ check(s);
+ if(max_solutions<=0)
+ return -2;
+
+ for(i=0; i<ICOUNT; i++){
+ assert(s->icounts[i]>0);
+ if(s->icounts[i]>1 && (bestidx<0 || s->icounts[i] < s->icounts[bestidx]))
+ bestidx= i;
+ }
+ if(bestidx >= 0){
+ for(i=0; i<VCOUNT; i++){
+ if(s->bitmap[bestidx][i]){
+ Context s2= *s;
+ fprintf(stderr, "split at %2d with val %d\n", bestidx, i);
+ if(fix(&s2, bestidx, i) >= 0)
+ checkNsplit(&s2);
+ }
+ }
+ }else if(max_solutions>0){
+ int chks=0;
+ printf("\n");
+ for(i=0; i<ICOUNT; i++){
+ if(s->icounts[i]>1){
+ printf("?");
+ }else{
+ for(j=0; j<VCOUNT; j++){
+ if(s->bitmap[i][j])
+ break;
+ }
+ printf("%d", j+1);
+ chks += j+1;
+ }
+ chks*=17;
+ if(i%9==8)
+ printf("\n");
+ }
+ printf("chk=%d\n", chks);
+ max_solutions--;
+ return 0;
+ }
+ return -2;
+}
+
+int main(){
+ int i,j;
+ Context s;
+
+ for(i=0; i<81; i++){
+ i2g[i][0]= i%9;
+ i2g[i][1]= i/9+9;
+ i2g[i][2]= ((i/3)%3)+3*(i/27)+18;
+ for(j=0; j<3; j++){
+ g2i[ i2g[i][j] ][ g2i[i2g[i][j]][9]++ ]= i;
+ }
+ }
+ memset(s.bitmap , 1, sizeof(s.bitmap));
+ memset(s.gcounts, 9, sizeof(s.gcounts));
+ memset(s.icounts, 9, sizeof(s.icounts));
+ for(i=0; i<ICOUNT; i++){
+ int ch= getchar();
+ if(ch==' ' || ch=='-' || ch=='+' || ch=='|' || ch=='\n'){
+ i--;
+ }else if(ch>='1' && ch<='9'){
+ fprintf(stderr, "will fix %d %d\n", i, ch-'1');
+ if(fix(&s, i, ch-'1') < 0){
+ fprintf(stderr, "No solutions\n");
+ return 0;
+ }
+ }
+ }
+ checkNsplit(&s);
+ return 2-max_solutions;
+}
Added: trunk/sudokoso/test0.sud
==============================================================================
--- /dev/null 00:00:00 1970 (empty, because file is newly added)
+++ trunk/sudokoso/test0.sud Wed Dec 1 00:31:05 2010 (r214)
@@ -0,0 +1,9 @@
+12345678.
+45698712.
+78.......
+2........
+3........
+5........
+6........
+9........
+.........
Added: trunk/sudokoso/test1.sud
==============================================================================
--- /dev/null 00:00:00 1970 (empty, because file is newly added)
+++ trunk/sudokoso/test1.sud Wed Dec 1 00:31:05 2010 (r214)
@@ -0,0 +1,9 @@
+12345678.
+78912345.
+45678912.
+31264597.
+97831264.
+64597831.
+231564...
+897......
+.........
\ No newline at end of file
Added: trunk/sudokoso/test2.sud
==============================================================================
--- /dev/null 00:00:00 1970 (empty, because file is newly added)
+++ trunk/sudokoso/test2.sud Wed Dec 1 00:31:05 2010 (r214)
@@ -0,0 +1,9 @@
+9........
+6.2.7....
+.8..146..
+.......4.
+8.64.5...
+724.9..5.
+4.....897
+269...314
+.78.49.6.
\ No newline at end of file
Added: trunk/sudokoso/test3.sud
==============================================================================
--- /dev/null 00:00:00 1970 (empty, because file is newly added)
+++ trunk/sudokoso/test3.sud Wed Dec 1 00:31:05 2010 (r214)
@@ -0,0 +1,9 @@
+9........
+..2.7....
+....146..
+.......4.
+8.6..5...
+724.9..5.
+.......97
+.6....314
+..8.49...
\ No newline at end of file
Added: trunk/sudokoso/test5.sud
==============================================================================
--- /dev/null 00:00:00 1970 (empty, because file is newly added)
+++ trunk/sudokoso/test5.sud Wed Dec 1 00:31:05 2010 (r214)
@@ -0,0 +1,9 @@
+5....7...
+...6....2
+.2......4
+.481..2..
+9....2..5
+7......4.
+.3..8....
+.....5.71
+....2.9..
\ No newline at end of file
More information about the Mndiff-dev
mailing list