Sudoku Solver & Generator

[bPmMaN]

hallo zusammen!

ich habe da ein paar kleine probleme beim erstellen eines sudokus. ich möchte gerne das ein sudoku erstellt wird, der nur EINE lösung hat und 3 schwierigkeitstufen hat. ich bekomme den backtracking-algo irgendwie nicht hin. ich habe mir schon mehrere seiten und foren angeguckt, aber ich bekomme es irgendwie nicht auf meinen source übertragen. wäre echt nett, wenn ihr mir weiterhelfen könntet.

hier ist der relevante code (fehlen tut eigentlich nur was bei CSolver

//*******************CSolver*********************
public class CSolver
{
    private CSolver()
    {}

    public static CGrid createPuzzle(  )
    {
    	//CODE FEHLT
    	//erstellen eines kompletten sudkokus
    }

    public static CGrid createStartGrid( CGrid solution, int difficulty )
    {
    	//CODE FEHLT
    	//legt die startfelder fest die am anfang zusehen sind, abhängig vom schwierigkeitsgrad
    }

    public static CGrid solve( CGrid gridToSolve )
    {
    	//CODE FEHLT
    	//das übergebene grid soll gelöst werden
    }
}


//******************CGrid***********************
public class CGrid
{
    private int m_data[][] = new int[9][9];
    public static final int EMPTY=-1;

    public CGrid()
    {
        reset();
    }

    public void reset()
    {
        for( int i=0;i<9;i++)
        {
            for( int j=0;j<9;j++)
            {
                m_data[i][j] = EMPTY;     
            }
        }
    }

    public CGrid Clone()
    {
        CGrid copy = new CGrid();
        for( int i=0;i<9;i++)
        {
            for( int j=0;j<9;j++)
            {
                copy.m_data[i][j] = m_data[i][j];
            }
        }
        return copy;
    }

    public int getValueAt(int row, int col)
    {
        return m_data[row][col];
    }


    public void setValueAt(int value, int row,int col)
    {
        m_data[row][col] = value;
    }


    public int[][] getGrid()
    {
        return m_data;
    }


    public boolean isNumberInRow(int value, int row, int col)
    {
        for (int i = 0; i < 9; i++) {
            if (i == col)continue;
            if (m_data[row][i] == value)
                return true;
        }
        return false;
    }

    public boolean isNumberInCol(int value, int row, int col)
    {
        for (int i = 0; i < 9; i++) {
            if (i == row)continue;
            if (m_data[i][col] == value)
                return true;
        }
        return false;
    }

    public boolean isNumberInBox(int value, int row, int col)
    {
        int boxNum = getBoxFromPos(row, col);
        for (int i = 0; i < 9; i++) {
            if (CPosition.boxes[boxNum][i].row == row &&
                CPosition.boxes[boxNum][i].col == col)continue;
            if (m_data[ CPosition.boxes[boxNum][i].row ][ CPosition.boxes[boxNum][i].col ] == value )
            {
                return true;
            }
        }
        return false;
    }

    public int getBoxFromPos(int row, int col)
    {
        int idxBoxRow = row / 3;
        int idxBoxCol = col / 3;
        return 3 * idxBoxRow + idxBoxCol;
    }

    public boolean isValidPos(int value, int row, int col)
    {
        if ( m_data[row][col] != EMPTY )return false;
        if (!isNumberInBox(value, row, col) &&
            !isNumberInCol(value, row, col) &&
            !isNumberInRow(value, row, col) )return true;
        return false;
    }

    public boolean isAllCorrect()
    {
        int boxValue, colValue, rowValue;
        for(int i=0;i<9;i++)
        {
            for(int j=0;j<9;j++)
            {
                boxValue = m_data[i][j];
                colValue = m_data[j][i];
                rowValue = m_data[i][j];

                if (boxValue != EMPTY)
                    if(isNumberInBox(boxValue, i, j) )
                    return false;
                if (colValue != EMPTY)
                    if(isNumberInCol(colValue, j, i) )
                    return false;
                if (rowValue != EMPTY)
                    if(isNumberInRow(rowValue, i, j))
                    return false;
            }
        }
        return true;
    }
}


//*****************CPosition************************
public class CPosition
{
    public int row;
    public int col;


Aufbau des Grids(der boxen)

box0-----------box1------------box2
box3-----------box4------------box5
box6-----------box7------------box8


    //welche box hat welche positionen
    public static final CPosition[][] boxes =
            {
 /*box0*/   {new CPosition(0,0),new CPosition(0,1),new CPosition(0,2),new CPosition(1,0),new CPosition(1,1),new CPosition(1,2),new CPosition(2,0),new CPosition(2,1),new CPosition(2,2)},
 /*box1*/   {new CPosition(0,3),new CPosition(0,4),new CPosition(0,5),new CPosition(1,3),new CPosition(1,4),new CPosition(1,5),new CPosition(2,3),new CPosition(2,4),new CPosition(2,5)},
 /*box2*/   {new CPosition(0,6),new CPosition(0,7),new CPosition(0,8),new CPosition(1,6),new CPosition(1,7),new CPosition(1,8),new CPosition(2,6),new CPosition(2,7),new CPosition(2,8)},
 /*box3*/   {new CPosition(3,0),new CPosition(3,1),new CPosition(3,2),new CPosition(4,0),new CPosition(4,1),new CPosition(4,2),new CPosition(5,0),new CPosition(5,1),new CPosition(5,2)},
 /*box4*/   {new CPosition(3,3),new CPosition(3,4),new CPosition(3,5),new CPosition(4,3),new CPosition(4,4),new CPosition(4,5),new CPosition(5,3),new CPosition(5,4),new CPosition(5,5)},
 /*box5*/   {new CPosition(3,6),new CPosition(3,7),new CPosition(3,8),new CPosition(4,6),new CPosition(4,7),new CPosition(4,8),new CPosition(5,6),new CPosition(5,7),new CPosition(5,8)},
 /*box6*/   {new CPosition(6,0),new CPosition(6,1),new CPosition(6,2),new CPosition(7,0),new CPosition(7,1),new CPosition(7,2),new CPosition(8,0),new CPosition(8,1),new CPosition(8,2)},
 /*box7*/   {new CPosition(6,3),new CPosition(6,4),new CPosition(6,5),new CPosition(7,3),new CPosition(7,4),new CPosition(7,5),new CPosition(8,3),new CPosition(8,4),new CPosition(8,5)},
 /*box8*/   {new CPosition(6,6),new CPosition(6,7),new CPosition(6,8),new CPosition(7,6),new CPosition(7,7),new CPosition(7,8),new CPosition(8,6),new CPosition(8,7),new CPosition(8,8)}
 };

    public CPosition()
    {
        row=-1;
        col=-1;
    }

    public CPosition( int row, int col )
    {
        this.row = row;
        this.col = col;
    }

    public String toString()
    {
        return getClass().getName()+" [Reihe="+row+" Spalte="+col+"]";
    }
}


//******************CStack*********************
public class CStack
{
    private Vector m_moves;

    public CStack()
    {
        m_moves = new Vector(81);
    }

    public CStack( int stackSize )
    {
        m_moves = new Vector(stackSize);
    }

    public void push(CMove move)
    {
        if(m_moves.size() == m_moves.capacity())
            m_moves.removeElementAt(0);
        m_moves.add(move);
    }

    public CMove pop()
    {
        CMove copy = (CMove)m_moves.lastElement();
        m_moves.remove(m_moves.lastElement());
        return copy;
    }

    public void removeAllElements()
    {
        m_moves.removeAllElements();
    }

    public Vector getAllMoves()
    {
        return m_moves;
    }

    public void deleteMove( CMove move)
    {
        m_moves.remove(move);
    }

    public int size()
    {
        return m_moves.size();
    }

    public CMove getElementAt( int index )
    {
        return (CMove)m_moves.elementAt( index );
    }

    public void deleteElementAt(int row, int col)
    {
        for(int i=0; i<m_moves.size();i++)
        {
            if( ((CMove)m_moves.elementAt(i)).getPosition().row == row && ((CMove)m_moves.elementAt(i)).getPosition().col == col )
            {
                m_moves.removeElementAt( i );
            }
        }
        return;

    }

    public CMove getLastMove()
    {
        return (CMove)m_moves.lastElement();
    }

    public String toString()
    {
        String output = "";
        for(int i=0;i<m_moves.size();i++)
        {
            output += ((CMove)m_moves.elementAt(i)).toString()+"\n";
        }
        return output;
    }
}


//*********************CMove***************************
public class CMove
{

    //position auf dem grid (reihe & spalte)
    private CPosition position = new CPosition();
    //der wert der an die position gesetzt werden soll
    public int value;
    //der wert der dem zug an der position war
    public int oldGridValue;

    public CMove()
    {
         value = -1;
         oldGridValue = -1;
         position.row = -1;
         position.col = -1;
    }

    public CMove(CPosition pos, int value, int oldValue )
    {
        position = pos;
        this.oldGridValue = oldValue;
        this.value = value;
    }

    public CMove( int value, int oldValue, int row, int col )
    {
        position.row = row;
        position.col = col;
        this.value = value;
        this.oldGridValue = oldValue;
    }

    public CPosition getPosition()
    {
        return position;
    }


    public String toString()
    {
        return getClass().getName()+" [Reihe="+position.row+" Spalte="+position.col+" Wert="+value+" Alter Wert="+oldGridValue+"]";
    }
}

ich hoffe es ist halbwegs verständlich und ihr habt alle daten die ihr braucht.

 

[bpmman]

kann mir pls einer helfen...pseudo-code oder ne hilfestellung würde es auch schon tun

 

[VdA]

334 Zeilen :shock:
Hilfe und das soll ich mir alles angucken und dann auch noch den Fehler Finden :bahnhof:
kannst du nich einfach das was nicht funzt hier draufstellen dann hilft dir auch jemand :!:
Vielleicht...

 

[bpmman]

da ist kein fehler drinne...hoffe ich ^^
mir fehlt nur der rekursive solver und da wollte ich den code nur mitbeilegen damit ihr wisst, wie der code bei mir aussieht. das setzen und so bekomme ich auch alles hin nur dann wieder das löschen von den feldern bis er den richtigen hat verstehe ich nicht so ganz. also wenn ein zug ungültig war lösche ich ihn aber das bringt ja nix, nur den letzten zu löschen...ein pseudo-code mit meinen funktionen oder noch fehlenden methoden wäre auch ok

 

[Kraftzwerg]

Hallo bpmman,

hier ist mein bescheidenen Java Sudoku Solver:

public class SudokuSolver
{
private static final boolean IS_FIND_ONLY_FIRST_SOLUTION_ENABLED = false;
private static final int EMPTY = 0;
private static final int REGION_DIM = 3;
private static final int GRID_DIM = REGION_DIM * REGION_DIM;

private static long solutionCnt;
private static long visitCnt;
private static long solvingDuration;

private static int[][] sudokuGrid =
{
{0, 2, 0, 0, 0, 0, 9, 0, 0},
{0, 0, 0, 7, 5, 0, 0, 0, 6},
{0, 0, 6, 0, 0, 0, 0, 7, 0},

{1, 0, 0, 8, 0, 4, 0, 0, 2},
{0, 0, 3, 0, 0, 0, 1, 0, 0},
{2, 0, 0, 1, 0, 9, 0, 0, 4},

{0, 1, 0, 0, 0, 0, 7, 0, 0},
{4, 0, 0, 0, 6, 1, 0, 0, 0},
{0, 0, 8, 0, 0, 0, 0, 3, 0}
};

private static void setCellValue(int x, int y, int value)
{
sudokuGrid[y][x] = value;
}

private static int getCellValue(int x, int y)
{
return sudokuGrid[y][x];
}

private static boolean isEmptyCell(int x, int y)
{
return (sudokuGrid[y][x] == EMPTY);
}

private static boolean isValidCell(int x, int y)
{
int value = getCellValue(x, y);

// (1) Check if value is unique in column x
for (int j = 0; j < GRID_DIM; j++)
if (j != y)
if (getCellValue(x, j) == value)
return false; // NOT unique => NOT valid

// (2) Check if value is unique in row y
for (int i = 0; i < GRID_DIM; i++)
if (i != x)
if (getCellValue(i, y) == value)
return false; // NOT unique => NOT valid

// (3) Check if value is unique in the region of x, y
int xOrigin = x - x % REGION_DIM;
int yOrigin = y - y % REGION_DIM;
for (int j = yOrigin; j < yOrigin + REGION_DIM; j++)
if (j != y) // cause row y was already processed in (2)
for (int i = xOrigin; i < xOrigin + REGION_DIM; i++)
if (i != x) // cause column x was already processed in (1)
if (getCellValue(i, j) == value)
return false; // NOT unique => NOT valid

return true;
}

private static void handleSolution()
{
solutionCnt++;
showGrid("Solution " + solutionCnt + ":");
}

private static void showGrid(String header)
{
System.out.println(header + "\n");
for (int y = 0; y < GRID_DIM; y++)
{
for (int x = 0; x < GRID_DIM; x++)
System.out.print(
getCellValue(x, y) +
((x % REGION_DIM + 1 < REGION_DIM) ? " " : " "));

System.out.print(((y % REGION_DIM + 1 < REGION_DIM) ? "\n" : "\n\n"));
}
}

private static boolean evaluate(int x, int y)
{
if (!isValidCell(x, y))
return false;

if (x + 1 < GRID_DIM)
return solve(x + 1, y);

if (y + 1 < GRID_DIM)
return solve(0, y + 1);

handleSolution();
return true;
}

private static boolean solve(int x, int y)
{
visitCnt++;
if (!isEmptyCell(x, y))
return evaluate(x, y); // Recursive call for the presetting values

for (int value = 1; value <= GRID_DIM; value++)
{
setCellValue(x, y, value);

if (evaluate(x, y))
if (IS_FIND_ONLY_FIRST_SOLUTION_ENABLED)
return true;

setCellValue(x, y, EMPTY);
}

return false;
}

public static void solve()
{
solvingDuration = System.currentTimeMillis();
solutionCnt = 0;
visitCnt = 0;
solve(0, 0);
solvingDuration = System.currentTimeMillis() - solvingDuration;
System.out.println(solutionCnt + " solution(s) found and");
System.out.println(visitCnt + " visit(s) performed");
System.out.println("in " + solvingDuration + " millisecond(s).");
}

public static void main(String[] args)
{
showGrid("Sudoku Puzzle:");
solve();
}
}

 

[bpmman]

thx...den will ich mir mal angucken und sehen ob ich den nicht bei mir eingebaut bekomme

 

[Kraftzwerg]

Hello again:

hier noch eine 2. Version des Solvers, der ohne boolsche Rückgabewerte der rekursiven 'solve' Methode auskommt. (Sorry, da ich nur Gast bin, poste ich über den rudimentären Quick Reply, was leider zur Folge hat, dass der Source-Code etwas eigenwillig (soll heißen scheiße) formatiert wird ;-)):

public class SudokuSolver
{
private static final boolean IS_FIND_ONLY_FIRST_SOLUTION_ENABLED = true;
private static final int EMPTY = 0;
private static final int REGION_DIM = 3;
private static final int GRID_DIM = REGION_DIM * REGION_DIM;

private static long solutionCnt;
private static long visitCnt;
private static long solvingDuration;

private static int[][] sudokuGrid =
{
{0, 2, 0, 0, 0, 0, 9, 0, 0},
{0, 0, 0, 7, 5, 0, 0, 0, 6},
{0, 0, 6, 0, 0, 0, 0, 7, 0},

{1, 0, 0, 8, 0, 4, 0, 0, 2},
{0, 0, 3, 0, 0, 0, 1, 0, 0},
{2, 0, 0, 1, 0, 9, 0, 0, 4},

{0, 1, 0, 0, 0, 0, 7, 0, 0},
{4, 0, 0, 0, 6, 1, 0, 0, 0},
{0, 0, 8, 0, 0, 0, 0, 3, 0}
};

private static void setCellValue(int x, int y, int value)
{
sudokuGrid[y][x] = value;
}

private static int getCellValue(int x, int y)
{
return sudokuGrid[y][x];
}

private static boolean isEmptyCell(int x, int y)
{
return (sudokuGrid[y][x] == EMPTY);
}

private static boolean isValidCell(int x, int y)
{
int value = getCellValue(x, y);

// (1) Check if value is unique in column x
for (int j = 0; j < GRID_DIM; j++)
if (j != y)
if (getCellValue(x, j) == value)
return false; // NOT unique => NOT valid

// (2) Check if value is unique in row y
for (int i = 0; i < GRID_DIM; i++)
if (i != x)
if (getCellValue(i, y) == value)
return false; // NOT unique => NOT valid

// (3) Check if value is unique in the region of x, y
int xOrigin = x - x % REGION_DIM;
int yOrigin = y - y % REGION_DIM;
for (int j = yOrigin; j < yOrigin + REGION_DIM; j++)
if (j != y) // cause row y was already processed in (2)
for (int i = xOrigin; i < xOrigin + REGION_DIM; i++)
if (i != x) // cause column x was already processed in (1)
if (getCellValue(i, j) == value)
return false; // NOT unique => NOT valid

return true;
}

private static void showGrid(String header)
{
System.out.println(header + "\n");
for (int y = 0; y < GRID_DIM; y++)
{
for (int x = 0; x < GRID_DIM; x++)
System.out.print(
getCellValue(x, y) +
((x % REGION_DIM + 1 < REGION_DIM) ? " " : " "));

System.out.print(((y % REGION_DIM + 1 < REGION_DIM) ? "\n" : "\n\n"));
}
}

private static void evaluate(int x, int y)
{
if (isValidCell(x, y))
if (x + 1 < GRID_DIM)
solve(x + 1, y);
else if (y + 1 < GRID_DIM)
solve(0, y + 1);
else
{
solutionCnt++;
showGrid("Solution " + solutionCnt + ":");
}
}

private static void solve(int x, int y)
{
visitCnt++;
if (isEmptyCell(x, y))
for (int value = 1; value <= GRID_DIM; value++)
{
setCellValue(x, y, value);

evaluate(x, y);
if (IS_FIND_ONLY_FIRST_SOLUTION_ENABLED && (solutionCnt > 0))
return;

setCellValue(x, y, EMPTY);
}
else
evaluate(x, y); // Recursive call for the presetting values
}

public static void solve()
{
solvingDuration = System.currentTimeMillis();
solutionCnt = 0;
visitCnt = 0;
solve(0, 0);
solvingDuration = System.currentTimeMillis() - solvingDuration;
System.out.println(solutionCnt + " solution(s) found and");
System.out.println(visitCnt + " visit(s) performed");
System.out.println("in " + solvingDuration + " millisecond(s).");
}

public static void main(String[] args)
{
showGrid("Sudoku Puzzle:");
solve();
}
}

 

[bpmman]

wenn man andere werte eingibt für das grid dann funzt es nicht mehr kann das sein?
da ich ja die werte ändern muss damit man verschiedene sudokus bekommt, wenn
man sie erstellt. (denn ich brauche ja ein creator)

 

[Gast]

hm... ich habe das ganze mal "Objektorientierter" gelöst...
So spart man sich einiges an Code. Ich habe Zahlen in verschiedene logische Blöcke(Reihen,Spalten und Quadrate) zusammengefasst und wenn eine Zahl in dem Block eingetragen wurde aus der Liste mit den noch vorhandenen möglichen zahlen entfernt, wenn nur noch eine Zahl in der Liste vorhanden ist wird die nächste Zahl gesetzt. Für das ganze bot sich dann natürlich rekursion an...

 

[bpmman]

hast du denn mal pls den code? oder noch besser wäre es wenn es zu dem code passen würde den kraftzwerg gepostet hat denn das funzt bei mir jetzt.

 

[raynic35]

Hallo,
ich hatte das Problem auch schon mal.
SudokuCheck überprüft dabei, ob der jeweilige Eintrag in das Feld möglich ist, aber das ist nicht so schwer umzusetzen. Lass dich von "solvedSudoku" nicht verwirren, dass ist nur eine Hashtable mit 81 Feldern.

Hier ist meine Lösung:

import java.util.Hashtable;

public class SudokuSolverComplete implements {
	
	private Hashtable<Integer,SudokuField> solvedSudoku;
	private SudokuCheck sudokuChecker;
	
	/**
	 * Kopiert das aktuelle Sudoku und erstellt eine Instanz von SudokuCheck.
	 */
	public SudokuSolverComplete(){
		this.solvedSudoku = Sudoku.getSudokuObject().getSudoku();
		this.sudokuChecker = new SudokuCheck();
		this.resetSudoku();
		this.solve(0);		
	}
	
	/**
	 * Das aktuelle Sudoku komplett gelöst und in einem Array gespeichert.
	 * 
	 * @param field
	 *            Die Nummer des Feldes, das aktuell berechnet wird.
	 * @return true wenn der Lösungsweg möglich, false wenn nicht
	 */
	public boolean solve(int field){
		if(field == 81)
		{
			return true;
		}
	
		if(!this.solvedSudoku.get(field).getChangeable())
		{
			if(solve(field+1))
			{
				return true;
			}
		}
		else
		{
			for(int i = 1;  i <= 9 + 1; i++)
			{	
				if(this.sudokuChecker.checkSudoku(i,this.solvedSudoku.get(field)) == false){
					this.solvedSudoku.get(field).setValue(i);

					if(solve(field+1)){
						return true;
					}
					this.solvedSudoku.get(field).setValue(0);
				}
			}
		}
		return false;
	}
}

Gruss Ray

 

[bpmman]

danke schön für dein post, aber wenn ich das richtig sehen ist das nur der solver oder? ich bräuchte aber ein generator, der mir ein sudoku mit nur EINER lösung berechnet