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

sudokuSolver_improved

Code

import std.stdio;
import std.datetime;
import std.algorithm;

void main(string[] args){
	if(args.length<2){
		writeln("Usage: ./quickSudoku sudoku");
		writeln("The sudoku is represented by a string of digits with every unknown digit beeing 0");
		return;
	}
	
	if(args[1].length!=81){
		writeln("A sudoku is 81 digits, not ",args[1].length," digits");
		return;
	}

int[81] sudoku;
	foreach(int i,char c;args[1]){
		sudoku[i]=cast(int)c-'0';
	}

auto start=Clock.currStdTime();
	fill(sudoku,0);
	writeln(Clock.currStdTime()-start);

foreach(int c;sudoku)
		write(c);
	writeln(); //newline
}

static ubyte fill(ref int[81] sudoku,int index){
	assert(index<81);
	
	if(sudoku[index]!=0){
		if(index==80)
			return true;
		else
			return fill(sudoku,index+1);
	}

ubyte[10] region=getRegion(sudoku,index);
		
	foreach(int number;1..10){
		//if that number is already present in it's region, pick a new one
		if(region[number])
			continue;

sudoku[index]=number;
		
		if(index==80){
			return true;
		}else{
			if(fill(sudoku,index+1)==true)
				return true;	
		}
	}

sudoku[index]=0;
	return false;
}

ubyte[10] getRegion(ref int[81] sudoku, int index){
	ubyte[10] tempRegion;
	int[9] tempSerie;

//row
	tempSerie[]=sudoku[index/9*9..(index/9+1)*9];

foreach(int curNumber;tempSerie)
		tempRegion[curNumber]=true;		
	
	for(int x=0;x<9;x++)
		tempSerie[x]=sudoku[x*9+index%9];

foreach(int curNumber;tempSerie)
		tempRegion[curNumber]=true;
	
	int x=(index/9)/3*3;
	int y=(index%9)/3*3;
	tempSerie[]=sudoku[x*9+y..x*9+y+3] ~ sudoku[(x+1)*9+y..(x+1)*9+y+3] ~ sudoku[(x+2)*9+y..(x+2)*9+y+3];

foreach(int curNumber;tempSerie)
		tempRegion[curNumber]=true;

return tempRegion;
}

Application output:

Usage: ./quickSudoku sudoku
The sudoku is represented by a string of digits with every unknown digit beeing 0

Paste info

Author: Guest

Views: 119

Private: no

Expires: Never

Uploaded: 19.08.12 18:29

Votes: 0

Compilation

Compiler: DMD 2.062

Pointer size: m64

Code

Application output:

Paste info

Compilation

Actions

Confirm

Confirm