digitalmars.D.learn - Programming Puzzle 8-8-08
- Wyverex (60/60) Aug 08 2008 Another day, another puzzle!! I'll try keeping this up as long as I can...
- Wyverex (108/108) Aug 08 2008 //Heres a backtracking solution
- Steven Schveighoffer (273/273) Aug 08 2008 Depth-first brute force with the standard sudoku constraints
- BCS (200/200) Aug 08 2008 Reply to wyverex,
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
Wyverex <wyverex.cypher gmail.com>
//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
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,R U,C$-"B U,S$ ,C V(#DT-PT*/3T]/3T]/3T]/3T]/3T]/3T]/3T]/3T-
M"B W,38 ,C U(#DT
M-S0 ,3 V(#DU
M-#DR
M.#DQ
M,PT*(#DT
M"B P,#D
M/3T]/3T]/3T]/3T]/3T]/3T-" T*(#DP
M/3T]/3T]/3T]/3T]/3T-" T*(#DU
M,C U(#DV-
M." U,S8-" T*(#DX-B
M,S8 -#DW
M(#DX-2
`
end
Aug 08 2008
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