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

sudoku solver generalized

Code

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

//sudoku Information
enum int squareSide = 3;
enum int boardSide = squareSide ^^ 2;
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. **/

// But, atention, an ushort is only 16 bits. Change this to uint to be able to solve 25 x 25 sudoku's (http://dlang.org/type.html)
alias ushort SudokuCell; // contains only values in (0, everythingPossible)

// 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) {
        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 / squareSide * squareSide;
    immutable uint y = collIndex / squareSide * squareSide;

foreach (t; 0 .. boardSide)
        sudokuField[(x + t / squareSide) * boardSide + y + t % squareSide] &= 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) {
    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;
    }
	
	if(args[1].countchars("0-" ~ to!string(boardSide)) + args[1].countchars(".") < args[1].length){
		writeln("A sudoku is represented by digits with every unknown digit beeing '0' or '.'");
		return;
	}
	
    SudokuField sudokuField = everythingPossible;
    Occupied occupied = false;

foreach (uint i, c; args[1])
        if (c != '0' && c != '.')
            put(sudokuField, occupied, c - '0', i);

auto start = Clock.currStdTime();

backtrack(sudokuField, occupied); // solve it

writeln("Solved in ", (Clock.currStdTime() - start) / 10_000_000.0 , " seconds");
    writeln(sudokuField);
}

Application output:

Usage: /home/c111/c332 <sudoku>

Paste info

Author: Guest

Views: 153

Private: no

Expires: Never

Uploaded: 25.08.12 15:59

Votes: 0

Compilation

Compiler: DMD 2.062

Pointer size: m64

Code

Application output:

Paste info

Compilation

Actions

Confirm

Confirm