Sudoku

[Puzzle]

Binnenkort post ik hier De Ultieme Oplossing ( niet zelf geschreven

Ja, ik wacht.

[Puzzle]

Het is ondertussen al verbeterd tot 292 microseconden en ik ga nog iets proberen.

microseconden of milliseconden ????

Ik zeg toch microseconden. Het meetresultaat staat op mijn website.

[Puzzle]

Binnenkort post ik hier De Ultieme Oplossing (niet zelf geschreven)

Voila, ik heb 3 oplossingen, geschreven door de prof.

Ik heb alles gekopieerd op word-file, maar het zijn 14 blz in totaal, maw te lang om hier te posten.

Geïnteresseerden sturen me maar een mailtje (galibier2646@hotmail.com ) en ik stuur ze op.

Doe toch niet zo flauw. 14 blz is ten hoogste 1400 lijntjes. Zet het hier gewoon op.

[Puzzle]

Aan het idee heb ik niets veranderd, maar wel aan de implementatie, die efficiënter geworden is.

Zaterdag had ik een versie van 168 microseconden op de beige Mac G3 van 233 MHz. Dat is vooral te wijten aan programmeertrucs en compileropties.

Daarna heb ik een implementatie geprobeerd met gelinkte lijsten. Ik dacht dat dat rapper ging zijn omdat het geen dubbel werk doet, maar ik kwam uit op 304 microseconden.

Het probleem is in feite dat je tijd verliest door een functie aan te roepen en door eerst nog eens parameters te kopiëren.

Als je het doet volgens de regels van de kunst dan heb je vele functies met een paar instructies in en dan verlies je voornamelijk tijd met het aanroepen van functies. Typisch aan mijn oplossing is dat het maar een akkefietje was om er ook iets anders mee te doen, zoals random puzzels maken.

Als je alles in een paar functies schrijft met vele instructies in, dan zal het rapper werken, maar dan zijn de data niet beschermd, dan is het moeilijk om te lezen, om te debuggen of om er nog iets anders mee te doen.


______________________
Een programma met 1 functie is zoals een wetboek met 1 artikel.

[Galibier2646]

package sudoko;

import java.io.PrintWriter;
import java.util.SortedSet;
import java.util.TreeSet;

public class BoardBruteForce implements BoardI {

static class Unit {

SortedSet<Integer> todo = new TreeSet<Integer>();

SortedSet<Integer> done = new TreeSet<Integer>();

public Unit() {
for (int i = 1; i < 10; i++) {
todo.add(i);
}
}

}

static class Square extends Unit {

private int[][] cells = new int[3][3];

public void set(final int r, final int c, final int v) {

if (!check(r, c, v))
throw new RuntimeException("value already contained in unit or position taken: " + this);

cells[r][c] = v;
todo.remove(v);
done.add(v);
}

public void clear(final int r, final int c, final int v) {

cells[r][c] = 0;
todo.add(v);
done.remove(v);
}

public boolean check(final int r, final int c, final int v) {
return cells[r][c] == 0 && todo.contains(v);
}

public void toWriter(final PrintWriter printWriter) {
for (int[] row : cells) {
printWriter.print("|");
for (int cell : row) {
printWriter.print(cell + "|");
}
printWriter.println();
}
}
}

static class Row extends Unit {

private int[] cells = new int[9];

public void set(final int c, final int v) {

if (!check(c, v))
throw new RuntimeException("value already contained in unit or position taken: " + this);

cells[c] = v;
todo.remove(v);
done.add(v);
}

public void clear(final int c, final int v) {

cells[c] = 0;
todo.add(v);
done.remove(v);
}

public boolean check(final int c, final int v) {
return cells[c] == 0 && todo.contains(v);
}

public void toWriter(final PrintWriter printWriter) {
printWriter.print("|");
for (int cell : cells) {
printWriter.print(cell + "|");
}
printWriter.println();
}
}

static class Column extends Row {
}

// state

Square[][] asSquares = new Square[3][3];

Row[] asRows = new Row[9];

Column[] asColumns = new Column[9];

int iteration = 0;

// constructors

public BoardBruteForce() {

Solver.out.println("BoardMostConstrainedRowFirst(): contructor");
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
asSquares[j] = new Square();
}
}
for (int i = 0; i < 9; i++) {
asRows = new Row();
}
for (int i = 0; i < 9; i++) {
asColumns = new Column();
}
}

public void init(final int[][] board) {
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
if (board[j] == 0)
continue;
else
set(i, j, board[j]);
}
}
}

// modifiers

public void set(final int r, final int c, final int v) {
asSquares[r / 3][c / 3].set(r % 3, c % 3, v);
asRows[r].set(c, v);
asColumns[c].set(r, v);
}

public void clear(final int r, final int c, final int v) {
asSquares[r / 3][c / 3].clear(r % 3, c % 3, v);
asRows[r].clear(c, v);
asColumns[c].clear(r, v);
}

// readers

public boolean check(final int r, final int c, final int v) {
return asSquares[r / 3][c / 3].check(r % 3, c % 3, v) && asRows[r].check(c, v) && asColumns[c].check(r, v);
}

public void toWriter(final PrintWriter printWriter) {

printWriter.println("AS ROWS");
for (Row row : asRows) {
row.toWriter(printWriter);
}

// printWriter.println("AS COLUMS");
// for (Column column : asColumns) {
// column.toWriter(printWriter);
// }
//
// printWriter.println("AS SQUARES");
// for (Square[] squares : asSquares) {
// for (Square square : squares) {
// square.toWriter(printWriter);
// }
// }
}

public boolean solve(final int rowIndex, final int columnIndex) {

iteration++;

// board is solved
if (rowIndex == 9) {
Solver.out.println("SOLUTION FOUND");
return true;
} else {

final Row row;
row = asRows[rowIndex];

// row is solved ( nothing to do )
if (row.todo.isEmpty()) {
return solve(rowIndex + 1, 0);
} else {
// cell is empty
if (row.cells[columnIndex] == 0) {
for (int value : row.todo.toArray(new Integer[0])) {
if (check(rowIndex, columnIndex, value)) {
set(rowIndex, columnIndex, value);
if (solve(rowIndex, columnIndex + 1))
return true;
else
clear(rowIndex, columnIndex, value);
}
}
// nothing worked
return false;
} else {
// cell is not empty
return solve(rowIndex, columnIndex + 1);
}
}
}
}

public boolean solve() {
return solve(0, 0);
}

public int getIterations() {
return iteration;
}
}


package sudoko;

import java.io.IOException;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.Collections;
import java.util.LinkedList;
import java.util.List;

public class BoardConstrainedCellFirst implements BoardI {

static class Cell implements Comparable<Cell> {

private int x;

private int y;

private boolean[] bbRow;

private boolean[] bbColumn;

private boolean[] bbSquare;

private int nrOfOptions;

private int value;

public Cell(final int x, final int y) {

this.x = x;
this.y = y;

bbRow = new boolean[9];
bbColumn = new boolean[9];
bbSquare = new boolean[9];

for (int i = 0; i < 9; i++) {
bbRow = false;
bbColumn = false;
bbSquare = false;
}

nrOfOptions = 8;
value = -1;
}

public int getNrOfOptions() {
return nrOfOptions;
}

public int get() {
if (value == -1) {
if (nrOfOptions == 0) {
for (int i = 0; i < 9; i++) {
if (!bbRow && !bbColumn & !bbSquare[i])
return i;
}
throw new RuntimeException("error in algorithm");
} else
return -nrOfOptions - 1;
} else
return value;
}

public int[] getOptions() {
int[] options;
options = new int[nrOfOptions + 1];
int j = 0;
for (int i = 0; i < 9; i++)
if (!bbRow[i] && !bbColumn[i] & !bbSquare[i])
options[j++] = i;
return options;
}

public void set(int value) {
this.value = value;
}

public void unset() {
this.value = -1;
}

public void removeFromSquare(int value) {
bbSquare[value] = true;
// nrOfOptions--; ??
}

public void removeFromColumn(int value) {
bbColumn[value] = true;
// nrOfOptions--; ??
}

public void removeFromRow(int value) {
bbRow[value] = true;
// nrOfOptions--; ??
}

public void activate(int value) {
// nrOfOptions++; ??
}

public boolean check(int value) {
return !bbRow[value] && !bbColumn[value] & !bbSquare[value];
}

public int compareTo(Cell other) {
if (this.value != -1)
return +1;
if (other.value != -1)
return -1;
return this.nrOfOptions - other.nrOfOptions;
}

public String toString() {
return x + "," + y + "=>" + (get() + 1) + "[" + nrOfOptions + "]";
}
}

// state

Cell[][] board = new Cell[9][9];

List<Cell> cells = new ArrayList<Cell>(81);

int iteration = 0;

// constructors

public BoardConstrainedCellFirst() {

for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
board[i][j] = new Cell(i, j);
cells.add(board[i][j]);
}
}
}

public void init(final int[][] board) {
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
if (board[i][j] == 0)
continue;
else
set(i, j, board[i][j] - 1);
}
}
}

// modifiers

public void set(final int r, final int c, final int v) {

board[r][c].set(v);

// update row
for (int i = 0; i < 9; i++)
board[i][c].remove(v);

// update column
for (int i = 0; i < 9; i++)
board[r][i].remove(v);

// update square
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
board[r / 3 * 3 + i][c / 3 * 3 + j].remove(v);
}
}
}

public void unset(final int r, final int c, final int v) {

board[r][c].unset();

// update row
for (int i = 0; i < 9; i++)
board[i][c].activate(v);

// update column
for (int i = 0; i < 9; i++)
board[r][i].activate(v);

// update square
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
board[r / 3 * 3 + i][c / 3 * 3 + j].activate(v);
}
}
}

// readers

public boolean check(final int r, final int c, final int v) {
return board[r][c].check(v);
}

public void toWriter(final PrintWriter printWriter) {

for (int i = 0; i < 9; i++) {
printWriter.print("|");
for (int j = 0; j < 9; j++) {
final int value = board[i][j].get() + 1;
if (value > 0)
printWriter.print(" " + value + "|");
else
printWriter.print(value + "|");
}
printWriter.println();
}
}

public boolean solve() throws IOException {

iteration++;

Collections.sort(cells);
System.out.println(cells);
// System.in.read();

final Cell cell;
cell = cells.get(0);

if (cell.value != -1) {
System.out.println("SOLUTION");
return true;
} else if (cell.nrOfOptions == 0) {
set(cell.x, cell.y, cell.get());
return solve();
} else {
for (int i : cell.getOptions()) {
set(cell.x, cell.y, i);
if (solve() == false) {
System.out.println("backtrack");
unset(cell.x, cell.y, i);
} else
return true;
}
}

return false;
}

public int getIterations() {
return iteration;
}

}
package sudoko;

import java.io.PrintWriter;
import java.util.SortedSet;
import java.util.TreeSet;

public class BoardMostConstrainedRowFirst implements BoardI {

abstract static class Unit {

SortedSet<Integer> todo = new TreeSet<Integer>();

SortedSet<Integer> done = new TreeSet<Integer>();

public Unit() {
for (int i = 1; i < 10; i++) {
todo.add(i);
}
}

}

static class Square extends Unit {

private int[][] cells = new int[3][3];

public void set(final int r, final int c, final int v) {

if (!check(r, c, v))
throw new RuntimeException("value already contained in unit or position taken: " + this);

cells[r][c] = v;
todo.remove(v);
done.add(v);
}

public void clear(final int r, final int c, final int v) {

cells[r][c] = 0;
todo.add(v);
done.remove(v);
}

public boolean check(final int r, final int c, final int v) {
return cells[r][c] == 0 && todo.contains(v);
}

public void toWriter(final PrintWriter printWriter) {
for (int[] row : cells) {
printWriter.print("|");
for (int cell : row) {
printWriter.print(cell + "|");
}
printWriter.println();
}
}
}

static class Row extends Unit {

private int[] cells = new int[9];

public void set(final int c, final int v) {

if (!check(c, v))
throw new RuntimeException("value already contained in unit or position taken: " + this);

cells[c] = v;
todo.remove(v);
done.add(v);
}

public void clear(final int c, final int v) {

cells[c] = 0;
todo.add(v);
done.remove(v);
}

public boolean check(final int c, final int v) {
return cells[c] == 0 && todo.contains(v);
}

public void toWriter(final PrintWriter printWriter) {
printWriter.print("|");
for (int cell : cells) {
printWriter.print(cell + "|");
}
printWriter.println();
}
}

static class Column extends Row {
}

// state

Square[][] asSquares = new Square[3][3];

Row[] asRows = new Row[9];

Column[] asColumns = new Column[9];

int iteration = 0;

// constructors

public BoardMostConstrainedRowFirst() {

Solver.out.println("BoardMostConstrainedRowFirst(): contructor");
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
asSquares[i][j] = new Square();
}
}
for (int i = 0; i < 9; i++) {
asRows[i] = new Row();
}
for (int i = 0; i < 9; i++) {
asColumns[i] = new Column();
}
}

public void init(final int[][] board) {
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
if (board[i][j] == 0)
continue;
else if (check(i, j, board[i][j]))
set(i, j, board[i][j]);
}
}
}

// modifiers

public void set(final int r, final int c, final int v) {
asSquares[r / 3][c / 3].set(r % 3, c % 3, v);
asRows[r].set(c, v);
asColumns[c].set(r, v);
}

public void clear(final int r, final int c, final int v) {
asSquares[r / 3][c / 3].clear(r % 3, c % 3, v);
asRows[r].clear(c, v);
asColumns[c].clear(r, v);
}

// readers

public boolean check(final int r, final int c, final int v) {
return asSquares[r / 3][c / 3].check(r % 3, c % 3, v) && asRows[r].check(c, v) && asColumns[c].check(r, v);
}

public void toWriter(final PrintWriter printWriter) {

printWriter.println("AS ROWS");
for (Row row : asRows) {
row.toWriter(printWriter);
}

// printWriter.println("AS COLUMS");
// for (Column column : asColumns) {
// column.toWriter(printWriter);
// }
//
// printWriter.println("AS SQUARES");
// for (Square[] squares : asSquares) {
// for (Square square : squares) {
// square.toWriter(printWriter);
// }
// }
}

public boolean solve() {

iteration++;

final int rowIndex;
rowIndex = getConstrainedRowIndex();
if (rowIndex == -1) {
Solver.out.println("SOLUTION FOUND");
return true;
}

final Row row;
row = asRows[rowIndex];

// find empty cell
int columnIndex = -1;
for (int i = 0; i < 9; i++)
if (row.cells[i] == 0) {
columnIndex = i;
break;
}
if (columnIndex == -1)
throw new RuntimeException("error in algorithm");

// put something in cell, recurse
for (int value : row.todo.toArray(new Integer[0])) {
if (check(rowIndex, columnIndex, value)) {
set(rowIndex, columnIndex, value);
if (solve())
return true;
else
clear(rowIndex, columnIndex, value);
}
}
// nothing worked
return false;

}

private int getConstrainedRowIndex() {

int foundIndex = -1;
for (int candidateIndex = 0; candidateIndex < 9; candidateIndex++) {
if (asRows[candidateIndex].todo.isEmpty())
continue;
if (foundIndex == -1)
foundIndex = candidateIndex;
else if (asRows[candidateIndex].todo.size() < asRows[foundIndex].todo.size())
foundIndex = candidateIndex;
}
return foundIndex;
}

public int getIterations() {
return iteration;
}

}


package sudoko;

import java.io.IOException;
import java.io.PrintWriter;

public interface BoardI {

public abstract void init(final int[][] board);

public abstract void toWriter(final PrintWriter printWriter);

public abstract boolean solve() throws IOException;

public abstract int getIterations();

}


package sudoko;

import java.io.IOException;
import java.io.PrintWriter;

public class Solver {

static final PrintWriter out = new PrintWriter(System.out);

public static void main(String[] args) throws IOException {

out.println("Creating BoardMostConstrainedRowFirst");
BoardI board;
board = new BoardConstrainedCellFirst();

out.println("Setting Cells");

// easy
// board.init(new int[][] {
// {
// 7, 0, 0, 0, 2, 4, 1, 0, 0 }, {
// 0, 3, 0, 0, 0, 6, 0, 0, 0 }, {
// 9, 4, 0, 7, 0, 0, 6, 3, 2 }, {
// 0, 2, 0, 0, 0, 0, 0, 1, 3 }, {
// 0, 0, 9, 0, 0, 0, 4, 0, 0 }, {
// 5, 1, 0, 0, 0, 0, 0, 9, 0 }, {
// 6, 9, 1, 0, 0, 3, 0, 4, 7 }, {
// 0, 0, 0, 5, 0, 0, 0, 2, 0 }, {
// 0, 0, 5, 9, 4, 0, 0, 0, 8 }, });

// evil
board.init(new int[][] {
{
7, 0, 0, 2, 9, 0, 0, 0, 0 }, {
0, 4, 0, 1, 0, 0, 7, 0, 5 }, {
8, 0, 0, 0, 0, 3, 0, 0, 0 }, {
0, 0, 0, 3, 0, 0, 1, 0, 0 }, {
0, 9, 0, 0, 1, 0, 0, 2, 0 }, {
0, 0, 7, 0, 0, 8, 0, 0, 0 }, {
0, 0, 0, 8, 0, 0, 0, 0, 2 }, {
9, 0, 6, 0, 0, 4, 0, 1, 0 }, {
0, 0, 0, 0, 3, 1, 0, 0, 8 } });

out.flush();

board.solve();

out.println("Nr of iterations: " + board.getIterations());
board.toWriter(out);

out.flush();
}
}

[Flip FSR]

Voorzichtig vraagje: Is er dan niemand van jullie die zijn verstand gebruikt om die puzzels op te lossen ipv het internet
Allez, zo doe ik het af en toe...
Maar ja, ik snap dan ook niks nougaballen van alles dat hierboven staat

[Puzzle]

Ik ga dat eerst eens in een code-blok zetten zodat geïndenteerd is zodat iedereen het kan lezen.

Code: Selecteer alles

package sudoko;

import java.io.PrintWriter;
import java.util.SortedSet;
import java.util.TreeSet;

public class BoardBruteForce implements BoardI {

    static class Unit {

        SortedSet<Integer> todo = new TreeSet<Integer>();

        SortedSet<Integer> done = new TreeSet<Integer>();

        public Unit() {
            for (int i = 1; i < 10; i++) {
                todo.add(i);
            }
        }

    }

    static class Square extends Unit {

        private int[][] cells = new int[3][3];

        public void set(final int r, final int c, final int v) {

            if (!check(r, c, v))
                throw new RuntimeException("value already contained in unit or position taken: " + this);

            cells[r][c] = v;
            todo.remove(v);
            done.add(v);
        }

        public void clear(final int r, final int c, final int v) {

            cells[r][c] = 0;
            todo.add(v);
            done.remove(v);
        }

        public boolean check(final int r, final int c, final int v) {
            return cells[r][c] == 0 && todo.contains(v);
        }

        public void toWriter(final PrintWriter printWriter) {
            for (int[] row : cells) {
                printWriter.print("|");
                for (int cell : row) {
                    printWriter.print(cell + "|");
                }
                printWriter.println();
            }
        }
    }

    static class Row extends Unit {

        private int[] cells = new int[9];

        public void set(final int c, final int v) {

            if (!check(c, v))
                throw new RuntimeException("value already contained in unit or position taken: " + this);

            cells[c] = v;
            todo.remove(v);
            done.add(v);
        }

        public void clear(final int c, final int v) {

            cells[c] = 0;
            todo.add(v);
            done.remove(v);
        }

        public boolean check(final int c, final int v) {
            return cells[c] == 0 && todo.contains(v);
        }

        public void toWriter(final PrintWriter printWriter) {
            printWriter.print("|");
            for (int cell : cells) {
                printWriter.print(cell + "|");
            }
            printWriter.println();
        }
    }

    static class Column extends Row {
    }

    // state

    Square[][] asSquares = new Square[3][3];

    Row[] asRows = new Row[9];

    Column[] asColumns = new Column[9];

    int iteration = 0;

    // constructors

    public BoardBruteForce() {

        Solver.out.println("BoardMostConstrainedRowFirst(): contructor");
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                asSquares[i][j] = new Square();
            }
        }
        for (int i = 0; i < 9; i++) {
            asRows[i] = new Row();
        }
        for (int i = 0; i < 9; i++) {
            asColumns[i] = new Column();
        }
    }

    public void init(final int[][] board) {
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                if (board[i][j] == 0)
                    continue;
                else
                    set(i, j, board[i][j]);
            }
        }
    }

    // modifiers

    public void set(final int r, final int c, final int v) {
        asSquares[r / 3][c / 3].set(r % 3, c % 3, v);
        asRows[r].set(c, v);
        asColumns[c].set(r, v);
    }

    public void clear(final int r, final int c, final int v) {
        asSquares[r / 3][c / 3].clear(r % 3, c % 3, v);
        asRows[r].clear(c, v);
        asColumns[c].clear(r, v);
    }

    // readers

    public boolean check(final int r, final int c, final int v) {
        return asSquares[r / 3][c / 3].check(r % 3, c % 3, v) && asRows[r].check(c, v) && asColumns[c].check(r, v);
    }

    public void toWriter(final PrintWriter printWriter) {

        printWriter.println("AS ROWS");
        for (Row row : asRows) {
            row.toWriter(printWriter);
        }

        // printWriter.println("AS COLUMS");
        // for (Column column : asColumns) {
        // column.toWriter(printWriter);
        // }
        //
        // printWriter.println("AS SQUARES");
        // for (Square[] squares : asSquares) {
        // for (Square square : squares) {
        // square.toWriter(printWriter);
        // }
        // }
    }

    public boolean solve(final int rowIndex, final int columnIndex) {

        iteration++;

        // board is solved
        if (rowIndex == 9) {
            Solver.out.println("SOLUTION FOUND");
            return true;
        } else {

            final Row row;
            row = asRows[rowIndex];

            // row is solved ( nothing to do )
            if (row.todo.isEmpty()) {
                return solve(rowIndex + 1, 0);
            } else {
                // cell is empty
                if (row.cells[columnIndex] == 0) {
                    for (int value : row.todo.toArray(new Integer[0])) {
                        if (check(rowIndex, columnIndex, value)) {
                            set(rowIndex, columnIndex, value);
                            if (solve(rowIndex, columnIndex + 1))
                                return true;
                            else
                                clear(rowIndex, columnIndex, value);
                        }
                    }
                    // nothing worked
                    return false;
                } else {
                    // cell is not empty
                    return solve(rowIndex, columnIndex + 1);
                }
            }
        }
    }

    public boolean solve() {
        return solve(0, 0);
    }
    
    public int getIterations() {
        return iteration;
    }
}


package sudoko;

import java.io.IOException;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.Collections;
import java.util.LinkedList;
import java.util.List;

public class BoardConstrainedCellFirst implements BoardI {

    static class Cell implements Comparable<Cell> {

        private int x;

        private int y;

        private boolean[] bbRow;

        private boolean[] bbColumn;

        private boolean[] bbSquare;

        private int nrOfOptions;

        private int value;

        public Cell(final int x, final int y) {

            this.x = x;
            this.y = y;

            bbRow = new boolean[9];
            bbColumn = new boolean[9];
            bbSquare = new boolean[9];

            for (int i = 0; i < 9; i++) {
                bbRow[i] = false;
                bbColumn[i] = false;
                bbSquare[i] = false;
            }

            nrOfOptions = 8;
            value = -1;
        }

        public int getNrOfOptions() {
            return nrOfOptions;
        }

        public int get() {
            if (value == -1) {
                if (nrOfOptions == 0) {
                    for (int i = 0; i < 9; i++) {
                        if (!bbRow[i] && !bbColumn[i] & !bbSquare[i])
                            return i;
                    }
                    throw new RuntimeException("error in algorithm");
                } else
                    return -nrOfOptions - 1;
            } else
                return value;
        }

        public int[] getOptions() {
            int[] options;
            options = new int[nrOfOptions + 1];
            int j = 0;
            for (int i = 0; i < 9; i++)
                if (!bbRow[i] && !bbColumn[i] & !bbSquare[i])
                    options[j++] = i;
            return options;
        }

        public void set(int value) {
            this.value = value;
        }

        public void unset() {
            this.value = -1;
        }
        
        public void removeFromSquare(int value) {
            bbSquare[value] = true;
            // nrOfOptions--; ??
        }
        
        public void removeFromColumn(int value) {
            bbColumn[value] = true;
            // nrOfOptions--; ??
        }

        public void removeFromRow(int value) {
            bbRow[value] = true;
            // nrOfOptions--; ??
        }

        public void activate(int value) {
            // nrOfOptions++; ??
        }

        public boolean check(int value) {
            return !bbRow[value] && !bbColumn[value] & !bbSquare[value];
        }

        public int compareTo(Cell other) {
            if (this.value != -1)
                return +1;
            if (other.value != -1)
                return -1;
            return this.nrOfOptions - other.nrOfOptions;
        }

        public String toString() {
            return x + "," + y + "=>" + (get() + 1) + "[" + nrOfOptions + "]";
        }
    }

    // state

    Cell[][] board = new Cell[9][9];

    List<Cell> cells = new ArrayList<Cell>(81);

    int iteration = 0;

    // constructors

    public BoardConstrainedCellFirst() {

        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                board[i][j] = new Cell(i, j);
                cells.add(board[i][j]);
            }
        }
    }

    public void init(final int[][] board) {
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                if (board[i][j] == 0)
                    continue;
                else
                    set(i, j, board[i][j] - 1);
            }
        }
    }

    // modifiers

    public void set(final int r, final int c, final int v) {

        board[r][c].set(v);

        // update row
        for (int i = 0; i < 9; i++)
            board[i][c].remove(v);

        // update column
        for (int i = 0; i < 9; i++)
            board[r][i].remove(v);

        // update square
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                board[r / 3 * 3 + i][c / 3 * 3 + j].remove(v);
            }
        }
    }

    public void unset(final int r, final int c, final int v) {

        board[r][c].unset();

        // update row
        for (int i = 0; i < 9; i++)
            board[i][c].activate(v);

        // update column
        for (int i = 0; i < 9; i++)
            board[r][i].activate(v);

        // update square
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                board[r / 3 * 3 + i][c / 3 * 3 + j].activate(v);
            }
        }
    }

    // readers

    public boolean check(final int r, final int c, final int v) {
        return board[r][c].check(v);
    }

    public void toWriter(final PrintWriter printWriter) {

        for (int i = 0; i < 9; i++) {
            printWriter.print("|");
            for (int j = 0; j < 9; j++) {
                final int value = board[i][j].get() + 1;
                if (value > 0)
                    printWriter.print(" " + value + "|");
                else
                    printWriter.print(value + "|");
            }
            printWriter.println();
        }
    }

    public boolean solve() throws IOException {

        iteration++;

        Collections.sort(cells);
        System.out.println(cells);
        // System.in.read();

        final Cell cell;
        cell = cells.get(0);

        if (cell.value != -1) {
            System.out.println("SOLUTION");
            return true;
        } else if (cell.nrOfOptions == 0) {
            set(cell.x, cell.y, cell.get());
            return solve();
        } else {
            for (int i : cell.getOptions()) {
                set(cell.x, cell.y, i);
                if (solve() == false) {
                    System.out.println("backtrack");
                    unset(cell.x, cell.y, i);
                } else
                    return true;
            }
        }

        return false;
    }

    public int getIterations() {
        return iteration;
    }

}
package sudoko;

import java.io.PrintWriter;
import java.util.SortedSet;
import java.util.TreeSet;

public class BoardMostConstrainedRowFirst implements BoardI {

    abstract static class Unit {

        SortedSet<Integer> todo = new TreeSet<Integer>();

        SortedSet<Integer> done = new TreeSet<Integer>();

        public Unit() {
            for (int i = 1; i < 10; i++) {
                todo.add(i);
            }
        }

    }

    static class Square extends Unit {

        private int[][] cells = new int[3][3];

        public void set(final int r, final int c, final int v) {

            if (!check(r, c, v))
                throw new RuntimeException("value already contained in unit or position taken: " + this);

            cells[r][c] = v;
            todo.remove(v);
            done.add(v);
        }

        public void clear(final int r, final int c, final int v) {

            cells[r][c] = 0;
            todo.add(v);
            done.remove(v);
        }

        public boolean check(final int r, final int c, final int v) {
            return cells[r][c] == 0 && todo.contains(v);
        }

        public void toWriter(final PrintWriter printWriter) {
            for (int[] row : cells) {
                printWriter.print("|");
                for (int cell : row) {
                    printWriter.print(cell + "|");
                }
                printWriter.println();
            }
        }
    }

    static class Row extends Unit {

        private int[] cells = new int[9];

        public void set(final int c, final int v) {

            if (!check(c, v))
                throw new RuntimeException("value already contained in unit or position taken: " + this);

            cells[c] = v;
            todo.remove(v);
            done.add(v);
        }

        public void clear(final int c, final int v) {

            cells[c] = 0;
            todo.add(v);
            done.remove(v);
        }

        public boolean check(final int c, final int v) {
            return cells[c] == 0 && todo.contains(v);
        }

        public void toWriter(final PrintWriter printWriter) {
            printWriter.print("|");
            for (int cell : cells) {
                printWriter.print(cell + "|");
            }
            printWriter.println();
        }
    }

    static class Column extends Row {
    }

    // state

    Square[][] asSquares = new Square[3][3];

    Row[] asRows = new Row[9];

    Column[] asColumns = new Column[9];

    int iteration = 0;

    // constructors

    public BoardMostConstrainedRowFirst() {

        Solver.out.println("BoardMostConstrainedRowFirst(): contructor");
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                asSquares[i][j] = new Square();
            }
        }
        for (int i = 0; i < 9; i++) {
            asRows[i] = new Row();
        }
        for (int i = 0; i < 9; i++) {
            asColumns[i] = new Column();
        }
    }

    public void init(final int[][] board) {
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                if (board[i][j] == 0)
                    continue;
                else if (check(i, j, board[i][j]))
                    set(i, j, board[i][j]);
            }
        }
    }

    // modifiers

    public void set(final int r, final int c, final int v) {
        asSquares[r / 3][c / 3].set(r % 3, c % 3, v);
        asRows[r].set(c, v);
        asColumns[c].set(r, v);
    }

    public void clear(final int r, final int c, final int v) {
        asSquares[r / 3][c / 3].clear(r % 3, c % 3, v);
        asRows[r].clear(c, v);
        asColumns[c].clear(r, v);
    }

    // readers

    public boolean check(final int r, final int c, final int v) {
        return asSquares[r / 3][c / 3].check(r % 3, c % 3, v) && asRows[r].check(c, v) && asColumns[c].check(r, v);
    }

    public void toWriter(final PrintWriter printWriter) {

        printWriter.println("AS ROWS");
        for (Row row : asRows) {
            row.toWriter(printWriter);
        }

        // printWriter.println("AS COLUMS");
        // for (Column column : asColumns) {
        // column.toWriter(printWriter);
        // }
        //
        // printWriter.println("AS SQUARES");
        // for (Square[] squares : asSquares) {
        // for (Square square : squares) {
        // square.toWriter(printWriter);
        // }
        // }
    }

    public boolean solve() {

        iteration++;

        final int rowIndex;
        rowIndex = getConstrainedRowIndex();
        if (rowIndex == -1) {
            Solver.out.println("SOLUTION FOUND");
            return true;
        }

        final Row row;
        row = asRows[rowIndex];

        // find empty cell
        int columnIndex = -1;
        for (int i = 0; i < 9; i++)
            if (row.cells[i] == 0) {
                columnIndex = i;
                break;
            }
        if (columnIndex == -1)
            throw new RuntimeException("error in algorithm");

        // put something in cell, recurse
        for (int value : row.todo.toArray(new Integer[0])) {
            if (check(rowIndex, columnIndex, value)) {
                set(rowIndex, columnIndex, value);
                if (solve())
                    return true;
                else
                    clear(rowIndex, columnIndex, value);
            }
        }
        // nothing worked
        return false;

    }

    private int getConstrainedRowIndex() {

        int foundIndex = -1;
        for (int candidateIndex = 0; candidateIndex < 9; candidateIndex++) {
            if (asRows[candidateIndex].todo.isEmpty())
                continue;
            if (foundIndex == -1)
                foundIndex = candidateIndex;
            else if (asRows[candidateIndex].todo.size() < asRows[foundIndex].todo.size())
                foundIndex = candidateIndex;
        }
        return foundIndex;
    }

    public int getIterations() {
        return iteration;
    }

}


package sudoko;

import java.io.IOException;
import java.io.PrintWriter;

public interface BoardI {

    public abstract void init(final int[][] board);

    public abstract void toWriter(final PrintWriter printWriter);

    public abstract boolean solve() throws IOException;
    
    public abstract int getIterations();

}


package sudoko;

import java.io.IOException;
import java.io.PrintWriter;

public class Solver {

    static final PrintWriter out = new PrintWriter(System.out);

    public static void main(String[] args) throws IOException {

        out.println("Creating BoardMostConstrainedRowFirst");
        BoardI board;
        board = new BoardConstrainedCellFirst();

        out.println("Setting Cells");

        // easy
        // board.init(new int[][] {
        // {
        // 7, 0, 0, 0, 2, 4, 1, 0, 0 }, {
        // 0, 3, 0, 0, 0, 6, 0, 0, 0 }, {
        // 9, 4, 0, 7, 0, 0, 6, 3, 2 }, {
        // 0, 2, 0, 0, 0, 0, 0, 1, 3 }, {
        // 0, 0, 9, 0, 0, 0, 4, 0, 0 }, {
        // 5, 1, 0, 0, 0, 0, 0, 9, 0 }, {
        // 6, 9, 1, 0, 0, 3, 0, 4, 7 }, {
        // 0, 0, 0, 5, 0, 0, 0, 2, 0 }, {
        // 0, 0, 5, 9, 4, 0, 0, 0, 8 }, });

        // evil
        board.init(new int[][] {
                {
                        7, 0, 0, 2, 9, 0, 0, 0, 0 }, {
                        0, 4, 0, 1, 0, 0, 7, 0, 5 }, {
                        8, 0, 0, 0, 0, 3, 0, 0, 0 }, {
                        0, 0, 0, 3, 0, 0, 1, 0, 0 }, {
                        0, 9, 0, 0, 1, 0, 0, 2, 0 }, {
                        0, 0, 7, 0, 0, 8, 0, 0, 0 }, {
                        0, 0, 0, 8, 0, 0, 0, 0, 2 }, {
                        9, 0, 6, 0, 0, 4, 0, 1, 0 }, {
                        0, 0, 0, 0, 3, 1, 0, 0, 8 } });

        out.flush();

        board.solve();

        out.println("Nr of iterations: " + board.getIterations());
        board.toWriter(out);

        out.flush();
    }
}

[Puzzle]

Ik heb nog maar even naar de oplossing van de prof gekeken.

Er zitten grote gebreken in waardoor kan het niet anders dan traag kan zijn:
- delingen.
- gesorteerde lijsten.
- exceptions.

Er zitten ook typfouten in. Zo gebruikt hij ergens een & in plaats van een &&. Het is mij niet bekend of dat in Java hetzelfde is als in C++. In C++ is & een bitwise AND en is && een logische AND.

Van de volgende klassen zou ik de broncode moeten hebben:
- java.util.SortedSet,
- java.util.TreeSet,
- java.util.ArrayList,
- java.util.Arrays,
- java.util.Collection,
- java.util.Collections,
- java.util.LinkedList,
- java.util.List.
Waar kan ik dat ergens vinden zonder al te veel te moeten downloaden? Dan kan ik dat compileren. Ik zou dat ook kunnen bekijken in C++ en meten, maar dan moeten we eerst overeenstemming vinden wat betreft de implementatie van bovengenoemde klassen.

Ik ben nu bezig met een verbetering van de versie die ik op 5/12/06 heb gepubliceerd.

In mijn versie van 168 µs had ik de statische variabelen van het type Negental van klasse Rooster gekopieerd naar member data. De ingevulde vakken schrap ik daar uit. Dat scheelt de helft van het werk. Dat was geïmplementerd met gelinkte lijsten, maar nu doe ik dat met geïndexeerde tabellen.

De mogelijke cijfers van een vak doe ik nu ook met geïndexeerde tabellen. Zo kan ik het enige cijfer vinden in 1 stap.

De lege vakken komen in een tabel van gelinkte lijsten, een lijst voor elk aantal mogelijke cijfers. Zo kan ik het lege vak met de minste keuze vinden in ten hoogste 9 stappen.

[Puzzle]

Van de volgende klassen zou ik de broncode moeten hebben:
- java.util.SortedSet,
- java.util.TreeSet,
- java.util.ArrayList,
- java.util.Arrays,
- java.util.Collection,
- java.util.Collections,
- java.util.LinkedList,
- java.util.List.
Waar kan ik dat ergens vinden zonder al te veel te moeten downloaden?

Gevonden op http://www.koders.com .

Je vindt er ook 163 resultaten als je zoekt naar "Sudoku".

[Puzzle]

Mijn C++-versie is af.

http://cliffhuylebroeck.50megs.com/Sudoku/Sudoku.html