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

sudokusolver

Code

import std.range, std.algorithm, std.string, std.conv;

//sudoku Information
enum int squareWidth = 5;
enum int squareHeight = 5;
enum int boardSide = squareWidth * squareHeight;
enum int boardSize = boardSide ^^ 2;

/** A SudokuCell is "boardSide" bits with every bit beeing a possibility
000000001 => 1 is possible
010000010 => 8 and 2 are possible
This was the idea of Timon Gehr. **/

// SudokuCell contains only values in (0, everythingPossible) (a RangedValue when available)
static if (boardSide <= short.sizeof * 8) {
     alias ushort SudokuCell;
} else static if (boardSide <= uint.sizeof * 8) {
     alias uint SudokuCell;
} else static if (boardSide <= ulong.sizeof * 8) {
     alias ulong SudokuCell;
} else
     static assert(false, "BoardSide is too big, no value has enough bits to store all possibilities in");

// everything possible, the default value of every Sudoku cell
enum SudokuCell everythingPossible = cast(SudokuCell) (2 ^^ boardSide - 1);

alias SudokuCell[boardSize] SudokuField;
alias bool[boardSize] Occupied;// ucent is useful here as bitmask (or maybe try to use array!bool?)

/// Inlined array with variable (but limited) length.
struct MaxArray(T, size_t maxLen) {
    T[maxLen] data;
    private uint len;
    alias items this;

void opAssign(T[] a) pure nothrow {
        this.data[0 .. a.length] = a;
        this.len = cast(typeof(len))a.length;
    }

@property T[] items() pure nothrow {
        return data[0 .. len];
    }
}

//__gshared improves performance as does MaxArray
__gshared MaxArray!(int, boardSide)[2 ^^ boardSide] cachedBitsetToRange;

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

unittest {
    assert(bitsetToRange(everythingPossible).equal(iota(boardSide)));
    assert(bitsetToRange(0b1_0010_0100).equal([2, 5, 8]));
}

// easy to cache, very few possibilities (2 ^^ boardSide)
void generateBitsetCache() {
    foreach (SudokuCell i, ref x; cachedBitsetToRange)
        x = bitsetToRange(i).array();
}

/// put a certain possibility at index and update possibilities along the way
void put(ref SudokuField sudokuField, ref Occupied occupied, in int possibility, in uint index)
pure nothrow in {
    // valid possibility
    assert(possibility >= 1 && possibility <= boardSide);

// no use putting something somewhere twice is there?
    assert(!occupied[index]);
} body {
    occupied[index] = true;

immutable bitRepresentation = cast(SudokuCell)(1 << (possibility - 1));

// compute the inverse and "and" it, that way we filter out "possibility"
    immutable SudokuCell mask = everythingPossible ^ bitRepresentation;

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

immutable uint rowIndex = index / boardSide;
    immutable uint collIndex = index % boardSide;

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

foreach (x; 0 .. boardSide)
        sudokuField[x * boardSide + collIndex] &= mask;

immutable uint x = rowIndex / squareHeight * squareHeight;
    immutable uint y = collIndex / squareWidth * squareWidth;

foreach (t; 0 .. boardSide)
        sudokuField[(x + t / squareWidth) * boardSide + y + t % squareHeight] &= mask;

sudokuField[index] = bitRepresentation;
}

/**
Returns -1 if the sudoku contains an empty field solves single candidates.
Returns the field with the least possibilities and if everything was solved, return boardSize.
*/
int optimize(ref SudokuField sudokuField, ref Occupied occupied) nothrow{
    int returnValue = boardSize;
    size_t leastPossibilities = boardSide + 1;

foreach (int i, x; sudokuField) {
        immutable curLength = cachedBitsetToRange[x].length;

switch (curLength) {
            case 0: // no possibilities
                return -1;
            case 1:
                if (!occupied[i])
                    put(sudokuField, occupied, cachedBitsetToRange[x][0] + 1, i);
                break;
            default:
                if (curLength < leastPossibilities) {
                    returnValue = i;
                    leastPossibilities = curLength;
                }
        }
    }

return returnValue;
}

bool backtrack(ref SudokuField sudokuField, ref Occupied occupied) nothrow{
    immutable int index = optimize(sudokuField, occupied);

// we finished
    if (index == boardSize)
        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
    SudokuField backupSudokuField = sudokuField;
    Occupied backupOccupied = occupied;

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

put(sudokuField, occupied, curPossibility, index);

if (backtrack(sudokuField, occupied))
            return true;

// it failed, restore everything
        occupied = backupOccupied;
        sudokuField = backupSudokuField;
    }

// iterated everything without success? return false
    return false;
}

void main(in string[] args) {
    import std.stdio, std.datetime;
	
    generateBitsetCache();

if (args.length != 2) {
        writeln("Usage: ", args[0], " <sudoku>");
        return;
    }

if (args[1].length != boardSize) {
        writeln("A sudoku is ",boardSize," digits, not ", args[1].length, " digits");
        return;
    }
	
    SudokuField sudokuField = everythingPossible;
    Occupied occupied = false;

foreach (uint i, c; args[1]){
		int charToPossibility = -1;
		
        if (inPattern(c, "1-9"))
            charToPossibility = c - '0';
		if (inPattern(c,"a-b"))
			charToPossibility = c - 'a' + 10;
		if (inPattern(c,"A-B"))
			charToPossibility = c - 'A' + 10 + 26;
			
		if(charToPossibility > boardSide){
			writeln(c, " at index ", i + 1, " is out of range 1-", boardSide);
			return;
		}
		
		if(charToPossibility != -1)
			put(sudokuField, occupied, charToPossibility, i);
	}
	
    auto start = Clock.currStdTime();

backtrack(sudokuField, occupied); // solve it

writeln("Solved in ", (Clock.currStdTime() - start) / 10_000_000f , " seconds");
    writeln(map!(x => cachedBitsetToRange[x])(sudokuField[]));
}

Compilation output:

/usr/local/lib/dmd2/libphobos2.a(gc_2fa_390.o): In function `gc_enable':
src/gc/gc.d:(.text.gc_enable+0x7): relocation truncated to fit: R_X86_64_PC32 against symbol `_D2gc2gc5proxyPS2gc2gc5Proxy' defined in .bss section in /usr/local/lib/dmd2/libphobos2.a(gc.o)
src/gc/gc.d:(.text.gc_enable+0x11): relocation truncated to fit: R_X86_64_PC32 against symbol `_D2gc2gc3_gcC2gc3gcx2GC' defined in .bss section in /usr/local/lib/dmd2/libphobos2.a(gc.o)
src/gc/gc.d:(.text.gc_enable+0x21): relocation truncated to fit: R_X86_64_PC32 against symbol `_D2gc2gc5proxyPS2gc2gc5Proxy' defined in .bss section in /usr/local/lib/dmd2/libphobos2.a(gc.o)
/usr/local/lib/dmd2/libphobos2.a(gc_2fb_3fd.o): In function `gc_disable':
src/gc/gc.d:(.text.gc_disable+0x7): relocation truncated to fit: R_X86_64_PC32 against symbol `_D2gc2gc5proxyPS2gc2gc5Proxy' defined in .bss section in /usr/local/lib/dmd2/libphobos2.a(gc.o)
src/gc/gc.d:(.text.gc_disable+0x11): relocation truncated to fit: R_X86_64_PC32 against symbol `_D2gc2gc3_gcC2gc3gcx2GC' defined in .bss section in /usr/local/lib/dmd2/libphobos2.a(gc.o)
src/gc/gc.d:(.text.gc_disable+0x21): relocation truncated to fit: R_X86_64_PC32 against symbol `_D2gc2gc5proxyPS2gc2gc5Proxy' defined in .bss section in /usr/local/lib/dmd2/libphobos2.a(gc.o)
/usr/local/lib/dmd2/libphobos2.a(gc_2fc_40f.o): In function `gc_collect':
src/gc/gc.d:(.text.gc_collect+0x7): relocation truncated to fit: R_X86_64_PC32 against symbol `_D2gc2gc5proxyPS2gc2gc5Proxy' defined in .bss section in /usr/local/lib/dmd2/libphobos2.a(gc.o)
src/gc/gc.d:(.text.gc_collect+0x11): relocation truncated to fit: R_X86_64_PC32 against symbol `_D2gc2gc3_gcC2gc3gcx2GC' defined in .bss section in /usr/local/lib/dmd2/libphobos2.a(gc.o)
src/gc/gc.d:(.text.gc_collect+0x24): relocation truncated to fit: R_X86_64_PC32 against symbol `_D2gc2gc5proxyPS2gc2gc5Proxy' defined in .bss section in /usr/local/lib/dmd2/libphobos2.a(gc.o)
/usr/local/lib/dmd2/libphobos2.a(gc_2fd_48b.o): In function `gc_minimize':
src/gc/gc.d:(.text.gc_minimize+0x7): relocation truncated to fit: R_X86_64_PC32 against symbol `_D2gc2gc5proxyPS2gc2gc5Proxy' defined in .bss section in /usr/local/lib/dmd2/libphobos2.a(gc.o)
src/gc/gc.d:(.text.gc_minimize+0x11): additional relocation overflows omitted from the output
collect2: error: ld returned 1 exit status
--- errorlevel 1

Paste info

Author: Guest

Views: 107

Private: no

Expires: Never

Uploaded: 26.08.12 0:53

Votes: 0

Compilation

Compiler: DMD 2.062

Pointer size: m64

Code

Compilation output:

Paste info

Compilation

Actions

Confirm

Confirm