Programming Puzzle 8-8-08
BCS
ao at pathlink.com
Fri Aug 8 13:17:25 PDT 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); }
More information about the Digitalmars-d-learn
mailing list