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.......

//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;
}

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

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); }