www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - Programming Puzzle 8-8-08

reply Wyverex <wyverex.cypher gmail.com> writes:
Another day, another puzzle!!  I'll try keeping this up as long as I can!



Write a program that can solve Sudoku!

http://en.wikipedia.org/wiki/Sudoku

the input...

char[][] boards =
["000075400000000008080190000300001060000000034000068170204000603900000020530200000",
"300000000050703008000028070700000043000000000003904105400300800100040000968000200",
"302609005500730000000000900000940000000000109000057060008500006000000003019082040",
"530000008007000030200006901000500200090370004000981000300040560000090000000007080",
"008310900095000160000000005000400000000080049006072000000001030000240607001008200",
"000400970000051600042000010030000000070508064000070000700030000300090000005864009",
"060500000720000000000000320000050637000004500000230180180009000603070000004006003",
"274000030000000005000600041900306000100280000006054000000000002007000583000095700",
"570000069000003800090000000801600000000030600702000050000060501000702000006091032",
"005200000400300700600000010800020100040800500000095000083040070090006080500902000",
"400500600200000000000020000002004380000030000790000504000060490070093810500100030",
"000790000001000000040050080000800027009003000000020403000040600004907100600501790",
"060010000403700008520640000002000000009438005000006300004301200000200000005070000",
"130400000705300000600020000000000027000900400000000085860500003059103000002004060",
"020001048400000037071006020500000000000010802000809500090030400000040000000902060",
"000000020006410035180020000008130406020000300600000000790005000004000008001300002",
"040000200000007090000006010870020004901000028060030100006800041000070050005900000",
"000030009048900000200470100125000080000080710000500000000090054061000003000050070",
"000000060306000000000000805000605071005000300100870042900200014201080000000703000",
"900000586008070004401000300002010900804005100000007000003008702000000000600040009",
"000032970070045010000800000001060000000000000029000840500620007004000009100009036",
"950003008800002000031000000060350090010007050000060010008000307000206009007000004",
"000000000300027801100083000005001000001370060007004002200060070004000000900030650",
"030207001000180670001030050000500900190004008000600020300700000000005080000020006",
"600000004020507000000000031010900060000350109800000002240108000067090000003000006",
"600095000000061802000000100500016000004000200002008036000002450040050000003400070",
"201070800460000090080010040000050030030980051000006000004097000500000000090020700",
"090000030100000800000312700050640007000730240080500000026000010000004300000050060",
"000560300100000800024000000009000000080720006610800000007206000400080037000104090",
"090035406001000000007000089070940050100200000006800700008004030000600040605000000",
"050060040006247091000190000000600900200000084000300005031000008000000006004000250"];

output...

000075400     693875412
000000008     145632798
080190000     782194356
300001060     357421869
000000034  =  816957234
000068170     429368175
204000603     274519683
900000020     968743521
530200000     531286947

300000000     387419526
050703008     259763418
000028070     641528379
700000043     716285943
000000000  =  594631782
003904105     823974165
400300800     472396851
100040000     135842697
968000200     968157234

302609005     382619475
500730000     594738621
000000900     176425938
000940000     863941752
000000.......
Aug 08 2008
next sibling parent Wyverex <wyverex.cypher gmail.com> writes:
//Heres a backtracking solution


import tango.io.Stdout;

char[][] boards =
["000075400000000008080190000300001060000000034000068170204000603900000020530200000",
"300000000050703008000028070700000043000000000003904105400300800100040000968000200",
"302609005500730000000000900000940000000000109000057060008500006000000003019082040",
"530000008007000030200006901000500200090370004000981000300040560000090000000007080",
"008310900095000160000000005000400000000080049006072000000001030000240607001008200",
"000400970000051600042000010030000000070508064000070000700030000300090000005864009",
"060500000720000000000000320000050637000004500000230180180009000603070000004006003",
"274000030000000005000600041900306000100280000006054000000000002007000583000095700",
"570000069000003800090000000801600000000030600702000050000060501000702000006091032",
"005200000400300700600000010800020100040800500000095000083040070090006080500902000",
"400500600200000000000020000002004380000030000790000504000060490070093810500100030",
"000790000001000000040050080000800027009003000000020403000040600004907100600501790",
"060010000403700008520640000002000000009438005000006300004301200000200000005070000",
"130400000705300000600020000000000027000900400000000085860500003059103000002004060",
"020001048400000037071006020500000000000010802000809500090030400000040000000902060",
"000000020006410035180020000008130406020000300600000000790005000004000008001300002",
"040000200000007090000006010870020004901000028060030100006800041000070050005900000",
"000030009048900000200470100125000080000080710000500000000090054061000003000050070",
"000000060306000000000000805000605071005000300100870042900200014201080000000703000",
"900000586008070004401000300002010900804005100000007000003008702000000000600040009",
"000032970070045010000800000001060000000000000029000840500620007004000009100009036",
"950003008800002000031000000060350090010007050000060010008000307000206009007000004",
"000000000300027801100083000005001000001370060007004002200060070004000000900030650",
"030207001000180670001030050000500900190004008000600020300700000000005080000020006",
"600000004020507000000000031010900060000350109800000002240108000067090000003000006",
"600095000000061802000000100500016000004000200002008036000002450040050000003400070",
"201070800460000090080010040000050030030980051000006000004097000500000000090020700",
"090000030100000800000312700050640007000730240080500000026000010000004300000050060",
"000560300100000800024000000009000000080720006610800000007206000400080037000104090",
"090035406001000000007000089070940050100200000006800700008004030000600040605000000",
"050060040006247091000190000000600900200000084000300005031000008000000006004000250"];


void main()
{
   foreach(org; boards)
   {
     auto sol = solve( org.dup, 0 );

     for(int x = 0; x <81; x+=9)
       Stdout.formatln("{}  {}  {}", org[x..x+9], (x == 4*9 ? "=": " "), 
sol[x..x+9]);
     Stdout.newline;
   }
}

char[] solve( char[] board, int index )
{
   if( index >= 81 )
     return board;

   if( board[index] != '0' )
     return solve( board, index + 1 );

   for( int i = 1; i < 10; i++ )
   {
     board[index] = i + '0';

     if( !test( board, index ) ) continue;

     auto ans = solve( board, index + 1 );
     if( ans !is null )
       return ans;
   }

   board[index] = '0';
   return null;
}


bool test( char[] board, int index )
{
   //tests if the new number is legal
   int x = index % 9;
   int y = index / 9;

   //test what row the number is in
   {
     int[10] find;
     for(int i = y*9; i < y*9+9; i++)
     {
       int n = board[i] - '0';
       if(n == 0) continue;
       if(find[n] == 1) return false;
       find[n] = 1;
     }
   }

   //test the column
   {
     int[10] find;
     for( int i = 0; i < 9; i++ )
     {
       int n = board[i*9 + x] - '0';
       if(n == 0) continue;
       if(find[n] == 1) return false;
       find[n] = 1;
     }
   }

   //now to test the local block
   {
     int bx = x / 3;
     int by = y / 3;
     int[10] find;
     for( int yy = by * 3; yy < (by * 3) + 3; ++yy )
     {
       for( int xx = bx*3; xx < (bx * 3) + 3; ++xx )
       {
         int i = yy*9+xx;
         int n = board[i] - '0';
         if(n == 0) continue;
         if(find[n] == 1) return false;
         find[n] = 1;
       }
     }
   }

   return true;
}
Aug 08 2008
prev sibling next sibling parent "Steven Schveighoffer" <schveiguy yahoo.com> writes:
Depth-first brute force with the standard sudoku constraints

Code:

import tango.io.Stdout;

char[][] boards = [...];


bool solve(int[][] brd, int idx)
{
    if(idx == 9 * 9)
        return true;
    int x = idx % 9;
    int y = idx / 9;
    if(brd[x][y])
        return solve(brd, idx + 1);
    bool[10] bad;
    for(int i = 0; i < 9; i++)
    {
        bad[brd[x][i]] = true;
        bad[brd[i][y]] = true;
    }

    int boxx = (x / 3) * 3;
    int boxy = (y / 3) * 3;
    for(int i = 0; i < 3; i++)
        for(int j = 0; j < 3; j++)
            bad[brd[boxx + i][boxy + j]] = true;
    for(int i = 1; i < 10; i++)
        if(!bad[i])
        {
            brd[x][y] = i;
            if(solve(brd, idx + 1))
                return true;
        }
    brd[x][y] = 0;
    return false;
}

void printboard(int[][] brd)
{
    for(int i = 0; i < 9; i++)
    {
        if(i % 3 == 0)
            Stdout.newline;
        for(int j = 0; j < 9; j++)
        {
            if(j % 3 == 0)
                Stdout(" ");
            Stdout(brd[i][j]);
        }
        Stdout.newline;
    }
}

void main()
{
    for(int i = 0; i < boards.length; i++)
    {
        int[][] brd = new int[][](9,9);
        for(int j = 0; j < 9; j++)
            for(int k = 0; k < 9; k++)
                brd[j][k] = boards[i][j * 9 + k] - '0';
        Stdout("=======================").newline;
        printboard(brd);
        solve(brd, 0);
        Stdout.newline;
        printboard(brd);
    }
}

Output is attached (for comparison)

run time:

real    0m1.797s
user    0m1.794s
sys     0m0.003s

-Steve



begin 666 sudoku.txt
M/3T]/3T]/3T]/3T]/3T]/3T]/3T]/3T-" T*(# P," P-S4 -# P#0H ,# P
M(# P," P,# -"B P.#  ,3DP(# P, T*#0H ,S P(# P,2 P-C -"B P,#  
M,# P(# S- T*(# P," P-C  ,3<P#0H-"B R,#0 ,# P(#8P,PT*(#DP," P
M,#  ,#(P#0H -3,P(#(P," P,# -" T*#0H -CDS(# W-2 T,3(-"B Q-#4 
M-C,R(#<Y. T*(#<X,B Q.30 ,S4V#0H-"B S-3< -#(Q(# V.0T*(# Q-B Y
M-3< ,C,T#0H -#(Y(#,V." Q-S4-" T*(#(W-" U,3D -C S#0H .38X(#<T
M,R U,C$-"B U,S$ ,C V(#DT-PT*/3T]/3T]/3T]/3T]/3T]/3T]/3T]/3T-
M" T*(#,P," P,#  ,# P#0H ,#4P(#<P,R P,# -"B P,#  ,#(X(# W, T*
M#0H -S P(# P," P-#,-"B P,#  ,# P(# P, T*(# P,R Y,#0 ,3 U#0H-
M"B T,#  ,S P(# P, T*(#$P," P-#  ,# P#0H .38X(# P," R,# -" T*
M#0H ,S W(#0Q.2 U,C8-"B R-3D -S8S(#0Q. T*(#8T,2 U,C  ,S<Y#0H-
M"B W,38 ,C U(#DT,PT*(#4Y-" V,S$ -S R#0H .#(S(#DW-" Q-C4-" T*
M(#0W,B S.38 .#4Q#0H ,3,U(# T,B V.3<-"B Y-C  ,34W(#(S- T*/3T]
M/3T]/3T]/3T]/3T]/3T]/3T]/3T-" T*(#,P,B V,#D ,# U#0H -3 P(#<S
M," P,# -"B P,#  ,# P(#DP, T*#0H ,# P(#DT," P,# -"B P,#  ,# P
M(#$P.0T*(# P," P-3< ,#8P#0H-"B P,#  -3 P(# P- T*(# P," P,#  
M,# S#0H ,#$Y(# X,B P-# -" T*#0H ,S R(#8Q.2 T-S4-"B U.30 -S,X
M(#8R,0T*(#$W-B T,C4 .3,X#0H-"B X-C, .30Q(#<U, T*(#0U-R R-C, 
M,3 Y#0H .3(Q(# U-R S-C0-" T*(#<S." U.30 ,C$V#0H ,C0U(#$W-B X
M.3,-"B V,3D ,S R(#4T-PT*/3T]/3T]/3T]/3T]/3T]/3T]/3T]/3T-" T*
M(#4S," P,#  ,# X#0H ,# W(# P," P,S -"B R,#  ,# V(#DP,0T*#0H 
M,# P(#4P," R,# -"B P.3  ,S<P(# P- T*(# P," Y.#$ ,# P#0H-"B S
M,#  ,#0P(#4V, T*(# P," P.3  ,# P#0H ,# P(# P-R P.# -" T*#0H 
M-3,V(#0Q.2 W,C -"B Y,3< .#(U(#0S- T*(#(T." W,S8 .34Q#0H-"B W
M.#$ -38T(#(Y,PT*(#8Y-2 S-S( .#$T#0H -#(S(#DX,2 V-S4-" T*(#,W
M.2 Q-#  -38R#0H .#4R(#8Y,R Q-#<-"B Q-C0 ,C4W(#,X.0T*/3T]/3T]
M/3T]/3T]/3T]/3T]/3T]/3T-" T*(# P." S,3  .3 P#0H ,#DU(# P," Q
M-C -"B P,#  ,# P(# P-0T*#0H ,# P(#0P," P,# -"B P,#  ,# P(# T
M.0T*(# P-B P-S( ,# P#0H-"B P,#  ,# Q(# S, T*(# P," R-#  -C W
M#0H ,# Q(# P." R,# -" T*#0H -#8X(#,Q-2 Y-S(-"B W.34 .#(T(#$V
M,PT*(#$S,B V.3< -# U#0H-"B X,3D -#4S(#<R- T*(#(U-R Q.#8 ,S0Y
M#0H ,S0V(#DW,B X-3$-" T*(#DR-" W-C$ -3,X#0H -3 S(#(T.2 V,3<-
M"B V-S$ -3,X(#(Y- T*/3T]/3T]/3T]/3T]/3T]/3T]/3T]/3T-" T*(# P
M," T,#  .3<P#0H ,# P(# U,2 V,# -"B P-#( ,# P(# Q, T*#0H ,#,P
M(# P," P,# -"B P-S  -3 X(# V- T*(# P," P-S  ,# P#0H-"B W,#  
M,#,P(# P, T*(#,P," P.3  ,# P#0H ,# U(# V-" P,#D-" T*#0H -3$S
M(#0R-B Y-S -"B Y.#< ,S4Q(#8T, T*(#8T,B Y.#< -3$S#0H-"B X,S$ 
M-C0Y(#(U-PT*(#(W.2 U,3  ,S8T#0H -#4V(#(W,R X.3$-" T*(#<Y." Q
M,S4 -#(V#0H ,S8T(#<Y,B Q.#4-"B Q,C4 .#8T(#<S.0T*/3T]/3T]/3T]
M/3T]/3T]/3T]/3T]/3T-" T*(# V," U,#  ,# P#0H -S(P(# P," P,# -
M"B P,#  ,# P(#,R, T*#0H ,# P(# U," V,S<-"B P,#  ,# T(#4P, T*
M(# P," R,S  ,3 P#0H-"B Q.#  ,# Y(# P, T*(#8P,R P-S  ,# P#0H 
M,# T(# P-B P,#,-" T*#0H ,S8Y(#4T,B X-S$-"B W,C$ .#DS(#0V-0T*
M(#4T." W-C$ ,S(Y#0H-"B T,3( .34X(#8S-PT*(# S-R V,30 -3DR#0H 
M.34V(#(S-R Q.#0-" T*(#$X-2 S,CD -S0V#0H -CDS(#0W-2 R,3 -"B R
M-S0 ,3 V(#DU,PT*/3T]/3T]/3T]/3T]/3T]/3T]/3T]/3T-" T*(#(W-" P
M,#  ,#,P#0H ,# P(# P," P,#4-"B P,#  -C P(# T,0T*#0H .3 P(#,P
M-B P,# -"B Q,#  ,C P(# P, T*(# P-B P-30 ,# P#0H-"B P,#  ,# P
M(# P, T*(# P-R P,#  -3 S#0H ,# P(# Y-2 W,# -" T*#0H ,C<T(#4Q
M." V,SD-"B S-C$ .30R(# W-0T*(# U.2 V,S< ,C0Q#0H-"B Y.#( ,S<V
M(#$U- T*(#$T-2 R.#D ,S8W#0H -S,V(#$U-" Y,C -" T*(#4Q." W-C, 
M-#DR#0H -CDW(#0R,2 U.#,-"B T,C, .#DU(#<Q- T*/3T]/3T]/3T]/3T]
M/3T]/3T]/3T]/3T-" T*(#4W," P,#  ,#8Y#0H ,# P(# P,R X,# -"B P
M.3  ,# P(# P, T*#0H .# Q(#8P," P,# -"B P,#  ,#,P(#8P, T*(#<P
M,B P,#  ,#4P#0H-"B P,#  ,#8P(#4P,0T*(# P," W,#( ,# P#0H ,# V
M(# Y,2 P,S(-" T*#0H -3<S(#0R." Q-CD-"B V,C0 .3$S(# W-0T*(#$Y
M." U-S8 ,C0S#0H-"B X,S$ -C0U(#DR-PT*(#DT-2 R,S< -C$X#0H -S8R
M(#$X.2 S-30-" T*(#(X-R S-C0 -3DQ#0H ,S$Y(#<U,B T.#8-"B T-38 
M.#DQ(#<S, T*/3T]/3T]/3T]/3T]/3T]/3T]/3T]/3T-" T*(# P-2 R,#  
M,# P#0H -# P(#,P," W,# -"B V,#  ,# P(# Q, T*#0H .# P(# R," Q
M,# -"B P-#  .# P(#4P, T*(# P," P.34 ,# P#0H-"B P.#, ,#0P(# W
M, T*(# Y," P,#8 ,# P#0H -3 P(#DP,B P,# -" T*#0H -S,U(#(Q." Y
M-C0-"B T,3  ,S8Y(#<U, T*(#8R.2 T-3< ,S$X#0H-"B X-3< -C(T(#$Y
M,PT*(#DT,2 X-S, -3(V#0H ,S8R(#$Y-2 X-#<-" T*(#(X,R U-#$ -C<Y
M#0H ,3DT(#<S-B R.#4-"B U-S8 .3 R(#0S,0T*/3T]/3T]/3T]/3T]/3T]
M/3T]/3T]/3T-" T*(#0P," U,#  -C P#0H ,C P(# P," P,# -"B P,#  
M,#(P(# P, T*#0H ,# R(# P-" S.# -"B P,#  ,#,P(# P, T*(#<Y," P
M,#  -3 T#0H-"B P,#  ,#8P(#0Y, T*(# W," P.3, .#$P#0H -3 P(#$P
M," P,S -" T*#0H -#,X(#4Q.2 V-S(-"B R,38 -#<X(#DU,PT*(#DU-R S
M,C8 ,30X#0H-"B Q-C( -S4T(#,X.0T*(# T-2 Y,S( -S8Q#0H -SDS(#8X
M,2 U,C0-" T*(#,R,2 X-C4 -#DW#0H -C<T(#(Y,R X,34-"B U.#D ,30W
M(#(S- T*/3T]/3T]/3T]/3T]/3T]/3T]/3T]/3T-" T*(# P," W.3  ,# P
M#0H ,# Q(# P," P,# -"B P-#  ,#4P(# X, T*#0H ,# P(# P," P,C<-
M"B P,#D ,# S(# P, T*(# P," P,C  -# S#0H-"B P,#  ,#0P(#8P, T*
M(# P-" Y,#< ,3 P#0H -C P(#4P,2 W.3 -" T*#0H ,S8U(#<Y." R-#$-
M"B Y.#$ ,C,T(#4W- T*(#<T,B Q-38 ,S Y#0H-"B T,S8 .#$U(#DR-PT*
M(#(Q.2 T-S, .#8U#0H -3<X(#8R.2 T,3,-" T*(#$Y-R S-#( -C4X#0H 
M.#4T(#DV-R Q,S(-"B V,C, -3 Q(#<Y- T*/3T]/3T]/3T]/3T]/3T]/3T]
M/3T]/3T-" T*(# V," P,3  ,# P#0H -# S(#<P," P,# -"B U,C  -C0P
M(# P, T*#0H ,# R(# P," P,# -"B P,#D -#,X(# P-0T*(# P," P,#8 
M,S P#0H-"B P,#0 ,S Q(#(P, T*(# P," R,#  ,# P#0H ,# U(# W," P
M,# -" T*#0H .38W(# Q,R U-#(-"B T,3, -S4R(#DV. T*(#4R." V-#D 
M-S,Q#0H-"B S-3( ,3DW(#8X- T*(#8W.2 T,S  ,3(U#0H .#0Q(#4R-B S
M.3<-" T*(#<X-" S-C$ ,C4Y#0H ,3DV(#(X-2 T-S,-"B R,S4 .3<T(# Q
M- T*/3T]/3T]/3T]/3T]/3T]/3T]/3T]/3T-" T*(#$S," T,#  ,# P#0H 
M-S U(#,P," P,# -"B V,#  ,#(P(# P, T*#0H ,# P(# P," P,C<-"B P
M,#  .3 P(#0P, T*(# P," P,#  ,# U#0H-"B X-C  -3 P(# P,PT*(# U
M.2 Q,#, ,# P#0H ,# R(# P-" P-C -" T*#0H ,3,X(#0W.2 V-3(-"B W
M,C4 ,S$V(# Y- T*(#8Y-" X,C4 -S,Q#0H-"B U-#$ -C,X(#DR-PT*(#(X
M,R Y-3< -#$V#0H .3<V(#(T,2 S.#4-" T*(# V-R U.3( ,30S#0H -#4Y
M(#$V,R R-S -"B S,3( -S T(#4V.0T*/3T]/3T]/3T]/3T]/3T]/3T]/3T]
M/3T-" T*(# R," P,#$ ,#0X#0H -# P(# P," P,S<-"B P-S$ ,# V(# R
M, T*#0H -3 P(# P," P,# -"B P,#  ,#$P(# P, T*(# P," X,#D -3 P
M#0H-"B P.3  ,#,P(#0P, T*(# P," P-#  ,# P#0H ,# P(#DP,B P-C -
M" T*#0H .3(U(#,W,2 V-# -"B T-C  ,CDU(#$S-PT*(#,W,2 T.#8 .3(U
M#0H-"B U.#D -S(T(#,Q- T*(#<T-B U,3, .#DR#0H ,3,R(# V.2 U-S0-
M" T*(#(Y-R V,S  -#4Q#0H -C4S(#$T-R R.#D-"B X,30 .34R(#<V,PT*
M/3T]/3T]/3T]/3T]/3T]/3T]/3T]/3T-" T*(# P," P,#  ,#(P#0H ,# V
M(#0Q," P,S4-"B Q.#  ,#(P(# P, T*#0H ,# X(#$S," T,#8-"B P,C  
M,# P(#,P, T*(#8P," P,#  ,# P#0H-"B W.3  ,# U(# P, T*(# P-" P
M,#  ,# X#0H ,# Q(#,P," P,#(-" T*#0H ,S0Y(#8U." Q,C<-"B R-S8 
M-#$Y(# S-0T*(#$X-2 W,C, .38T#0H-"B Y-3  ,3,R(#0W- T*(#0R-R Y
M.#8 ,S4Q#0H -C$S(#4W-" R.#D-" T*(#<Y,B X-#4 -C$S#0H -3,T(#(V
M,2 W.3 -"B X-C$ ,SDW(#4T, T*/3T]/3T]/3T]/3T]/3T]/3T]/3T]/3T-
M" T*(# T," P,#  ,C P#0H ,# P(# P-R P.3 -"B P,#  ,# V(# Q, T*
M#0H .#<P(# R," P,#0-"B Y,#$ ,# P(# R. T*(# V," P,S  ,3 P#0H-
M"B P,#8 .# P(# T,0T*(# P," P-S  ,#4P#0H ,# U(#DP," P,# -" T*
M#0H -C0Y(#,Q-2 R.#<-"B Q,S( -# W(#8Y-0T*(#4X-R R.38 -#$S#0H-
M"B X-S, ,3(Y(#4V- T*(#DU,2 W-C0 ,S(X#0H ,C8T(#4S." Q-SD-" T*
M(#,Y-B X-3( -S0Q#0H -#$X(#8W,R Y-3(-"B W,C4 .30Q(# S- T*/3T]
M/3T]/3T]/3T]/3T]/3T]/3T]/3T-" T*(# P," P,S  ,# Y#0H ,#0X(#DP
M," P,# -"B R,#  -#<P(#$P, T*#0H ,3(U(# P," P.# -"B P,#  ,# P
M(#<Q, T*(# P," U,#  ,# P#0H-"B P,#  ,#DP(# U- T*(# V,2 P,#  
M,# S#0H ,# P(# U," P-S -" T*#0H -S$V(# S-2 T,CD-"B S-#  .3$R
M(#4V-PT*(#(U.2 T-S8 ,3,X#0H-"B Q,C4 ,S0W(#DX- T*(#8S-" R.#D 
M-S$U#0H .3 W(#4V,2 S-#(-" T*(# W,B Q.3, -C4T#0H -38Q(#<R-" X
M.3,-"B T.3, -C4X(#(W,0T*/3T]/3T]/3T]/3T]/3T]/3T]/3T]/3T-" T*
M(# P," P,#  ,#8P#0H ,S V(# P," P,# -"B P,#  ,# P(# P-0T*#0H 
M,# P(#8P-2 P-S$-"B P,#4 ,# P(#,P, T*(#$P," X-S  ,#0R#0H-"B Y
M,#  ,C P(# Q- T*(#(P,2 P.#  ,# P#0H ,# P(#<P,R P,# -" T*#0H 
M-3 W(#,T,B Q-CD-"B S,38 -3DX(#0R-PT*(#0R.2 Q-C< .#,U#0H-"B X
M-#( -C,U(#DW,0T*(#<Y-2 T,C$ ,S V#0H ,38S(# W.2 U-#(-" T*(#DS
M." R-38 -S$T#0H ,C<Q(#DX-" V-3,-"B V-30 -S$S(#(Y. T*/3T]/3T]
M/3T]/3T]/3T]/3T]/3T]/3T-" T*(#DP," P,#  -3 V#0H ,# X(# W," P
M,#0-"B T,#$ ,# P(#,P, T*#0H ,# R(# Q," Y,# -"B X,#0 ,# U(#$P
M, T*(# P," P,#< ,# P#0H-"B P,#, ,# X(#<P, T*(# P," P,#  ,# P
M#0H -C P(# T," P,#D-" T*#0H .3(W(#0S,2 U.#8-"B S-C  -3<Y(#(Q
M- T*(#0U,2 R.#8 ,SDW#0H-"B W,S( .#$T(#DV-0T*(# Y-" V,C4 ,3<S
M#0H -3$V(#,Y-R T,C -" T*(#$T,R Y-C  -S4R#0H ,C Y(#<U,R V-#$-
M"B V-S4 ,30R(# S.0T*/3T]/3T]/3T]/3T]/3T]/3T]/3T]/3T-" T*(# P
M," P,S( .3<P#0H ,#<P(# T-2 P,3 -"B P,#  .# P(# P, T*#0H ,# Q
M(# V," P,# -"B P,#  ,# P(# P, T*(# R.2 P,#  .#0P#0H-"B U,#  
M-C(P(# P-PT*(# P-" P,#  ,# Y#0H ,3 P(# P.2 P,S8-" T*#0H .#0V
M(#$S,B Y-S4-"B S-S( .30U(#8Q. T*(#DQ-2 X-S8 ,S(T#0H-"B T-3$ 
M,S8X(#<Y, T*(#<S." R.30 -38Q#0H -C(Y(#4Q-R X-#,-" T*(#4Y,R V
M,C$ -# W#0H ,C8T(#<X,R Q-3D-"B Q.#< -#4Y(#(S- T*/3T]/3T]/3T]
M/3T]/3T]/3T]/3T]/3T-" T*(#DU," P,#, ,# X#0H .# P(# P,B P,# -
M"B P,S$ ,# P(# P, T*#0H ,#8P(#,U," P.3 -"B P,3  ,# W(# U, T*
M(# P," P-C  ,#$P#0H-"B P,#  ,# P(#,P-PT*(# P," R,#8 ,# Y#0H 
M,# W(# P," P,#0-" T*#0H .34R(#<Q,R V-# -"B X-S8 -30R(#DS,0T*
M(#0S,2 V.#D ,C<U#0H-"B W-C0 ,S4Q(# Y, T*(#,Q.2 X,C< -#4V#0H 
M,C U(#DV-" W,3,-" T*(#$R." T.34 ,S8W#0H -30S(#(W-B Q.#D-"B V
M.3< ,3,X(#4R- T*/3T]/3T]/3T]/3T]/3T]/3T]/3T]/3T-" T*(# P," P
M,#  ,# P#0H ,S P(# R-R X,#$-"B Q,#  ,# S(# P, T*#0H ,# U(# P
M,2 P,# -"B P,#$ ,S<P(# V, T*(# P-R P,#0 ,# R#0H-"B R,#  ,#8P
M(# W, T*(# P-" P,#  ,# P#0H .3 P(# S," V-3 -" T*#0H -3 Y(#$T
M-B W,C,-"B S-#8 -3(W(# Y,0T*(#$W,B Y.#, -30V#0H-"B V,S4 ,CDQ
M(#0X-PT*(#0R,2 S-S  .38U#0H .#DW(#8U-" S,3(-" T*(#(U,R T-CD 
M,3<X#0H -S8T(# Q-2 R,SD-"B Y,3  -S,R(#8U- T*/3T]/3T]/3T]/3T]
M/3T]/3T]/3T]/3T-" T*(# S," R,#< ,# Q#0H ,# P(#$X," V-S -"B P
M,#$ ,#,P(# U, T*#0H ,# P(#4P," Y,# -"B Q.3  ,# T(# P. T*(# P
M," V,#  ,#(P#0H-"B S,#  -S P(# P, T*(# P," P,#4 ,# P#0H ,# P
M(# R," P,#8-" T*#0H .3,V(#(U-R X-#$-"B R-#4 ,3 Y(#8W,PT*(#<X
M,2 T,S8 ,C4Y#0H-"B X-C0 -3$R(#DS-PT*(#$Y,B S-S0 -38X#0H -3<S
M(#8Y." Q,C0-" T*(#,R." W-C$ -#DU#0H -C$W(#DT-2 S.#(-"B T-3D 
M.#(S(#<Q- T*/3T]/3T]/3T]/3T]/3T]/3T]/3T]/3T-" T*(#8P," P,#  
M,# T#0H ,#(P(#4P-R P,# -"B P,#  ,# P(# S,0T*#0H ,#$P(#DP," P
M-C -"B P,#  ,S4P(#$P.0T*(# P," P,#  ,# R#0H-"B R-#  ,3 X(# P
M, T*(# V-R P.3  ,# P#0H ,# S(# P," P,#8-" T*#0H -C4Q(# S.2 W
M,C0-"B S,C0 -3$W(#8Y. T*(#<Y." T,C8 -3,Q#0H-"B U,3( .3 T(#,V
M-PT*(#0W-B S-3( ,3 Y#0H .#,Y(#8W,2 T-3(-" T*(#(T-2 Q-C  .3<S
M#0H ,38W(#(Y,R X-#4-"B Y.#, -S0U(#(Q- T*/3T]/3T]/3T]/3T]/3T]
M/3T]/3T]/3T-" T*(#8P," P.34 ,# P#0H ,# P(# V,2 X,#(-"B P,#  
M,# P(#$P, T*#0H -3 P(# Q-B P,# -"B P,#0 ,# P(#(P, T*(# P,B P
M,#  ,#,V#0H-"B P,#  ,# R(#0U, T*(# T," P-3  ,# P#0H ,# S(#0P
M," P-S -" T*#0H -C(Q(# Y-2 S-#<-"B T-S4 ,S8Q(# Y, T*(#,Y." W
M,C0 ,38U#0H-"B U,SD ,C$V(#<X- T*(# V-" U,S< ,C$Y#0H -S$R(#DT
M." U,S8-" T*(#DX-B Q-S( -#4S#0H ,30W(#8U,R Y,C -"B R-3, -# Y
M(#8W,0T*/3T]/3T]/3T]/3T]/3T]/3T]/3T]/3T-" T*(#(P,2 P-S  .# P
M#0H -#8P(# P," P.3 -"B P.#  ,#$P(# T, T*#0H ,# P(# U," P,S -
M"B P,S  .3 P(# U,0T*(# P," P,#8 ,# P#0H-"B P,#0 ,#DW(# P, T*
M(#4P," P,#  ,# P#0H ,#DP(# R," W,# -" T*#0H ,C4Q(#0W.2 X-C,-
M"B T-C< ,C,X(#$Y-0T*(#DX,R V,34 ,C0W#0H-"B X-#D -S4Q(#8S, T*
M(#<S-B Y.#( -#4Q#0H ,3(U(#,T-B Y-S -" T*(#,Q-" X.3< -3(V#0H 
M-3<R(#$V-" S.#D-"B V.3  -3(S(#<Q- T*/3T]/3T]/3T]/3T]/3T]/3T]
M/3T]/3T-" T*(# Y," P,#  ,#,P#0H ,3 P(# P," X,# -"B P,#  ,S$R
M(#<P, T*#0H ,#4P(#8T," P,#<-"B P,#  -S,P(#(T, T*(# X," U,#  
M,# P#0H-"B P,C8 ,# P(# Q, T*(# P," P,#0 ,S P#0H ,# P(# U," P
M-C -" T*#0H ,CDU(# W-B T,S$-"B Q-S, -#DU(# R- T*(#8T." S,3( 
M-S4Y#0H-"B S-3( -C0Y(#$X-PT*(#DV,2 W,S  ,C0U#0H -# W(#4R,2 V
M.3,-" T*(#<R-B Y.#, -3$T#0H -3$Y(#(V-" S-S -"B X,S0 ,34W(#DV
M, T*/3T]/3T]/3T]/3T]/3T]/3T]/3T]/3T-" T*(# P," U-C  ,S P#0H 
M,3 P(# P," X,# -"B P,C0 ,# P(# P, T*#0H ,# Y(# P," P,# -"B P
M.#  -S(P(# P- T*(#8Q," X,#  ,# P#0H-"B P,#< ,C V(# P, T*(#0P
M," P.#  ,#,W#0H ,# P(#$P-" P.3 -" T*#0H .3<X(#4V,B S,30-"B Q
M,S8 -#DW(# R-0T*(#4R-" S,3  -S8Y#0H-"B W-#D -C4S(#$X, T*(#,X
M-2 W,C$ .30V#0H -C$R(# T.2 U-S,-" T*(# Y-R R,S8 -#4Q#0H -#8Q
M(#DX-2 R,S<-"B R-3, ,3<T(#8Y. T*/3T]/3T]/3T]/3T]/3T]/3T]/3T]
M/3T-" T*(# Y," P,S4 -# V#0H ,# Q(# P," P,# -"B P,#< ,# P(# X
M.0T*#0H ,#<P(#DT," P-3 -"B Q,#  ,C P(# P, T*(# P-B X,#  -S P
M#0H-"B P,#  ,# T(# S, T*(# P," V,#  ,#0P#0H -C U(# P," P,# -
M" T*#0H .#DR(#<S-2 T,38-"B U-C$ -# Y(#,W, T*(#0S-R Q-C( -3 Y
M#0H-"B R-S, .30V(#$U. T*(#$X-" R-3< .38S#0H .34V(# Q,R W,C0-
M" T*(#<R." U.30 -C,Q#0H ,S$Y(#8W." R-#4-"B V-#4 ,S(Q(# Y-PT*
M/3T]/3T]/3T]/3T]/3T]/3T]/3T]/3T-" T*(# U," P-C  ,#0P#0H ,# V
M(#(T-R P.3$-"B P,#  ,3DP(# P, T*#0H ,# P(#8P," Y,# -"B R,#  
M,# P(# X- T*(# P," S,#  ,# U#0H-"B P,S$ ,# P(# P. T*(# P," P
M,#  ,# V#0H ,# T(# P," R-3 -" T*#0H ,34Y(# V,R W-#(-"B S.#8 
M,C0W(#4Y,0T*(#<T,B Q.34 .#8S#0H-"B T,34 -C R(#DS-PT*(#(W,R U
M,3D -C T#0H -CDX(#,W-" Q,C4-" T*(#4S,2 Y,C8 -#<X#0H .3(W(#0U
5." S,38-"B X-C0 -S,Q(#(U.0T*
`
end
Aug 08 2008
prev sibling parent BCS <ao pathlink.com> writes:
Reply to wyverex,

It's not taking input in the correct format, but I do think I'll tie for 
the easiest solution as All I had to do was copy it from an old NG post of 
mine:


BTW 2.7 ms per program run las I checked.

import std.stdio;
import std.string;
import std.cstream;


struct Game
{
	char[81] value;
	ushort[81] mask;
	int count;

	int working;
	int guess;
	ushort guessMask;

}

//bool[81] changed;

class Block:Error{this(char[]c){super(c);}}

int main()
{
	Game current;
	Game[81] stack;
	int at;
	int iter;

	void Report(int z)
	{
		static char[] value = ".123456789";
debug		writef(
"
depth      = %d
found      = %d
iterations = %d
working    = %d
guess      = %d\n\n",
at, current.count, iter, current.working, current.guess);
		for(int y = 0; y < 9; y++)
		{
			for(int x = 0; x < 9; x++)
			{
				writef("%d  ",// value[
				current.value[y*9+x]);//]);
				if(2 == x%3) writef("  ");
			}
			writef("\n");
			if(2 == y%3) writef("\n");
		}

		debug for(int y = 0; y < 9; y++)
		{
			for(int x = 0; x < 9; x++)
			{
				int i = 0;
				ushort t = current.mask[y*9+x];
				for(int z=0; z<9; z++)
				{
					writef((t & 0x0100) ? "." : "!");
					i+=(t & 0x0100) ? 0 : 1;
					t<<=1;
				}

				writef("%d  ",i);
				if(2 == x%3) writef("  ");
			}
			writef("\n");
			if(2 == y%3) writef("\n");

		}
	};

	
//	int loop = 0; restart: loop++;

	at=0;
	current.count=0;
	current.working = -1;
	for(int i = 0; i<81; i++)
	{
		current.value[i] = 0;
		current.mask[i] = 0x0;
	}

	static byte[81] seeds = [
		0, 0, 0,  0, 0, 7,  4, 0, 2,
		7, 0, 0,  6, 0, 0,  0, 5, 8,
		0, 0, 5,  0, 8, 2,  0, 0, 0,

		0, 0, 8,  4, 0, 0,  0, 0, 7,
		3, 0, 0,  0, 0, 0,  0, 0, 4,
		0, 0, 0,  0, 0, 1,  9, 0, 0,

		0, 0, 0,  7, 3, 0,  6, 0, 0,
		9, 7, 0,  0, 0, 5,  0, 0, 3,
		1, 0, 3,  8, 0, 0,  0, 0, 0
		];

	foreach(int i, c;seeds)
		setValue(current, i, c);

//	Report(0);	writef(\n\n);

	bool delta;
	int v;

	do
	{
		do
		{
			delta = false;
			for(int c=0; c<80; c++)
			{
				switch(current.mask[c])
				{
					case 0x01ff:
						goto backUp;

					default:
					case 0xffff:
						continue;

					case 0x00ff:	v = 9; break;
					case 0x017f:	v = 8; break;
					case 0x01bf:	v = 7; break;
					case 0x01df:	v = 6; break;
					case 0x01ef:	v = 5; break;
					case 0x01f7:	v = 4; break;
					case 0x01fb:	v = 3; break;
					case 0x01fd:	v = 2; break;
					case 0x01fe:	v = 1; break;
				}
				setValue(current, c, v);
				delta = true;
			}
		}while (delta)

		while(false)	// skip this block unless we get here by goto
		{
			backUp:
			assert(0 < at);
			at--;
			current = stack[at];
			current.mask[current.working] ^= current.guessMask;
			debug writef("<<<<< backup %d\n", at);
		}

		with(current)
		{
				// find a unknown cell
			while(working == -1 || 0 != value[working])
			{
				working++;
				guess = 1;
				guessMask = 0x01;
			}

				// find an avalable value
			while(0 != (mask[working] & guessMask))
			{
				guess++;
				guessMask<<=1;
				if(9 < guess) goto backUp;
			}
		}

		// store off state
		stack[at] = current;
		at++;

		debug writef("cell=%d guess=%d\n", current.working, current.guess);
		//make move
		setValue(current, current.working, current.guess);

		
		iter++;

	}while(current.count < 81)

//	if(loop<1000) goto restart;
	Report(0);
	return 0;
}

byte[20][81] depends;
static this()
{
	int at;
	for(int set = 0; set<81; set++)
	{
		at=0;
		for(int to = 0; to<81; to++)
		{
			if(set == to) continue;
			if(	set/9 == to/9 ||
				set%9 == to%9 || 
				(
					(set/3)%3 == (to/3)%3 &&
					set/27 == to/27
				)
			)
				depends[set][at++] = to;
		}
		assert(at == 20);
	}
}


bool setValue(inout Game where, int what, int to)
{
	if(0 == to || 9 < to) return false;
	bool ret = false;
	short mask = 0x0001 << (to-1);

//	if(where.value[what] || where.mask[what] & mask) throw new Error(__FILE__":" 
~ itoa!(__LINE__)~" error\n");

	where.value[what] = to;
	where.mask[what] = 0xffff;
	where.count++;

	foreach(c;depends[what])
		where.mask[c] |= mask;

	return ret;
}











template decimalDigit(int n){const char[] decimalDigit = "0123456789"[n..n+1];} 

template itoa(long n){
	static if (n < 0)		const char[] itoa = "-" ~ itoa!(-n);  
	else static if (n < 10)		const char[] itoa = decimalDigit!(n); 
	else				const char[] itoa = itoa!(n/10L) ~ decimalDigit!(n%10L); }
Aug 08 2008