Mndiff-dev

Download

mndiff-dev@mplayerhq.hu

November 2010

1 participants
1 discussions

[mndiff]: r214 - in trunk/sudokoso: . H1 H2 H3 H4 H5 h1 h2 sudokoso.c test0.sud test1.sud test2.sud test3.sud test5.sud
by michael 30 Nov '10

30 Nov '10

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(a)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

1 0