DPaste - Paste #1618 - pastebin, online compiler and collaboration tool dedicated to D Programming Language

newSudoku fixed for 64 bit

Code

import std.range;
import std.algorithm;
import std.stdio;
import std.datetime;
import std.string;

//a short is 9 bits with every bit beeing a possibility
//000000001 => 1 is possible
//010000010 => 8 and 2 are possible
//this was the idea of timon gehr

//everything possible, the default value of every sudoku cell
const short everythingPossible=0b111111111;

//turn a short in a bitset range
auto bitsetToRange(short x){
	//bitshift it and check the last bit. if it's one, that number is a possibility
	return iota(0,9).filter!(i=>(x>>i)&1);
}

unittest{
	assert(equal(bitsetToRange(everythingPossible),iota(0,9)));
	assert(equal(bitsetToRange(0b100100100),[2,5,8]));
}

//easy to cache, very few possibilities (2^9)
int[][0b1000000000] generateBitsetCache(){
    int[][0b1000000000] returnValue;

foreach(short x;0..0b1000000000)
		returnValue[x]=array(bitsetToRange(x));

return returnValue;
}

int[][0b1000000000] cachedBitsetToRange;

void main(string[] args){

//would be nice if we could use ctfe here but it's not working :( ...
	//probably lack of experience on my side but I seem to allways fail at using ctfe
	cachedBitsetToRange=generateBitsetCache();

if(args.length!=2){
		writeln("usage: ./newSudoku <sudoku>");
		return;
	}

if(args[1].length!=81){
		writeln("a sudoku is 81 digits, not ",args[1].length," digits");
		return;
	}

short[81] possibilities;
	possibilities[]=everythingPossible;
	ubyte[81] taken;
	taken[]=false;

foreach(int i,char c;args[1])
		if(c!='0')
			put(possibilities,taken,cast(short)(c-'0'),i);

auto start=Clock.currStdTime();

//the solving part
	backtrack(possibilities,taken);

writeln(Clock.currStdTime()-start);
	writeln(possibilities);
}

//put a certain possibility at index and update possibilities along the way
void put(ref short[81] possibilities,ref ubyte[81] taken, int possibility,int index){
	//valid possibility
	assert(possibility<=9 && possibility >=1);
	
	//no use putting something somewhere twice is there?
	assert(!taken[index]);
	
	taken[index]=true;

short bitRepresentation=cast(short)(1<<(possibility-1));

//compute the inverse and and it, that way we filter out "possibility"
	short mask=0b111111111 ^ bitRepresentation;

// 0b000000001 => 0b111111110
	// every & operation will thus remove possibility

int rowIndex=index/9;
	int collIndex=index%9;

foreach(ref c;possibilities[rowIndex*9..(rowIndex+1)*9])
		c&= mask;

foreach(ref x;0..9)
		possibilities[x*9+collIndex] &= mask;

int x=rowIndex/3*3;
	int y=collIndex/3*3;

foreach(ref int t;0..9)
		possibilities[(x+t/3)*9+y+t%3] &= mask;

possibilities[index]=bitRepresentation;		
}

//returns -1 if the sudoku contains an empty field
//solves single candidates
//returns the field with the least possibilities
//if everything was solved, return 81
int optimize(ref short[81] possibilities,ref ubyte[81] taken){
	int returnValue=81;
	int leastPossibilities=10;
	
	foreach(int i,ref short x;possibilities){
		//length is uint on 32 bit machines but ulong on 64 bit machines
		//as the maximum length is 9, we can safely cast it to int and make it work on both environments
		int curLength=cast(int)cachedBitsetToRange[x].length;
	
		switch(curLength){
 			case 0://no possibilities
				return -1;
			case 1:
				if(!taken[i])
					put(possibilities,taken,cachedBitsetToRange[x][0]+1,i);
				break;
			default:
				if(curLength<leastPossibilities){
					assert(!taken[i],format("whait, what? %s",x));
					returnValue=i;
					leastPossibilities=curLength;
				}
		}
	}
	return returnValue;
}

ubyte backtrack(ref short[81] possibilities, ref ubyte[81] taken){
	int index=optimize(possibilities,taken);
	
	//we finished
	if(index==81)
		return true;
	
	//contained an empty field
	if(index==-1)
		return false;
	
	//foreach loop will destroy these but we still need them in case of bad candidates
	short[81] backupPossibilities=possibilities;
	ubyte[81] backupTaken=taken;

//iterate all possibilities and try them out, one by one
	foreach(int curPossibility;cachedBitsetToRange[possibilities[index]]){
		curPossibility++; //if 0 is a possibility in that range, we actually mean 1 ...

put(possibilities,taken,curPossibility,index);

if(backtrack(possibilities,taken))
			return true;

//it failed, restore everything
		taken=backupTaken;
		possibilities=backupPossibilities;
	}
	
	//iterated everything without success? return false
	return false;
}

Application output:

usage: ./newSudoku <sudoku>

Paste info

Author: Guest

Views: 82

Private: no

Expires: Never

Uploaded: 24.08.12 23:28

Parent: #8a2aef5b

Votes: 0

Compilation

Compiler: DMD 2.062

Pointer size: m64

Code

Application output:

Paste info

Compilation

Actions

Confirm

Confirm