Sudoku (Rekursion)
Ein Sudokuspiel besteht aus 9x9, also 81 Feldern im Quadrat angeordnet. Darin sind die neun 3x3 Kästchen ausgezeichnet (fett umrandet). In einigen dieser 81 Feldern sind Ziffern von 1 bis 9 vorgegeben. Gesucht sind die Ziffern von 1 bis 9 in allen übrigen Kästchen. Am Ende soll jede der neun Ziffern in jeder Zeile, jeder Spalte und in jedem der 3x3 Kästchen genau einmal vorkommen.
Ein möglicher rekursiver Algorithmus könnte wie folgt aussehen:
// Die Datenstruktur Sudoku ist in der Lage,
// ein ungelöstes oder auch ein bereits gelöstes
// Sudoku-Feld zu speichern:
loeseSudoku(s: Sudoku)
{
// Abbruch:
if(unloesbar(s)) then return;
if(geloest (s)) then printLoesung(s); exit();
// Rekursionsschritt:
zeile := sucheErsteZeileMitLeereintraegen(s);
unbenutzteZahl :=
suche eine Zahl, die auf "zeile" nicht vorkommt
Feld (Array) von sudokus :=
Für jeden Leereintrag in "zeile" erzeuge ein neues
Sudoku mit "unbenutzteZahl" an dieser Stelle.
Für alle (iterativ) Sudokus im eben erzeugten Feld:
loeseSudoku(sudokus[i])
}
1 Kommentare
7 Lösung(en)
// Loesung: Daniel Huber / Credit Suisse / Santis Training
//////////////////////////////////////////////////////////
public class Main {
public static void main(String[] args) {
new SudokuLoeser(new Sudoku());
}
}
//////////////////////////////////////////////////////////
public class SudokuLoeser {
public SudokuLoeser(Sudoku s) {
System.out.println("löse jetzt..");
int durchgang = 1;
loeseSudoku(s, durchgang);
}
public void loeseSudoku(Sudoku s, int durchgang) {
System.out.println("Durchgang:"+durchgang);
if(inkonsistent(s)) {
System.out.println("Inkonsistent");
return;
}
if(solved(s)) {
System.out.println("Jupii");
System.out.println(s);
Ausgabe a = new Ausgabe(s);
}
int nullZeile = ersteNullZeile(s);
int anzahlNullern = getAnzahlNullern(s, nullZeile);
int kleinsteZahl = kleinsteNichtverwendeteZahl(s, nullZeile);
Sudoku[] neueSudokus = new Sudoku[anzahlNullern];
macheNeueSudokus(s, neueSudokus, nullZeile, kleinsteZahl);
System.out.println("neue Berechnung..");
for(Sudoku ns : neueSudokus) {
loeseSudoku(ns, durchgang+1);
}
}
private void macheNeueSudokus(Sudoku s, Sudoku[] neueSudokus, int nullZeile, int kleinsteZahl) {
int sudokuNummer = 0;
for (int i = 0; i < 9; i++) {
if(s.struktur[nullZeile][i] == 0) {
neueSudokus[sudokuNummer] = kopiereSudoku(s);
neueSudokus[sudokuNummer].struktur[nullZeile][i] = kleinsteZahl;
sudokuNummer++;
}
}
}
private Sudoku kopiereSudoku(Sudoku s) {
Sudoku ns = new Sudoku();
for(int i=0; i<9; i++) {
for(int ii=0; ii<9; ii++) {
ns.struktur[i][ii] = s.struktur[i][ii];
}
}
return ns;
}
private int getAnzahlNullern(Sudoku s, int nullZeile) {
int cnt = 0;
for(int i=1; i<10; i++)
if(s.struktur[nullZeile][i-1] == 0) cnt++;
return cnt;
}
private int kleinsteNichtverwendeteZahl(Sudoku s, int nullZeile) {
int[] counter = {0,0,0,0,0,0,0,0,0};
int cnt = 0;
for(int z=1; z<10; z++) {
for(int i=0; i<9; i++)
if(s.struktur[nullZeile][i] == z) counter[z-1] = 1;
}
for(int i1=0; i1<9; i1++) {
if(counter[i1] == 0) {
cnt=i1+1;
break;
}
}
return cnt;
}
private int ersteNullZeile(Sudoku s) {
for(int i=0; i<9; i++)
for(int j=0; j<9; j++)
if(s.struktur[i][j] == 0) return i;
return 0;
}
private boolean inkonsistent(Sudoku s) {
for(int i=0; i<9; i++) {
if(inkonsistenteZeile(s, i)) {
return true;
}
if(inkonsistenteSpalte(s, i)) {
return true;
}
}
if(inkonsistentesQuadrat(s)) return true;
return false;
}
private boolean inkonsistentesQuadrat(Sudoku s) {
return checkQuadrat(s, 0, 0) || checkQuadrat(s, 0, 3) || checkQuadrat(s, 0, 6)
|| checkQuadrat(s, 3, 0) || checkQuadrat(s, 3, 3)
|| checkQuadrat(s, 3, 6) || checkQuadrat(s, 6, 0)
|| checkQuadrat(s, 6, 3) || checkQuadrat(s, 6, 6);
}
private boolean inkonsistenteZeile(Sudoku s, int y) {
System.out.println("Zeile");
int counter = 0;
for(int z=1; z<10; z++) {
for(int j=0; j<9; j++) {
if(s.struktur[j][y] == z) counter++;
// System.out.println("(y: "+y+"), (x: "+j+"), (c: "+counter+"), ZAHL:"+z);
}
if(counter <= 1) counter = 0;
else return true;
}
return false;
}
private boolean inkonsistenteSpalte(Sudoku s, int x) {
System.out.println("Spalte");
int counter = 0;
for(int z=1; z<10; z++) {
for(int j=0; j<9; j++) {
if(s.struktur[x][j] == z) counter++;
// System.out.println("(y: "+j+"), (x: "+x+"), (c: "+counter+"), ZAHL:"+z);
}
if(counter <= 1) counter = 0;
else return true;
}
return false;
}
private boolean checkQuadrat(Sudoku s, int a, int b) {
int c = a + 3;
int d = b + 3;
for (int x = 1; x < 10; x++) {
int count = 0;
for (int i = a; i < c; i++) {
for (int j = b; j < d; j++)
if (s.struktur[i][j] == x)
count++;
}
if (count > 1)
return true;
}
return false;
}
private boolean solved(Sudoku s) {
for (int x=0; x<9; x++) {
for (int y=0; y<9; y++) {
if(s.struktur[x][y] == 0) return false;
}
}
return true;
}
}
//////////////////////////////////////////////////////////
public class Sudoku {
// inhalte: 0 = leer; 1-9 = zahl;
int[][] struktur = {
{ 0,6,5, 0,0,0, 3,9,0 },
{ 3,0,0, 9,0,7, 0,0,6 },
{ 7,0,4, 0,0,0, 8,0,1 },
{ 0,3,0, 0,7,0, 0,2,0 },
{ 0,0,0, 5,0,8, 0,0,0 },
{ 0,5,0, 0,2,0, 0,8,0 },
{ 6,0,2, 0,0,0, 7,0,9 },
{ 5,0,0, 1,0,9, 0,0,2 },
{ 0,4,1, 0,0,0, 5,3,0 }
};
/*int[][] struktur = {
{ 2,6,5, 8,1,4, 3,9,7 },
{ 3,1,8, 9,5,7, 2,4,6 },
{ 7,9,4, 2,3,6, 8,5,1 },
{ 8,3,9, 0,7,1, 6,2,5 },
{ 4,2,6, 5,9,8, 1,7,3 },
{ 1,5,7, 6,2,3, 9,8,4 },
{ 6,0,2, 3,4,5, 0,0,9 },
{ 5,7,3, 1,8,9, 4,6,2 },
{ 9,4,1, 7,6,2, 5,3,8 }
};*/
public String toString() {
String ret = "+-------------------------------------------------+\n";
int cnt = 1, cntV = 1;
for(int[] i : struktur) {
for(int ii : i) {
ret += "Š "+ii+" Š";
ret += cnt==3||cnt==6?" ":cnt==9?"\n":"";
cnt = cnt==9?cnt=1:cnt+1;
}
ret += cntV==3||cntV==6||cntV==9?"+-------------------------------------------------+\n":"";
cntV++;
}
return ret;
}
}
//////////////////////////////////////////////////////////
import java.awt.Color;
import java.awt.GridLayout;
import javax.swing.*;
public class Ausgabe extends JFrame {
private static final long serialVersionUID = 1L;
JLabel[][] lbl = new JLabel[9][9];
JPanel pnl = new JPanel(new GridLayout(9,9));
JPanel[][] pnl2 = new JPanel[3][3];
public Ausgabe(Sudoku s) {
initLbls(s);
getContentPane().add(pnl);
setDefaultCloseOperation(EXIT_ON_CLOSE);
setSize(380,380);
setVisible(true);
}
private void initLbls(Sudoku s) {
for(int i=0; i<9; i++) {
for(int ii=0; ii<9; ii++) {
lbl[i][ii] = new JLabel();
lbl[i][ii].setText(""+s.struktur[i][ii]);
lbl[i][ii].setSize(40,40);
lbl[i][ii].setBorder(BorderFactory.createLineBorder(Color.black));
pnl.add(lbl[i][ii]);
}
}
}
}
/**
* sudoku (JavaScript)
* Autor: phi@gressly.ch
* Kurs: Siemens Modul 307: April 2010
*/
function startSudoku() {
var sudoku = initialisiereSudoku();
loeseSudoku(sudoku);
}
function initialisiereSudoku() {
sudoku = new Array(9); // 9 Spalten
sudoku[0] = new Array(0, 8, 1, 0, 0, 0, 7, 3, 0);
sudoku[1] = new Array(9, 0, 0, 2, 0, 8, 0, 0, 4);
sudoku[2] = new Array(6, 0, 0, 0, 0, 0, 0, 0, 8);
sudoku[3] = new Array(0, 3, 0, 7, 0, 1, 0, 2, 0);
sudoku[4] = new Array(0, 0, 0, 0, 0, 0, 0, 0, 0);
sudoku[5] = new Array(0, 9, 0, 5, 0, 2, 0, 1, 0);
sudoku[6] = new Array(8, 0, 0, 0, 0, 0, 0, 0, 7);
sudoku[7] = new Array(7, 0, 0, 3, 0, 6, 0, 0, 1);
sudoku[8] = new Array(0, 4, 5, 0, 0, 0, 6, 9, 0);
return sudoku;
}
function loeseSudoku(sudoku) {
if(istRegelVerletzt(sudoku)) {
return;
}
if(istVoll(sudoku)) {
ausgabe(sudoku);
return;
}
loeseRekursiv(sudoku);
}
/**
* Erstelle neue einfachere Sudokus und löse diese mit obigem
* "Algorithmus".
*/
function loeseRekursiv(sudoku) {
var zeile = findeErsteZeileMitLeereintraegen(sudoku);
var ziffer = findeKleinsteUnbenutzteZifferInZeile(sudoku, zeile);
var sudokus = erzeugeNeueSudokus(sudoku, zeile, ziffer);
for(var i = 0; i < sudokus.length; i++) {
loeseSudoku(sudokus[i]);
}
}
/**
* Ist eine der drei Sudoku-Reglen (zeile, spalte, block)
* verletzt?
*/
function istRegelVerletzt(sudoku) {
return istEineZeileVerletzt(sudoku) ||
istEineSpalteVerletzt(sudoku) ||
istEinBlockVerletzt(sudoku);
}
function istEineZeileVerletzt(sudoku) {
for(var zeile = 0; zeile < 9; zeile++) {
if(istZeileVerletzt(sudoku, zeile)) {
return true;
}
}
return false;
}
function istEineSpalteVerletzt(sudoku) {
for(var spalte = 0; spalte < 9; spalte ++) {
if(istSpalteVerletzt(sudoku, spalte)) {
return true;
}
}
return false;
}
function istEinBlockVerletzt(sudoku) {
for(var xb = 0; xb <= 6; xb = xb + 3) {
for(var yb = 0; yb <= 6; yb = yb + 3) {
if(istBlockVerletzt(sudoku, xb, yb)) {
return true;
}
}
}
return false;
}
function istZeileVerletzt(sudoku, zeile) {
for(ziffer = 1; ziffer <= 9; ziffer ++) {
if(vorkommenEinerZifferInZeile(sudoku, ziffer, zeile) > 1) {
return true;
}
}
return false;
}
/**
* Wie oft kommt "ziffer" auf "zeile" vor?
*/
function vorkommenEinerZifferInZeile(sudoku, ziffer, zeile) {
var vk = 0;
for(var spalte = 0; spalte <= 8; spalte ++) {
if(sudoku[spalte][zeile] == ziffer) {
vk = vk + 1;
}
}
return vk;
}
function istSpalteVerletzt(sudoku, spalte) {
for(ziffer = 1; ziffer <= 9; ziffer ++) {
if(vorkommenEinerZifferInSpalte(sudoku, ziffer, spalte) > 1) {
return true;
}
}
return false;
}
/**
* Wie oft kommt "ziffer" in "spalte" vor?
*/
function vorkommenEinerZifferInSpalte(sudoku, ziffer, spalte) {
var vk = 0;
for(var zeile = 0; zeile <= 8; zeile ++) {
if(sudoku[spalte][zeile] == ziffer) {
vk = vk + 1;
}
}
return vk;
}
function istBlockVerletzt(sudoku, xb, yb) {
for(var ziffer = 1; ziffer <= 9; ziffer ++) {
if(vorkommenInBlock(sudoku, xb, yb, ziffer) > 1) {
return true;
}
}
return false;
}
/**
* Wie oft kommt "ziffer" im 3x3 Kästchen ab (xb, yb) vor?
*/
function vorkommenInBlock(sudoku, xb, yb, ziffer) {
var vk = 0;
for(var x = xb; x < xb + 3; x ++) {
for(var y = yb; y < yb + 3; y++) {
if(ziffer == sudoku[y][x]) {
vk = vk + 1;
}
}
}
return vk;
}
/**
* Sind alle Felder besetzt?
*/
function istVoll(sudoku) {
var total = 0;
for(var zeile = 0; zeile <= 8; zeile ++) {
for(var spalte = 0; spalte <= 8; spalte ++) {
if(sudoku[spalte][zeile] > 0) {
total = total + 1;
}
}
}
return 81 == total;
}
function ausgabe(sudoku) {
var para = document.getElementById("ausgabe");
var ausgabeString = "";
for(var zeile = 0; zeile <= 8; zeile ++) {
for(var spalte = 0; spalte <= 7; spalte ++) {
ausgabeString += sudoku[spalte][zeile] + " | ";
if(0 == (spalte + 1) % 3) {
ausgabeString += "| ";
}
}
ausgabeString += sudoku[8][zeile] + "<br />";
if(0 == (zeile + 1) % 3) {
ausgabeString += "---------------------------------------------<br />";
}
}
para.innerHTML = ausgabeString;
}
/**
* Suche die oberste Zeile, die noch nicht voll besetzt ist.
*/
function findeErsteZeileMitLeereintraegen(sudoku) {
for(var zeile = 0; zeile <= 8; zeile++) {
if(hatLeerEintragAufZeile(sudoku, zeile)) {
return zeile;
}
}
}
function hatLeerEintragAufZeile(sudoku, zeile) {
for(var spalte = 0; spalte <= 8; spalte ++) {
if(0 == sudoku[spalte][zeile]) {
return true;
}
}
}
function findeKleinsteUnbenutzteZifferInZeile(sudoku, zeile) {
for(ziffer = 1; ziffer <= 9; ziffer++) {
if(!kommtZifferAufZeileVor(sudoku, ziffer, zeile)) {
return ziffer;
}
}
}
function kommtZifferAufZeileVor(sudoku, ziffer, zeile) {
for(var spalte = 0; spalte <= 8; spalte ++) {
if(ziffer == sudoku[<script type="text/javascript" src="http://edit.programmieraufgaben.ch/js/tiny_mce/themes/advanced/langs/de.js"></script><script type="text/javascript" src="http://edit.programmieraufgaben.ch/js/tiny_mce/plugins/syntaxhighlight/langs/de.js"></script>spalte][zeile]) {
return true;
}
}
return false;
}
/**
* Erzeuge für jedes freie Feld auf "zeile" ein neues
* Sudoku mit "ziffer" anstelle des freien Feldes.
*/
function erzeugeNeueSudokus(sudoku, zeile, ziffer) {
var plaetze = findeAnzahlFreiePlaetze(sudoku, zeile);
var sudokus = new Array(plaetze);
var pos = 0;
for(var spalte = 0; spalte <= 8; spalte ++) {
if(0 == sudoku[spalte][zeile]) {
sudokus[pos++] = neuesSudoku(sudoku, zeile, spalte, ziffer);
}
}
return sudokus;
}
/**
* Wie viele Felder sind auf "zeile" noch frei?
*/
function findeAnzahlFreiePlaetze(sudoku, zeile) {
var anz = 0;
for(var spalte = 0; spalte <= 8; spalte++) {
if(0 == sudoku[spalte][zeile]) {
anz++;
}
}
return anz;
}
/**
* Erzeuge aus "sudoku" ein neues (Kopie), das an der Stelle
* [spalte][zeile] die "ziffer" eingefüllt hat.
* Alle anderen Werte werden einfach aus "sudoku" kopiert.
*/
function neuesSudoku(sudoku, zeile, spalte, ziffer) {
var neuesSudoku = new Array(9);
for(var sp = 0; sp <= 8; sp ++) {
neuesSudoku[sp] = new Array(9);
for(var ze = 0; ze <= 8; ze ++) {
neuesSudoku[sp][ze] = sudoku[sp][ze];
}
}
neuesSudoku[spalte][zeile] = ziffer;
return neuesSudoku;
}
// Loese Sudoku durch Kombination von einfachem direkten Loeser und Back-Track Prinzip
import java.io.BufferedReader;
import java.io.File;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
import java.util.StringTokenizer;
import java.util. ArrayDeque;
public class SudokuV2{
private static final int BOX_SIZE = 3;
private static final int SIZE = BOX_SIZE * BOX_SIZE;
private static int[][] matrix = new int[SIZE][SIZE];
private static boolean[][] row = new boolean [SIZE][SIZE];
private static boolean[][] col = new boolean[SIZE][SIZE];
private static boolean[][] box = new boolean[SIZE][SIZE];
private static ArrayDeque <Entry> q= new ArrayDeque<Entry>();
private static int rec_tries=0;
/**
* Liest die Eingabedatei, wobei ein korrekter Aufbau vorausgesetzt wird.
* Fuellt dabei die Sudoku-Matrix mit den spezifizierten Eingabewerten.
*
* @param file
* Textdatei mit Ziffertripeln
*
*/
private static void parseInput(File file) {
try {
BufferedReader reader = new BufferedReader(new FileReader(file));
String sudokuLine = new String(reader.readLine());
StringTokenizer tokenizer = new StringTokenizer(sudokuLine, " ");
while (tokenizer.hasMoreTokens()) {
String token = tokenizer.nextToken();
try {
int i = Integer.parseInt(token.substring(0,1));
int j = Integer.parseInt(token.substring(1,2));
int val = Integer.parseInt(token.substring(2,3));
matrix[i][j] = val;
}
catch (NumberFormatException n) {
return;
}
} // end while
}
catch (FileNotFoundException e) {
System.out.println("ERROR: File not found");
}
catch (IOException e) {
System.out.println("ERROR: IOException in parseSudoku(...)");
}
} // end parseInput
/**
* Ueberprueft ob die Sudoku-Randbedingungen fuer das Vorkommen von Ziffern
* erfuellt sind. Fuellt gleichzeitig die Hilfsdatenstrukturen
* row, col und box
* @return true, falls matrix ein gueltiges Sudoku enthaelt, sonst false.
*/
private static boolean verifySudoku() {
int value;
for (int val=1; val<= SIZE; val++){
for (int i=0; i<SIZE; i++){
for (int j=0; j<SIZE; j++){
markValue(i,j,val,false);
}
}
}
for (int i = 0; i < SIZE; i++) {
for (int j = 0; j <SIZE; j++) {
value = matrix[i][j];
if (value != 0) {
if (valueNotSet(i,j,value))
markValue(i,j,value,true);
else
return false;
}
}
}
return true;
} // end verifySudoku
/**
* Prueft ob der Wert val bereits vorkommt
*
*/
private static boolean valueNotSet(int i, int j, int val) {
return (row[i][val-1]==false) &&
(col[j][val-1]==false) &&
(box[i/BOX_SIZE * BOX_SIZE + j/BOX_SIZE][val-1] == false);
} // end valueNotSet
/**
* Markiert den Wert val in den Hilfsdatenstrukturen
*/
private static void markValue(int i, int j, int val, boolean state) {
row[i][val-1] = state;
col[j][val-1] = state;
box[i/BOX_SIZE * BOX_SIZE + j/BOX_SIZE][val-1] = state;
} // end markValue
/**
* Setzt einen Matrixwert
*/
private static void setValue(int i, int j, int val) {
matrix[i][j]=val;
} // end setValue
/**
* Loest Sudoku
*
* @return true, falls das Sudoku geloest wurde, sonst false
*/
private static boolean solveSudoku() {
Entry e;
int i,j;
int count; // zaehler fuer m?gliche Eintraege
int val_to_use=0;
int max_iter;
int iter=0;
boolean monitor=true;
System.out.println("Start mit direktem Loesen");
// Die zu setzenden Ziffern als Auftraege in Schlange setzen
for (i = 0; i < SIZE; i++) {
for (j = 0; j <SIZE; j++) {
if (matrix[i][j]==0) {
q.offer(new Entry(i,j));
}
}
}
if ( q.size() ==0) return true;
max_iter=q.size();
if (monitor){
System.out.println("Inhalt der Schlange:");
System.out.println("Zeile Spalte #Kand Wert");
}
while (!q.isEmpty()){
e=q.poll();
i=e.getRow();
j=e.getCol();
count=0;
// wir pruefen und zaehlen die moeglichen Werte
for (int val = 1; val <= SIZE; val++){
if (valueNotSet(i,j,val)){
count++; val_to_use=val;
}
}
if(monitor)System.out.print(" " + i + " " + j + " " + count);
if (count==1){ // nur 1 Zahl passt: nutze sie
if(monitor) System.out.print(" " + val_to_use);
setValue(i,j,val_to_use);
markValue(i,j,val_to_use,true);
}
else
q.offer(e); // wieder in Schlange aufnehmen, da mehrere Kandidaten
if(monitor) System.out.println();
iter++; // Abarbeitung der Elemente zaehlen
if (iter==max_iter){ // kompletter Durchgang durch Schlange erfolgt
if (max_iter==q.size()){ // kein Eintrag ist verschwunden
System.out.println("Wechsel in Backtrack-Modus");
e=q.poll();
return solveBacktrack(e.getRow(), e.getCol());
}
else
if (q.size() > 0){
if (monitor) System.out.println("Naechste Serie");
iter=0;
max_iter=q.size();
}
}
}
return true;
} // end solveSudoku
private static boolean solveBacktrack(int i, int j) {
int val;
Entry e;
rec_tries++;
for (val = 1; val <= SIZE; val++) {
if (valueNotSet(i,j,val)) {
setValue(i,j,val);
markValue(i,j,val,true);
if (!q.isEmpty()){
e=q.poll(); // naechsten Index aus Schlange holen
if (solveBacktrack(e.getRow(),e.getCol()))
return true;
else{
setValue(i,j,0);
markValue(i,j,val,false);
q.offerFirst(e); // zurueck in die Schlange
}
}
else return true;
}
}
return false;
} // end solveBacktrack
/**
* Ausdruck eines Sudoku das in matrix gespeichert ist
*/
private static void printSudoku() {
for (int i = 0; i <SIZE; i++) {
for (int j = 0; j < SIZE; j++)
System.out.print((matrix[i][j] == 0 ? " ": matrix[i][j])+" ");
System.out.println();
}
} //end printSudoku
public static void main(String[] args) {
boolean result;
if (args.length == 1) {
File file = new File(args[0]);
parseInput(file);
System.out.println("Eingabe des Sudoku-Problems:");
printSudoku();
System.out.println();
if (verifySudoku()){
System.out.println("ist korrekt");
}
else{
System.out.println("ist fehlerhaft");
return;
}
start = getTime();
result= solveSudoku();
end = getTime();
if (result){
System.out.println("Loesung des Sudoku:");
printSudoku();
System.out.println("wurde" + (verifySudoku()? " ": " nicht ")+
"erfolgreich ueberprueft");
System.out.println("Funktionsaufrufe: " + rec_tries);
printTiming();
}
else{
System.out.println("Fehlerhaftes Programm");
}
}
} // end main
// Routinen fuer Zeitmessung
private static long getTime(){
return System.nanoTime();
}
private static void printTiming(){
double fMilliSeconds = (end - start) / 1000000.0;
System.out.printf("Sudoku geloest nach %5.1f ms", fMilliSeconds);
}
private static long start;
private static long end;
}
# Copyright Peter J.A. Cock, 2006
# All rights reserved.
#
# You may choose to be bound by either:
#
# (a) Licenced free for personal non-commerial use.
# May not be redistributed without prior permission.
#
# Or:
# (b) The GPL version 2, see http://www.gnu.org/licenses/gpl.html
RUN_BUILT_IN_TESTS=True
RUN_TEST_FILES=True
TRIPLETS = [[0,1,2],[3,4,5],[6,7,8]]
#Row/Col/3x3 iteration list, each is nine lists of nine (row,col) pairs
ROW_ITER = [[(row,col) for col in range(0,9)] for row in range(0,9)]
COL_ITER = [[(row,col) for row in range(0,9)] for col in range(0,9)]
TxT_ITER = [[(row,col) for row in rows for col in cols] for rows in TRIPLETS for cols in TRIPLETS]
class sudoku:
def __init__(self, start_grid=None) :
#Setup list of lists (the rows), each row is a list of 9 cells, which are each a list of integers 1-9 inclusive.
self.squares =[ [range(1,10) for col in range(0,9)] for row in range(0,9)]
if start_grid is not None:
if len(start_grid)==81 :
for row in range(0,9) :
self.set_row(row, start_grid[(row*9):((row+1)*9)])
else :
assert len(start_grid)==9, "Bad input!"
for row in range(0,9) :
self.set_row(row, start_grid[row])
#self.check()
self._changed=False
def solved(self) :
for row in range(0,9) :
for col in range(0,9) :
if len(self.squares[row][col]) > 1 :
return False
return True
def copy(self) :
sudoku_copy = sudoku(None)
for row in range(0,9) :
for col in range(0,9) :
sudoku_copy.squares[row][col] = self.squares[row][col][:] #copy!
sudoku_copy._changed=False
return sudoku_copy
def set_row(self,row, x_list) :
assert len(x_list)==9
for col in range(0,9) :
try :
x = int(x_list[col])
except :
x = 0
#self.set_cell(row,col,x)
self.set_cell(row,col,x)
def set_cell(self,row,col,x):
if self.squares[row][col] == [x] :
#Already done!
pass
elif x not in range(1,9+1) :
#Set to unknown
pass
else:
assert x in self.squares[row][col], \
"Told to set square (%i,%i) to an impossible entry, %i" % (row,col,x)
self.squares[row][col] = [x]
self.update_neighbours(row,col,x)
self._changed=True
def cell_exclude(self, row,col,x) :
assert x in range(1,9+1)
if x in self.squares[row][col] :
#Remove it...
self.squares[row][col].remove(x)
#Should be one or more entries left...
assert len(self.squares[row][col]) > 0, \
"Removed last possible entry for square (%i,%i) which was %i" \
% (row, col, x)
#Now, has this confirmed the value for this square?
if len(self.squares[row][col]) == 1 :
#This cell is now definate..
#Need to update its friends...
#print "After exluding %i, square (%i,%i) must be %i" \
#% (x, self.row, self.col, self[0])
self._changed=True
self.update_neighbours(row,col,self.squares[row][col][0])
else :
#Don't need to remove this, already done!
pass
return
def row_exclude(self, row, x) :
assert x in range(1,9+1)
for col in range(0,9) :
self.cell_exclude(row,col,x)
def col_exclude(self, col, x) :
assert x in range(1,9+1)
for row in range(0,9) :
self.cell_exclude(row,col,x)
def update_neighbours(self,set_row,set_col,x) :
"""Call this when the square is set to x, either directly,
or as a side effect of an exclude leaving only one entry"""
#print "Updating (%i,%i) to be %i..." % (self.row, self.col, x)
#Update the possibilies in this row...
for row in range(0,9) :
if row <> set_row :
self.cell_exclude(row,set_col,x)
#Update the possibilies in this col...
for col in range(0,9) :
if col <> set_col :
self.cell_exclude(set_row,col,x)
#Update the possibilies in this 3x3 square...
for triplet in TRIPLETS :
if set_row in triplet : rows = triplet[:]
if set_col in triplet : cols = triplet[:]
#Only need to do four of the eight possibles (well, 9 if you count the cell itself)
#as did two on the row, and two on the col
rows.remove(set_row)
cols.remove(set_col)
for row in rows :
for col in cols :
assert row <> set_row or col <> set_col
#print "Updating (%i,%i) to be %i, excluding %i from (%i, %i)" \
#% (self.row, self.col, x, x, row, col)
self.cell_exclude(row,col,x)
def get_cell_int(self,row,col) :
if len(self.squares[row][col])==1 :
return int(self.squares[row][col][0])
else :
return 0
def get_cell_str(self,row,col) :
if len(self.squares[row][col])==1 :
return "(%i,%i) = %i" % (row, col, self.squares[row][col][0])
else :
return ("(%i,%i) = " % (row, col)) + ",".join([str(x) for x in self.squares[row][col]])
def get_cell_digit_str(self,row,col) :
if len(self.squares[row][col])==1 :
return str(self.squares[row][col][0])
else :
return "0"
def as_test_81(self) :
"""Return a string of 81 digits"""
return "".join(self.as_test_list())
def simple_text(self) :
return "\n".join(self.as_test_list())
def as_test_list(self) :
return [ ("".join( [self.get_cell_digit_str(row,col) for col in range(0,9)])) for row in range(0,9) ]
"""
answer=[]
for row in range(0,9) :
line=""
for col in range(0,9) :
line = line + self.get_cell_digit_str(row,col)
answer.append(line)
return answer
"""
def __repr__(self):
answer="[" + ",".join([ \
("[" + ",".join( [self.get_cell_digit_str(row,col) for col in range(0,9)]) + "]") \
for row in range(0,9) ])
return answer
def __str__(self):
answer = " 123 456 789\n"
for row in range(0,9) :
answer = answer + str(row+1) \
+ " [" + "".join([self.get_cell_digit_str(row,col).replace("0","?") for col in range(0,3)]) \
+ "] [" + "".join([self.get_cell_digit_str(row,col).replace("0","?") for col in range(3,6)]) \
+ "] [" + "".join([self.get_cell_digit_str(row,col).replace("0","?") for col in range(6,9)]) \
+ "]\n"
if row+1 in [3,6] :
answer = answer + " --- --- ---\n"
return answer
def check(self, level=0) :
self._changed=True
while self._changed:
#print "checking..."
self._changed=False
self.check_for_single_occurances()
self.check_for_last_in_row_col_3x3()
if level >= 1 :
self.overlapping_3x3_and_row_or_col() #(aka slicing and dicing)
if level >= 2 :
self.one_level_supposition()
if level >= 3 :
self.two_level_supposition()
#If nothing happened, then self.changed==False (still)
#and we break the loop
return
def check_for_single_occurances(self):
#Want to see if x only occurs once in this row/col/3x3...
for check_type in [ROW_ITER, COL_ITER, TxT_ITER]:
for check_list in check_type :
for x in range(1,9+1) : #1 to 9 inclusive
x_in_list = []
for (row,col) in check_list :
if x in self.squares[row][col] :
x_in_list.append((row,col))
if len(x_in_list)==1 :
(row,col) = x_in_list[0]
#This position MUST be be x
if len(self.squares[row][col]) > 1 :
self.set_cell(row,col,x)
def check_for_last_in_row_col_3x3(self):
#Now, for each row/col/3x3 want to see if there is a single
#unknown entry...
for (type_name, check_type) in [("Row",ROW_ITER),("Col",COL_ITER),("3x3",TxT_ITER)]:
for check_list in check_type :
unknown_entries = []
unassigned_values = range(1,9+1) #1-9 inclusive
known_values = []
for (row,col) in check_list :
if len(self.squares[row][col]) == 1 :
assert self.squares[row][col][0] not in known_values, \
"Already have %i (%i,%i) in known list [%s] for %s" % (self.squares[row][col][0],row,col, ",".join(map(str,known_values)), type_name)
known_values.append(self.squares[row][col][0])
assert self.squares[row][col][0] in unassigned_values, \
"Expected %i (%i,%i) in list [%s] for %s" % (self.squares[row][col][0],row,col, ",".join(map(str,unassigned_values)), type_name)
unassigned_values.remove(self.squares[row][col][0])
else :
unknown_entries.append((row,col))
assert len(unknown_entries) + len(known_values) == 9
assert len(unknown_entries) == len(unassigned_values)
if len(unknown_entries) == 1 :
#This cell must be the only number 1-9 not in known_values
x = unassigned_values[0]
(row,col) = unknown_entries[0]
#assert x not in known_values
#print "Because its the last cell in its row/col/3x3 entry (%i,%i) must be %i" \
#% (row,col,x)
self.set_cell(row,col,x)
"""
for row in range(0,9) : self.check_row(row)
for col in range(0,9) : self.check_col(col)
#Check the 3x3 squares...
for rows in TRIPLETS :
for cols in TRIPLETS :
for x in range(0,9) :
x_in_location=[]
for row in rows:
for col in cols :
if x in self.squares[row][col] :
x_in_location.append((row,col))
if len(x_in_location)==1 :
(row,col) = x_in_location[0]
#This position MUST be be x
if len(self.squares[row][col]) > 1 :
self.set_cell(row,col,x)
"""
return
def diagnosis(self) :
answer=""
df = long(1)
for row in range(0,9) :
for col in range(0,9):
if len(self.squares[row][col]) > 1 :
answer = answer + str(self.squares[row][col]) + "\n"
df = df * len(self.squares[row][col])
answer = answer + "Degrees of freedom: %i" % df
return answer
def overlapping_3x3_and_row_or_col(self):
"""Block and Column / Row Interactions (name from Simon Armstrong)
http://www.simes.clara.co.uk/programs/sudokutechnique3.htm
Also known as 'slicing and dicing'
"""
#For a given 3x3, and a given digit, want to see if
#all the remaining candidates are in a single row or column..
#Want to see if x only occurs once in this row/col/3x3...
for check_list in TxT_ITER :
for x in range(1,9+1) : #1 to 9 inclusive
#print "Checking %i in 3x3" % x, check_list
rows_for_x = []
cols_for_x = []
for (row,col) in check_list :
if x in self.squares[row][col] :
#print "Found possible %i at (%i,%i)" % (x, row, col)
if row not in rows_for_x : rows_for_x.append(row)
if col not in cols_for_x : cols_for_x.append(col)
#Are they all in the same row?
if len(rows_for_x)==1 and len(cols_for_x) > 1 :
#print "%i must be in row %i using cols %s" % (x, rows_for_x[0]+1, ",".join(map(lambda i : str(i+1),cols_for_x)))
#print self
#This means, we can remove X from all the rest of the row...
row = rows_for_x[0]
for col in range(0,9) :
if col not in cols_for_x :
self.cell_exclude(row,col,x)
#We can also remove x from all the rest of this 3x3...
for (row,col) in check_list :
if col not in cols_for_x :
if row not in rows_for_x :
self.cell_exclude(row,col,x)
#Are they all in the same col?
if len(cols_for_x)==1 and len(rows_for_x) > 1 :
#print "%i must be in col %i using rows %s" % (x, cols_for_x[0]+1, ",".join(map(lambda i : str(i+1),rows_for_x)))
#print self
#This means, we can remove X from all the rest of the row...
col = cols_for_x[0]
for row in range(0,9) :
if row not in rows_for_x :
self.cell_exclude(row,col,x)
#We can also remove x from all the rest of this 3x3...
for (row,col) in check_list :
if col not in cols_for_x :
if row not in rows_for_x :
self.cell_exclude(row,col,x)
def one_level_supposition(self):
"""Probably what is known as 'Nishio', try a number and see if it leads to a dead end.
For all the ambigous squares, try each possible each entry and see
if its OK, or if it leads to a contradiction. In the case of a contradiction
we can remove it as a possibility...
Two level suppositions (two guess) may be required for extreme puzzles..."""
progress=True
while progress :
progress=False
#print "Doing one level supposition..."
for row in range(0,9) :
for col in range(0,9):
if len(self.squares[row][col]) > 1 :
bad_x = []
for x in self.squares[row][col] :
#print "/-- Trying setting (%i,%i) to %i" % (row,col,x)
sudoku_copy = self.copy()
try:
sudoku_copy.set_cell(row,col,x)
sudoku_copy.check(level=1)
except AssertionError, e :
#Leads to an error :)
#This means that this square cannot be x
#print e
#print "%s cannot be %i" % (str(self.squares[row][col]), x)
bad_x.append(x)
del sudoku_copy
#print "\-- End of exp"
if len(bad_x) == 0 :
pass
elif len(bad_x) < len(self.squares[row][col]) :
for x in bad_x :
self.cell_exclude(row,col,x)
self.check()
progress=True
else :
assert False, "Bugger! All possible values for square (%i,%i) fail" \
% (row,col)
#print "One level supposition done"
def two_level_supposition(self) :
progress=True
while progress :
progress=False
#print "Doing two level supposition..."
for row in range(0,9) :
for col in range(0,9):
if len(self.squares[row][col]) > 1 :
bad_x = []
for x in self.squares[row][col] :
#print "/-- Trying setting (%i,%i) to %i" % (row,col,x)
sudoku_copy = self.copy()
try:
sudoku_copy.set_cell(row,col,x)
#sudoku_copy.check()
#sudoku_copy.one_level_supposition()
sudoku_copy.check(level=2)
except AssertionError, e :
#Leads to an error :)
#This means that this square cannot be x
#print e
#print "%s cannot be %i" % (str(self.squares[row][col]), x)
bad_x.append(x)
del sudoku_copy
#print "\-- End of exp"
if len(bad_x) == 0 :
pass
elif len(bad_x) < len(self.squares[row][col]) :
for x in bad_x :
self.cell_exclude(row,col,x)
self.check()
progress=True
else :
assert False, "Bugger! All possible values for square (%i,%i) fail" \
% (row,col)
#print "Two level supposition done"
if __name__ == "__main__" and RUN_BUILT_IN_TESTS :
print "Running built in tests..."
tests = []
tests.append(
("Easy example from Warwick The Magazine",
['081074900', '004019307', '379085014', '007831000', '238456179', '006927400', '843562791', '762198543', '005743862'],
['681374925', '524619387', '379285614', '497831256', '238456179', '156927438', '843562791', '762198543', '915743862'],
None,
None,
None))
tests.append(
("Easy example from http://www.sudoku.com/",
['060104050', '008305600', '200609001', '800437006', '006852300', '700961004', '500703002', '007206900', '642598173'],
['963174258', '178325649', '254689731', '821437596', '496852317', '735961824', '589713462', '317246985', '642598173'],
None,
None,
None))
tests.append(
("Novemeber 2005 contest from http://www.sudoku.com/",
['000342000', '540070080', '002005406', '060200000', '308000204', '000008070', '609120500', '030080019', '000539000'],
['816342957', '543976182', '792815436', '467253891', '358791264', '921468375', '689127543', '235684719', '174539628'],
None,
None,
None))
tests.append(
("No. One from http://sudokublog.typepad.com/sudokublog/2005/08/two_and_three_i.html",
['000538400', '800007000', '437962851', '900605340', '700803005', '053004009', '004759160', '000001003', '001386000'],
['219538476', '865147932', '437962851', '982615347', '746893215', '153274689', '324759168', '678421593', '591386724'],
None,
None,
None))
tests.append(
("No. Two from http://sudokublog.typepad.com/sudokublog/2005/08/two_and_three_i.html",
['000004000', '000027486', '400803050', '009278300', '700030009', '003469800', '030702008', '248350000', '000900000'],
['800604000', '391527486', '400803050', '009278300', '784135009', '023469800', '930742008', '248350000', '000980000'],
['800604000', '391527486', '400803050', '009278300', '784135009', '023469800', '930742008', '248351007', '000986000'],
['852614793', '391527486', '467893152', '619278345', '784135629', '523469871', '936742518', '248351967', '175986234'],
None))
tests.append(
("No. Three from http://sudokublog.typepad.com/sudokublog/2005/08/two_and_three_i.html",
['508073190', '901600408', '000908035', '070000060', '002000900', '010000080', '190306000', '203007009', '687190304'],
['528473196', '931600478', '700918235', '070000560', '002700940', '010000780', '190306807', '203007619', '687190304'],
['528473196', '931600478', '700918235', '070000560', '002700940', '010000780', '190306807', '203007619', '687190304'],
['528473196', '931625478', '764918235', '379284561', '852761943', '416539782', '195346827', '243857619', '687192354'],
None))
tests.append(
("X-wings from http://sudokublog.typepad.com/sudokublog/2005/08/xwings.html",
['096047080', '000006000', '274108003', '560081207', '007002800', '428079031', '642813759', '000964328', '080725416'],
['196347582', '835296174', '274158963', '563481297', '917632845', '428579631', '642813759', '751964328', '389725416'],
None,
None,
None))
tests.append(
("http://blogs.sun.com/roller/page/danrice?entry=wednesday_sudoku_puzzle",
['006008070', '100600400', '004210003', '001080090', '260030184', '080060300', '600045700', '005001006', '010900500'],
['006408071', '170603400', '004217063', '001780690', '267539184', '089160307', '600045710', '005001006', '010906500'],
['006458071', '170693400', '004217063', '001780690', '267539184', '089160307', '600045710', '005001006', '010906500'],
['936458271', '172693458', '854217963', '341782695', '267539184', '589164327', '623845719', '795321846', '418976532'],
None))
tests.append(
("Hard or even impossible from http://langabi.name/blog/2005/07/15/soduku-solver",
['000010700', '000030005', '000890000', '320000500', '006000200', '008000090', '000020000', '900070001', '001460070'],
['000010700', '000030005', '000890000', '320000500', '006000200', '008000090', '000020000', '900070001', '001460070'],
['000010700', '000030005', '000890000', '320000500', '006000200', '008000090', '000020000', '900070001', '001460070'],
None,
None)) #Don't try second level supposition - it takes forever and may not work
tests.append(
("Interlocking Triples Zero from http://sudokublog.typepad.com/sudokublog/2005/08/interlocking_tr.html",
['006809010', '000003600', '003207085', '290371000', '350624079', '000985032', '180006300', '005008000', '030702500'],
['506849013', '800153600', '013267085', '290371056', '350624079', '000985032', '180596300', '005438001', '030712508'],
['526849713', '879153624', '413267985', '298371456', '351624879', '647985132', '182596347', '765438291', '934712568'],
None,
None))
tests.append(
("Interlocking Triples One from http://sudokublog.typepad.com/sudokublog/2005/08/interlocking_tr.html",
['051003040', '006051038', '380700520', '018000005', '000010000', '500000410', '067004153', '143675289', '020100674'],
['051003046', '006051038', '380700521', '018000305', '030510800', '500300410', '067004153', '143675289', '025130674'],
['051003046', '006051038', '380700521', '018000305', '030510800', '500300410', '067004153', '143675289', '025130674'],
['251983746', '476251938', '389746521', '718492365', '634517892', '592368417', '967824153', '143675289', '825139674'],
None))
tests.append(
("Interlocking Triples Two from http://sudokublog.typepad.com/sudokublog/2005/08/interlocking_tr.html",
['500830027', '700600100', '308004006', '180000002', '430070019', '900000074', '600100708', '804007001', '270086000'],
['500830427', '740600183', '308704006', '187000002', '430070019', '900000074', '603100708', '804307261', '271086005'],
['500830427', '740600183', '308704006', '187000002', '430070019', '900000074', '603100708', '804307261', '271086005'],
['569831427', '742695183', '318724956', '187469532', '435278619', '926513874', '653142798', '894357261', '271986345'],
None))
tests.append(
("A 'very hard Sudoku' from http://www.saidwhat.co.uk/sudokus/index.php",
['100802030', '700000020', '000560070', '008000900', '005217403', '004000700', '030089000', '020000008', '080004006'],
['159872634', '763001825', '842563179', '278000901', '695217483', '314008702', '030089207', '020000008', '080024006'],
['159872634', '763941825', '842563179', '278435961', '695217483', '314698752', '536189247', '421756398', '987324516'],
None,
None))
tests.append(
("A 'Fiendish Sudoku' from http://www.saidwhat.co.uk/sudokus/index.php",
['030000014', '200500680', '900300000', '050010030', '080030070', '060020090', '000008002', '003004001', '570000000'],
['635782914', '247591683', '918346527', '752619438', '189435276', '364827195', '496178352', '823954761', '571263849'],
None,
None,
None))
tests.append(
("Angus Johnson",
['040300070', '800061000', '000087003', '006040010', '420010095', '010050600', '700630000', '000570001', '050004060'],
['140305876', '800061000', '000087103', '506040010', '420016095', '010050600', '701630000', '004570001', '050104060'],
['140305876', '800061000', '000087103', '506040010', '420016095', '010050600', '701630000', '004570001', '050104060'],
['149325876', '873461529', '265987143', '536849217', '428716395', '917253684', '791638452', '684572931', '352194768'],
None))
tests.append(
("http://sudoku.com/forums/viewtopic.php?t=1057",
['681735942', '592841637', '700000581', '006080203', '000000100', '009050470', '300000769', '917563824', '268479315'],
['681735942', '592841637', '700000581', '006080203', '000000100', '009050470', '300218769', '917563824', '268479315'],
['681735942', '592841637', '700000581', '006080203', '000000100', '009050470', '300218769', '917563824', '268479315'],
['681735942', '592841637', '734692581', '456187293', '873924156', '129356478', '345218769', '917563824', '268479315'],
None))
tests.append(
("Gallery: really tough puzzles, no 142. from http://www.paulspages.co.uk/sudoku/",
['850100000', '900000080', '600004003', '700000002', '308500100', '400090006', '200700004', '530000001', '100002070'],
['853169427', '914273685', '672854913', '795641832', '368527149', '421398756', '289715364', '537486291', '146932578'],
None,
None,
None))
tests.append(
("Gallery: outlaw puzzles, no 129. from http://www.paulspages.co.uk/sudoku/",
['900002600', '004000005', '007001000', '035080900', '600000004', '001007020', '000300800', '500000700', '002600001'],
['900002600', '004000005', '007001000', '035080900', '600000004', '001007020', '000300800', '500000700', '002600001'],
['900002600', '004000005', '007001000', '035080900', '600000004', '001007020', '000300800', '500000700', '002600001'],
['953742618', '124896375', '867531249', '235184967', '679253184', '481967523', '746315892', '518429736', '392678451'],
None))
tests.append(
("Gallery: outlaw puzzles, no 112. from http://www.paulspages.co.uk/sudoku/",
['800000600', '040500100', '070090000', '030020007', '600008004', '500000090', '000030020', '001006050', '004000003'],
['800000600', '040500100', '170090000', '430020007', '600008004', '500000090', '000030020', '301006050', '004000003'],
['800000600', '040500100', '170090000', '430020007', '600008004', '500000090', '000030020', '301006058', '004000003'],
['852314679', '943567182', '176892345', '438129567', '619758234', '527643891', '785431926', '391276458', '264985713'],
None))
tests.append(
("19-cell '#1' from Brain of Britain, http://sudoku.sourceforge.net/brain.htm#3x3",
['000040030', '980601000', '000000200', '000000001', '004050700', '600000000', '005000000', '000908076', '070030000'],
['000040030', '983621457', '000000200', '000000001', '004050700', '600000005', '005000000', '002918576', '070030000'],
['000040030', '983621457', '000000200', '000000001', '004050700', '600000005', '005000000', '002918576', '070030000'],
['267549138', '983621457', '541783269', '758392641', '314856792', '629174385', '195467823', '432918576', '876235914'],
None))
tests.append(
("19-cell '#4' - Hardest 3x3 ever - from Brain of Britain, http://sudoku.sourceforge.net/brain.htm#3x3",
['020000000', '000600003', '074080000', '000003002', '080040010', '600500000', '000010780', '500009000', '000000040'],
['026000000', '000600003', '074080000', '000003002', '080040010', '600500000', '000010780', '500009000', '000000040'],
['026000000', '000600003', '074080000', '000003002', '080040010', '600500000', '000010780', '500009000', '000000040'],
['126437958', '895621473', '374985126', '457193862', '983246517', '612578394', '269314785', '548769231', '731852649'],
None))
tests.append(
("Hard from Arjen Lentz for MySQL, http://forums.mysql.com/read.php?98,51406",
#['043080250', '600000000', '000001094', '900004070', '000608000', '010200003', '820500000', '000000005', '034090710'],
['043080250', '600000000', '000001094', '900004070', '000608000', '010200003', '820500000', '000000005', '534890710'],
['043980250', '600425000', '200001094', '900004070', '300608000', '410209003', '820500000', '000000005', '534890710'],
['043980250', '600425000', '200001094', '900004070', '300608000', '410209003', '820500000', '000000005', '534890710'],
['143986257', '679425381', '285731694', '962354178', '357618942', '418279563', '821567439', '796143825', '534892716'],
None))
tests.append(
("Ambiguous from Arjen Lentz for MySQL, http://forums.mysql.com/read.php?98,51406",
#['043080250', '600000000', '000001094', '900004070', '000608000', '010200003', '020500000', '000000005', '034090710'],
['043080250', '600000000', '000001094', '900004070', '000608000', '010200003', '020500000', '000000005', '534890710'],
['043980250', '600425000', '200001094', '900004070', '300608000', '410209003', '020500000', '000000005', '534890710'],
['043980250', '600425000', '200001094', '900004070', '300608000', '410209003', '020500000', '000000005', '534890710'],
['043986250', '600425000', '200731694', '900304070', '300608040', '410209063', '020500000', '000100025', '534892716'],
None))
tests.append(
("top95 = 48.3............71.2.......7.5....6....2..8.............1.76...3.....4......5....",
['480300000','000000071','020000000','705000060','000200800','000000000','001076000','300000400','000050000'],
['480300000','000000071','120000000','705000060','000200800','000000000','001076000','300000400','000053000'],
['480300000','000000071','120000000','705000060','000200800','000000000','001076000','300000400','000053000'],
['487312695','593684271','126597384','735849162','914265837','268731549','851476923','379128456','642953718'],
None))
for test in tests :
name = test[0]
print "Running test: " + name
x = sudoku(test[1])
assert x.as_test_list() == test[1], "Load failed"
x.check()
assert x.as_test_list() == test[2], "Simple check failed"
if test[3] is not None and not x.solved() :
if test[3] <> test[2]: print "Overlapping (aka slicing and dicing) should helps"
x.overlapping_3x3_and_row_or_col()
#x.check()
assert x.as_test_list() == test[3], "Overlapping failed"
if test[4] is not None and not x.solved() :
if test[4] <> test[3]: print "One level supposition helps"
x.one_level_supposition()
#x.check()
assert x.as_test_list() == test[4], "One level supposition failed"
if test[5] is not None and not x.solved() :
if test[5] <> test[4]: print "Two level supposition helps"
x.two_level_supposition()
#x.check()
assert x.as_test_list() == test[5], "Two level supposition failed"
print "Builtin tests passed"
if __name__ == "__main__" and RUN_TEST_FILES :
print "Running test files"
#Using only check() and one_level_suposition(), completes 82 out of 95 in this test file, http://magictour.free.fr/top95
import os
import time
for test_file in ["top95.txt","top91.txt","top100.txt","msk_009.txt","top870.txt"] :
if not os.path.isfile(test_file) :
#Try without the extension...
test_file = test_file[:-4]
if os.path.isfile(test_file) :
print "Running tests from file %s" % test_file
input_file = open(test_file, "r")
score = 0
count = 0
start_time = time.time()
while True :
line = input_file.readline()
if not line :
break
if len(line)==0 :
break
if line[-1] == "\n" :
line = line[:-1]
if line[-1] =="\r" :
line = line[:-1]
if len(line)==81 :
count=count+1
print "%i - [%s]" % (count, line),
x = sudoku(line)
x.check(level=2)
#x.overlapping_3x3_and_row_or_col()
#x.check()
#x.one_level_supposition()
#x.check()
if not x.solved() :
print "Trying level two",
#x.two_level_supposition()
x.check(level=3)
if x.solved() :
print " - Done"
score=score+1
else :
print "- Failed"
print x.as_test_list()
else :
print "Bad line:\n%s" % line
job_time = time.time()-start_time
input_file.close()
print "Score %i / %i in %0.2f seconds" % (score,count,job_time)
else :
print "Could not find test file " + test_file
if __name__ == "__main__" :
print "Running demonstration..."
t = sudoku(["800500930",
"050000000",
"000200100",
"007020000",
"600190008",
"400300069",
"000000450",
"104080000",
"000406007"])
print "Before:"
#print t.as_test_list()
print t
print "Check:"
t.check()
print t
print "overlapping_3x3_and_row_or_col:"
t.check(level=1)
print t
print "supposition:"
t.check(level=2)
#print t.as_test_list()
print t
/**
* Löse Sudoku rekursiv.
*
* @author Philipp Gressly (phi AT gressly DOT ch)
* Dez. 2010.
*/
public class Sudoku {
public static void main(String[] args) {
new Sudoku().top();
}
// Die Datenstruktur Sudoku ist in der Lage,
// ein ungelöstes oder auch ein bereits gelöstes
// Sudoku-Feld zu speichern.
// 0-Einträge bezeichnen noch leere Felder.
int[][] feld = {
{ 0, 8, 1, 0, 0, 0, 7, 3, 0 },
{ 9, 0, 0, 2, 0, 8, 0, 0, 4 },
{ 6, 0, 0, 0, 0, 0, 0, 0, 8 },
{ 0, 3, 0, 7, 0, 1, 0, 2, 0 },
{ 0, 0, 0, 0, 0, 0, 0, 0, 0 },
{ 0, 9, 0, 5, 0, 2, 0, 1, 0 },
{ 8, 0, 0, 0, 0, 0, 0, 0, 7 },
{ 7, 0, 0, 3, 0, 6, 0, 0, 1 },
{ 0, 4, 5, 0, 0, 0, 6, 9, 0 } };
void top() {
loeseSudoku(this);
}
// Algorithmus aus "www.programmieraufgaben.ch"
void loeseSudoku(Sudoku s) {
// Abbruch:
if (unloesbar(s)) {
return;
}
if (geloest(s)) {
printLoesung(s);
System.exit(0);
}
// Rekursionsschritt:
int zeile = sucheErsteZeileMitLeereintraegen(s);
int unbenutzteZahl = sucheZahlDieAufZeileNichtVorkommt(s, zeile);
Sudoku[] sudokus = erzeugeSudokus(s, zeile, unbenutzteZahl);
for (Sudoku temp : sudokus) {
loeseSudoku(temp);
}
}
Sudoku[] erzeugeSudokus(Sudoku s, int zeile, int unbenutzteZahl) {
int nullerAnzahl = anzahlNullerAufZeile(s, zeile);
Sudoku[] sudokus = new Sudoku[nullerAnzahl];
int i = 0;
while (i < nullerAnzahl) {
sudokus[i] = neuesSudoku(s, zeile, unbenutzteZahl, i);
i = i + 1;
}
return sudokus;
}
/**
* @param pos bezeichnet die Null, die durch die
* "unbenutzteZahl" ersetzt werden muss.
* Dabei handelt es sich nicht um die Spaltenposition, sondern
* um das Auftreten der 0.
* Kommt die Null z. B. an den stellen 0, 3, 4 und 7 vor,
* so ist pos = 0, 1, 2, oder 3 und bezeichnet Spalte 0, 3, 4 bzw. 7.
*/
Sudoku neuesSudoku(Sudoku s, int zeile, int unbenutzteZahl, int pos) {
Sudoku sud = new Sudoku();
sud.feld = kopiere(s.feld);
int nr = -1;
int spalte = 0;
while (spalte < 9) {
if (0 == sud.feld[zeile][spalte]) {
nr = nr + 1;
if (nr == pos) {
sud.feld[zeile][spalte] = unbenutzteZahl;
return sud;
}
}
spalte = spalte + 1;
}
System.out.println("Fehler in pos: sud!");
System.exit(1);
return sud;
}
int[][] kopiere(int[][] f) {
int[][] kopie = new int[9][9];
int zeile, spalte;
zeile = 0;
while (zeile < 9) {
spalte = 0;
while (spalte < 9) {
kopie[zeile][spalte] = f[zeile][spalte];
spalte = spalte + 1;
}
zeile = zeile + 1;
}
return kopie;
}
int anzahlNullerAufZeile(Sudoku s, int zeile) {
int anz = 0;
int spalte = 0;
while (spalte < 9) {
if (0 == s.feld[zeile][spalte]) {
anz = anz + 1;
}
spalte = spalte + 1;
}
return anz;
}
int sucheZahlDieAufZeileNichtVorkommt(Sudoku s, int zeile) {
int zahl = 1;
while (zahl <= 9) {
int spalte = 0;
boolean kommtVor = false;
while (spalte < 9) {
if (zahl == s.feld[zeile][spalte]) {
kommtVor = true;
}
spalte = spalte + 1;
}
if (!kommtVor) {
return zahl;
}
zahl = zahl + 1;
}
return 10; // kommt nie vor!
}
int sucheErsteZeileMitLeereintraegen(Sudoku s) {
int zeile = 0;
while (zeile < 9) {
int spalte = 0;
while (spalte < 9) {
if (0 == s.feld[zeile][spalte]) {
return zeile;
}
spalte = spalte + 1;
}
zeile = zeile + 1;
}
System.out.println("Fehler -1!!");
return -1; //kommt nur vor, wenn unlösbar!
}
void printLoesung(Sudoku s) {
int x = 0;
while (x < 9) {
int y = 0;
while (y < 9) {
System.out.print(""+ s.feld[x][y] + ' ');
y = y + 1;
}
System.out.println();
x = x + 1;
}
}
/**
* Keine 0 kommt mehr vor
*
*/
boolean geloest(Sudoku s) {
int x = 0;
while (x < 9) {
int y = 0;
while (y < 9) {
if (0 == s.feld[x][y]) {
return false;
}
y = y + 1;
}
x = x + 1;
}
return true;
}
boolean unloesbar(Sudoku s) {
int i = 0;
while (i < 9) {
if (unloesbarWegenZeile(s, i)) {
return true;
}
if (unloesbarWegenSpalte(s, i)) {
return true;
}
if (unloesbarWegenBlock(s, i)) {
return true;
}
i = i + 1;
}
return false;
}
boolean unloesbarWegenZeile(Sudoku s, int i) {
int zahl = 1;
while (zahl <= 9) {
int vorkommen = 0;
int pos = 0;
while (pos < 9) {
if (s.feld[i][pos] == zahl) {
vorkommen = vorkommen + 1;
}
pos = pos + 1;
}
if (vorkommen > 1) {
return true;
}
zahl = zahl + 1;
}
return false;
}
boolean unloesbarWegenBlock(Sudoku s, int i) {
int zahl = 1;
while (zahl <= 9) {
int vorkommen = 0;
int posX = (i / 3) * 3; // int 0, 3 oder 6
int posY = 3 * (i % 3); // int 0, 3 oder 6
int x = 0;
while (x < 3) {
int y = 0;
while (y < 3) {
if (s.feld[posY + y][posX + x] == zahl) {
vorkommen = vorkommen + 1;
}
y = y + 1;
}
x = x + 1;
}
if (vorkommen > 1) {
return true;
}
zahl = zahl + 1;
}
return false;
}
boolean unloesbarWegenSpalte(Sudoku s, int i) {
int zahl = 1;
while (zahl <= 9) {
int vorkommen = 0;
int pos = 0;
while (pos < 9) {
if (s.feld[pos][i] == zahl) {
vorkommen = vorkommen + 1;
}
pos = pos + 1;
}
if (vorkommen > 1) {
return true;
}
zahl = zahl + 1;
}
return false;
}
} // end of class Sudoku
namespace SudokuLoesen
{
class Program
{
static int[,] feld = new int[9, 9];
static void Main(string[] args)
{
einlesen();
if (ausfuellen(0))
{
Console.WriteLine("Fertig");
ausgeben();
}
else Console.WriteLine("Keine Lösung gefunden");
Console.ReadLine();
}
static void einlesen()
{
string sstring;
int a = 0;
Console.WriteLine("Geben Sie das Sudoku zeilenweise ein.\nLeerstellen mit Nullen füllen.");
do
{
Console.Write((a + 1) + ". Zeile");
sstring = Console.ReadLine();
if (sstring.Length == 9)
{
for (int b = 0; b < 9; b++)
feld[a, b] = Convert.ToByte(sstring.Substring(b, 1));
a += 1;
}
else
Console.WriteLine("Neun Zahlen pro Zeile");
}
while (a<9);
}
static bool ausfuellen(int zaehler2)
{
int zaehler=1;
if (zaehler2 == 81)
return true;
else
{
if (feld[zaehler2 / 9, zaehler2 % 9] != 0)
{
if (ausfuellen(zaehler2 + 1))
return true;
else return false;
}
else
{
do
{
feld[zaehler2 / 9, zaehler2 % 9] = zaehler;
if (pruefen(zaehler, (zaehler2 / 9),( zaehler2 % 9)) == true)
if (ausfuellen(zaehler2 + 1) == true)
return true;
else zaehler += 1;
else zaehler += 1;
}
while (zaehler < 10);
feld[zaehler2 / 9, zaehler2 % 9] = 0;
return false;
}
}
}
static bool pruefen(int wert, int zind, int spind)
{
for (int count = 0; count < 9; count++)
{
if (count == spind)
continue;
if (feld[zind, count] == wert)
return false;
}
for (int count = 0; count < 9; count++)
{
if (count == zind)
continue;
if (feld[count, spind] == wert)
return false;
}
for (int z1=(zind/3)* 3; z1 < ((zind/3) * 3 + 3); z1++)
{
if (z1 == zind)
continue;
for(int z2=(spind/3)*3;z2<((spind/3)*3+3);z2++)
{
if (z2==spind)
continue;
if (feld[z1, z2] == wert)
return false;
}
}
return true;
}
static void ausgeben()
{
for(byte a=0;a<9;a++)
{
Console.WriteLine();
for(byte b=0;b<9;b++)
Console.Write(feld[a,b]+" ");
}
}
}
}
Lösung von: Name nicht veröffentlicht
// Autor: Andy Großhennig
// Solution for task: Sudoku (Rekursion)
#include <iostream>
#include <Windows.h>
#include <vector>
#include <string>
#include <cstdlib>
using namespace std;
// Function: Show the sudoku on the console
void showSudoku(short sh_arrSudoku[9][9])
{
system("cls");
COORD cur={0,0};
SetConsoleCursorPosition(GetStdHandle(STD_OUTPUT_HANDLE),cur);
printf("X 1 2 3 4 5 6 7 8 9\nY\n\n");
// Loop: Go through the sudoku
for(short shAxisY = 0;shAxisY < 9;shAxisY++)
{
printf("%i ", (shAxisY + 1));
for(short shAxisX = 0;shAxisX < 9;shAxisX++)
{
if(shAxisX == 2 || shAxisX == 5)
if(sh_arrSudoku[shAxisY][shAxisX] != 0)
printf(" %i |", sh_arrSudoku[shAxisY][shAxisX]);
else
printf(" |");
else
if(sh_arrSudoku[shAxisY][shAxisX] != 0)
printf(" %i ", sh_arrSudoku[shAxisY][shAxisX]);
else
printf(" ");
}
if(shAxisY < 8)
{
if(shAxisY == 2 || shAxisY == 5)
printf("\n ----------|-----------|----------\n");
else
printf("\n | |\n");
}
}
}
// Function: Calculate free lines
inline void fillSquares(short sh_arrSudokuFinish[9][9], short *sh_pAxisY, short *sh_pAxisX, short shSquare, short shNumber, bool *bSudokuSuccessfully)
{
srand(GetTickCount());
vector<short>sh_vecFreeFields; //Vector for remaining free fields in a square
short shField; //Random field from the vector
// Switch: Calculate free field accordingly of the rules of sudoku
switch(shSquare)
{
case 1: for(short shAxisY = 0;shAxisY < 3;shAxisY++)
{
for(short shAxisX = 0;shAxisX < 3;shAxisX++)
{
if(sh_arrSudokuFinish[shAxisY][shAxisX] == 0) //Check whether the field is empty
{
switch(shAxisY)
{
case 0: if(shAxisX == 0)
sh_vecFreeFields.push_back(1);
else if(shAxisX == 1)
sh_vecFreeFields.push_back(2);
else
sh_vecFreeFields.push_back(3);
;
break;
case 1: if(shAxisX == 0)
sh_vecFreeFields.push_back(4);
else if(shAxisX == 1)
sh_vecFreeFields.push_back(5);
else
sh_vecFreeFields.push_back(6);
;
break;
case 2: if(shAxisX == 0)
sh_vecFreeFields.push_back(7);
else if(shAxisX == 1)
sh_vecFreeFields.push_back(8);
else
sh_vecFreeFields.push_back(9);
;
break;
}
}
else
continue;
}
};
break;
case 2: for(short shAxisY = 0;shAxisY < 3;shAxisY++)
{
for(short shAxisX = 3;shAxisX < 6;shAxisX++)
{
// Switch: Check the X-Axis
switch(shAxisY)
{
case 0: if(sh_arrSudokuFinish[0][0] == shNumber || sh_arrSudokuFinish[0][1] == shNumber || sh_arrSudokuFinish[0][2] == shNumber)
continue;
break;
case 1: if(sh_arrSudokuFinish[1][0] == shNumber || sh_arrSudokuFinish[1][1] == shNumber || sh_arrSudokuFinish[1][2] == shNumber)
continue;
break;
case 2: if(sh_arrSudokuFinish[2][0] == shNumber || sh_arrSudokuFinish[2][1] == shNumber || sh_arrSudokuFinish[2][2] == shNumber)
continue;
}
if(sh_arrSudokuFinish[shAxisY][shAxisX] == 0)
{
switch(shAxisY)
{
case 0: if(shAxisX == 3)
sh_vecFreeFields.push_back(1);
else if(shAxisX == 4)
sh_vecFreeFields.push_back(2);
else
sh_vecFreeFields.push_back(3);
;
break;
case 1: if(shAxisX == 3)
sh_vecFreeFields.push_back(4);
else if(shAxisX == 4)
sh_vecFreeFields.push_back(5);
else
sh_vecFreeFields.push_back(6);
;
break;
case 2: if(shAxisX == 3)
sh_vecFreeFields.push_back(7);
else if(shAxisX == 4)
sh_vecFreeFields.push_back(8);
else
sh_vecFreeFields.push_back(9);
;
break;
}
}
else
continue;
}
};
break;
case 3: for(short shAxisY = 0;shAxisY < 3;shAxisY++)
{
for(short shAxisX = 6;shAxisX < 9;shAxisX++)
{
// Switch: Check the X-Axis
switch(shAxisY)
{
case 0: if(sh_arrSudokuFinish[0][0] == shNumber || sh_arrSudokuFinish[0][1] == shNumber || sh_arrSudokuFinish[0][2] == shNumber || sh_arrSudokuFinish[0][3] == shNumber || sh_arrSudokuFinish[0][4] == shNumber || sh_arrSudokuFinish[0][5] == shNumber)
continue;
break;
case 1: if(sh_arrSudokuFinish[1][0] == shNumber || sh_arrSudokuFinish[1][1] == shNumber || sh_arrSudokuFinish[1][2] == shNumber || sh_arrSudokuFinish[1][3] == shNumber || sh_arrSudokuFinish[1][4] == shNumber || sh_arrSudokuFinish[1][5] == shNumber)
continue;
break;
case 2: if(sh_arrSudokuFinish[2][0] == shNumber || sh_arrSudokuFinish[2][1] == shNumber || sh_arrSudokuFinish[2][2] == shNumber || sh_arrSudokuFinish[2][3] == shNumber || sh_arrSudokuFinish[2][4] == shNumber || sh_arrSudokuFinish[2][5] == shNumber)
continue;
}
if(sh_arrSudokuFinish[shAxisY][shAxisX] == 0)
{
switch(shAxisY)
{
case 0: if(shAxisX == 6)
sh_vecFreeFields.push_back(1);
else if(shAxisX == 7)
sh_vecFreeFields.push_back(2);
else
sh_vecFreeFields.push_back(3);
break;
case 1: if(shAxisX == 6)
sh_vecFreeFields.push_back(4);
else if(shAxisX == 7)
sh_vecFreeFields.push_back(5);
else
sh_vecFreeFields.push_back(6);
break;
case 2: if(shAxisX == 6)
sh_vecFreeFields.push_back(7);
else if(shAxisX == 7)
sh_vecFreeFields.push_back(8);
else
sh_vecFreeFields.push_back(9);
break;
}
}
else
continue;
}
};
break;
case 4: for(short shAxisY = 3;shAxisY < 6;shAxisY++)
{
for(short shAxisX = 0;shAxisX < 3;shAxisX++)
{
// Switch: Check the Y-Axis
switch(shAxisX)
{
case 0: if(sh_arrSudokuFinish[0][0] == shNumber || sh_arrSudokuFinish[1][0] == shNumber || sh_arrSudokuFinish[2][0] == shNumber)
continue;
break;
case 1: if(sh_arrSudokuFinish[0][1] == shNumber || sh_arrSudokuFinish[1][1] == shNumber || sh_arrSudokuFinish[2][1] == shNumber)
continue;
break;
case 2: if(sh_arrSudokuFinish[0][2] == shNumber || sh_arrSudokuFinish[1][2] == shNumber || sh_arrSudokuFinish[2][2] == shNumber)
continue;
}
if(sh_arrSudokuFinish[shAxisY][shAxisX] == 0)
{
switch(shAxisY)
{
case 3: if(shAxisX == 0)
sh_vecFreeFields.push_back(1);
else if(shAxisX == 1)
sh_vecFreeFields.push_back(2);
else
sh_vecFreeFields.push_back(3);;
break;
case 4: if(shAxisX == 0)
sh_vecFreeFields.push_back(4);
else if(shAxisX == 1)
sh_vecFreeFields.push_back(5);
else
sh_vecFreeFields.push_back(6);;
break;
case 5: if(shAxisX == 0)
sh_vecFreeFields.push_back(7);
else if(shAxisX == 1)
sh_vecFreeFields.push_back(8);
else
sh_vecFreeFields.push_back(9);;
break;
}
}
else
continue;
}
};
break;
case 5: for(short shAxisY = 3;shAxisY < 6;shAxisY++)
{
for(short shAxisX = 3;shAxisX < 6;shAxisX++)
{
// Switch: Check the Y-Axis
switch(shAxisX)
{
case 3: if(sh_arrSudokuFinish[0][3] == shNumber || sh_arrSudokuFinish[1][3] == shNumber || sh_arrSudokuFinish[2][3] == shNumber)
continue;
break;
case 4: if(sh_arrSudokuFinish[0][4] == shNumber || sh_arrSudokuFinish[1][4] == shNumber || sh_arrSudokuFinish[2][4] == shNumber)
continue;
break;
case 5: if(sh_arrSudokuFinish[0][5] == shNumber || sh_arrSudokuFinish[1][5] == shNumber || sh_arrSudokuFinish[2][5] == shNumber)
continue;
}
// Switch: Check the X-Axis
switch(shAxisY)
{
case 3: if(sh_arrSudokuFinish[3][0] == shNumber || sh_arrSudokuFinish[3][1] == shNumber || sh_arrSudokuFinish[3][2] == shNumber)
continue;
break;
case 4: if(sh_arrSudokuFinish[4][0] == shNumber || sh_arrSudokuFinish[4][1] == shNumber || sh_arrSudokuFinish[4][2] == shNumber)
continue;
break;
case 5: if(sh_arrSudokuFinish[5][0] == shNumber || sh_arrSudokuFinish[5][1] == shNumber || sh_arrSudokuFinish[5][2] == shNumber)
continue;
}
if(sh_arrSudokuFinish[shAxisY][shAxisX] == 0)
{
switch(shAxisY)
{
case 3: if(shAxisX == 3)
sh_vecFreeFields.push_back(1);
else if(shAxisX == 4)
sh_vecFreeFields.push_back(2);
else
sh_vecFreeFields.push_back(3);
;
break;
case 4: if(shAxisX == 3)
sh_vecFreeFields.push_back(4);
else if(shAxisX == 4)
sh_vecFreeFields.push_back(5);
else
sh_vecFreeFields.push_back(6);
;
break;
case 5: if(shAxisX == 3)
sh_vecFreeFields.push_back(7);
else if(shAxisX == 4)
sh_vecFreeFields.push_back(8);
else
sh_vecFreeFields.push_back(9);
;
break;
}
}
else
continue;
}
};
break;
case 6: for(short shAxisY = 3;shAxisY < 6;shAxisY++)
{
for(short shAxisX = 6;shAxisX < 9;shAxisX++)
{
// Switch: Check the Y-Axis
switch(shAxisX)
{
case 6: if(sh_arrSudokuFinish[0][6] == shNumber || sh_arrSudokuFinish[1][6] == shNumber || sh_arrSudokuFinish[2][6] == shNumber)
continue;
break;
case 7: if(sh_arrSudokuFinish[0][7] == shNumber || sh_arrSudokuFinish[1][7] == shNumber || sh_arrSudokuFinish[2][7] == shNumber)
continue;
break;
case 8: if(sh_arrSudokuFinish[0][8] == shNumber || sh_arrSudokuFinish[1][8] == shNumber || sh_arrSudokuFinish[2][8] == shNumber)
continue;
}
// Switch: Check the X-Axis
switch(shAxisY)
{
case 3: if(sh_arrSudokuFinish[3][0] == shNumber || sh_arrSudokuFinish[3][1] == shNumber || sh_arrSudokuFinish[3][2] == shNumber || sh_arrSudokuFinish[3][3] == shNumber || sh_arrSudokuFinish[3][4] == shNumber || sh_arrSudokuFinish[3][5] == shNumber)
continue;
break;
case 4: if(sh_arrSudokuFinish[4][0] == shNumber || sh_arrSudokuFinish[4][1] == shNumber || sh_arrSudokuFinish[4][2] == shNumber || sh_arrSudokuFinish[4][3] == shNumber || sh_arrSudokuFinish[4][4] == shNumber || sh_arrSudokuFinish[4][5] == shNumber)
continue;
break;
case 5: if(sh_arrSudokuFinish[5][0] == shNumber || sh_arrSudokuFinish[5][1] == shNumber || sh_arrSudokuFinish[5][2] == shNumber || sh_arrSudokuFinish[5][3] == shNumber || sh_arrSudokuFinish[5][4] == shNumber || sh_arrSudokuFinish[5][5] == shNumber)
continue;
}
if(sh_arrSudokuFinish[shAxisY][shAxisX] == 0)
{
switch(shAxisY)
{
case 3: if(shAxisX == 6)
sh_vecFreeFields.push_back(1);
else if(shAxisX == 7)
sh_vecFreeFields.push_back(2);
else
sh_vecFreeFields.push_back(3);
;
break;
case 4: if(shAxisX == 6)
sh_vecFreeFields.push_back(4);
else if(shAxisX == 7)
sh_vecFreeFields.push_back(5);
else
sh_vecFreeFields.push_back(6);
;
break;
case 5: if(shAxisX == 6)
sh_vecFreeFields.push_back(7);
else if(shAxisX == 7)
sh_vecFreeFields.push_back(8);
else
sh_vecFreeFields.push_back(9);
;
break;
}
}
else
continue;
}
};
break;
case 7: for(short shAxisY = 6;shAxisY < 9;shAxisY++)
{
for(short shAxisX = 0;shAxisX < 3;shAxisX++)
{
// Switch: Check the Y-Axis
switch(shAxisX)
{
case 0: if(sh_arrSudokuFinish[0][0] == shNumber || sh_arrSudokuFinish[1][0] == shNumber || sh_arrSudokuFinish[2][0] == shNumber || sh_arrSudokuFinish[3][0] == shNumber || sh_arrSudokuFinish[4][0] == shNumber || sh_arrSudokuFinish[5][0] == shNumber)
continue;
break;
case 1: if(sh_arrSudokuFinish[0][1] == shNumber || sh_arrSudokuFinish[1][1] == shNumber || sh_arrSudokuFinish[2][1] == shNumber || sh_arrSudokuFinish[3][1] == shNumber || sh_arrSudokuFinish[4][1] == shNumber || sh_arrSudokuFinish[5][1] == shNumber)
continue;
break;
case 2: if(sh_arrSudokuFinish[0][2] == shNumber || sh_arrSudokuFinish[1][2] == shNumber || sh_arrSudokuFinish[2][2] == shNumber || sh_arrSudokuFinish[3][2] == shNumber || sh_arrSudokuFinish[4][2] == shNumber || sh_arrSudokuFinish[5][2] == shNumber)
continue;
}
if(sh_arrSudokuFinish[shAxisY][shAxisX] == 0)
{
switch(shAxisY)
{
case 6: if(shAxisX == 0)
sh_vecFreeFields.push_back(1);
else if(shAxisX == 1)
sh_vecFreeFields.push_back(2);
else
sh_vecFreeFields.push_back(3);
;
break;
case 7: if(shAxisX == 0)
sh_vecFreeFields.push_back(4);
else if(shAxisX == 1)
sh_vecFreeFields.push_back(5);
else
sh_vecFreeFields.push_back(6);
;
break;
case 8: if(shAxisX == 0)
sh_vecFreeFields.push_back(7);
else if(shAxisX == 1)
sh_vecFreeFields.push_back(8);
else
sh_vecFreeFields.push_back(9);
;
break;
}
}
else
continue;
}
};
break;
case 8: for(short shAxisY = 6;shAxisY < 9;shAxisY++)
{
for(short shAxisX = 3;shAxisX < 6;shAxisX++)
{
// Switch: Check the Y-Axis
switch(shAxisX)
{
case 3: if(sh_arrSudokuFinish[0][3] == shNumber || sh_arrSudokuFinish[1][3] == shNumber || sh_arrSudokuFinish[2][3] == shNumber || sh_arrSudokuFinish[3][3] == shNumber || sh_arrSudokuFinish[4][3] == shNumber || sh_arrSudokuFinish[5][3] == shNumber)
continue;
break;
case 4: if(sh_arrSudokuFinish[0][4] == shNumber || sh_arrSudokuFinish[1][4] == shNumber || sh_arrSudokuFinish[2][4] == shNumber || sh_arrSudokuFinish[3][4] == shNumber || sh_arrSudokuFinish[4][4] == shNumber || sh_arrSudokuFinish[5][4] == shNumber)
continue;
break;
case 5: if(sh_arrSudokuFinish[0][5] == shNumber || sh_arrSudokuFinish[1][5] == shNumber || sh_arrSudokuFinish[2][5] == shNumber || sh_arrSudokuFinish[3][5] == shNumber || sh_arrSudokuFinish[4][5] == shNumber || sh_arrSudokuFinish[5][5] == shNumber)
continue;
}
// Switch: Check the X-Axis
switch(shAxisY)
{
case 6: if(sh_arrSudokuFinish[6][0] == shNumber || sh_arrSudokuFinish[6][1] == shNumber || sh_arrSudokuFinish[6][2] == shNumber)
continue;
break;
case 7: if(sh_arrSudokuFinish[7][0] == shNumber || sh_arrSudokuFinish[7][1] == shNumber || sh_arrSudokuFinish[7][2] == shNumber)
continue;
break;
case 8: if(sh_arrSudokuFinish[8][0] == shNumber || sh_arrSudokuFinish[8][1] == shNumber || sh_arrSudokuFinish[8][2] == shNumber)
continue;
}
if(sh_arrSudokuFinish[shAxisY][shAxisX] == 0)
{
switch(shAxisY)
{
case 6: if(shAxisX == 3)
sh_vecFreeFields.push_back(1);
else if(shAxisX == 4)
sh_vecFreeFields.push_back(2);
else
sh_vecFreeFields.push_back(3);
;
break;
case 7: if(shAxisX == 3)
sh_vecFreeFields.push_back(4);
else if(shAxisX == 4)
sh_vecFreeFields.push_back(5);
else
sh_vecFreeFields.push_back(6);
;
break;
case 8: if(shAxisX == 3)
sh_vecFreeFields.push_back(7);
else if(shAxisX == 4)
sh_vecFreeFields.push_back(8);
else
sh_vecFreeFields.push_back(9);
;
break;
}
}
else
continue;
}
};
break;
case 9: for(short shAxisY = 6;shAxisY < 9;shAxisY++)
{
for(short shAxisX = 6;shAxisX < 9;shAxisX++)
{
// Switch: Check the Y-Axis
switch(shAxisX)
{
case 6: if(sh_arrSudokuFinish[0][6] == shNumber || sh_arrSudokuFinish[1][6] == shNumber || sh_arrSudokuFinish[2][6] == shNumber || sh_arrSudokuFinish[3][6] == shNumber || sh_arrSudokuFinish[4][6] == shNumber || sh_arrSudokuFinish[5][6] == shNumber)
continue;
break;
case 7: if(sh_arrSudokuFinish[0][7] == shNumber || sh_arrSudokuFinish[1][7] == shNumber || sh_arrSudokuFinish[2][7] == shNumber || sh_arrSudokuFinish[3][7] == shNumber || sh_arrSudokuFinish[4][7] == shNumber || sh_arrSudokuFinish[5][7] == shNumber)
continue;
break;
case 8: if(sh_arrSudokuFinish[0][8] == shNumber || sh_arrSudokuFinish[1][8] == shNumber || sh_arrSudokuFinish[2][8] == shNumber || sh_arrSudokuFinish[3][8] == shNumber || sh_arrSudokuFinish[4][8] == shNumber || sh_arrSudokuFinish[5][8] == shNumber)
continue;
}
// Switch: Check the X-Axis
switch(shAxisY)
{
case 6: if(sh_arrSudokuFinish[6][0] == shNumber || sh_arrSudokuFinish[6][1] == shNumber || sh_arrSudokuFinish[6][2] == shNumber || sh_arrSudokuFinish[6][3] == shNumber || sh_arrSudokuFinish[6][4] == shNumber || sh_arrSudokuFinish[6][5] == shNumber)
continue;
break;
case 7: if(sh_arrSudokuFinish[7][0] == shNumber || sh_arrSudokuFinish[7][1] == shNumber || sh_arrSudokuFinish[7][2] == shNumber || sh_arrSudokuFinish[7][3] == shNumber || sh_arrSudokuFinish[7][4] == shNumber || sh_arrSudokuFinish[7][5] == shNumber)
continue;
break;
case 8: if(sh_arrSudokuFinish[8][0] == shNumber || sh_arrSudokuFinish[8][1] == shNumber || sh_arrSudokuFinish[8][2] == shNumber || sh_arrSudokuFinish[8][3] == shNumber || sh_arrSudokuFinish[8][4] == shNumber || sh_arrSudokuFinish[8][5] == shNumber)
continue;
}
if(sh_arrSudokuFinish[shAxisY][shAxisX] == 0)
{
switch(shAxisY)
{
case 6: if(shAxisX == 6)
sh_vecFreeFields.push_back(1);
else if(shAxisX == 7)
sh_vecFreeFields.push_back(2);
else
sh_vecFreeFields.push_back(3);
;
break;
case 7: if(shAxisX == 6)
sh_vecFreeFields.push_back(4);
else if(shAxisX == 7)
sh_vecFreeFields.push_back(5);
else
sh_vecFreeFields.push_back(6);
;
break;
case 8: if(shAxisX == 6)
sh_vecFreeFields.push_back(7);
else if(shAxisX == 7)
sh_vecFreeFields.push_back(8);
else
sh_vecFreeFields.push_back(9);
;
break;
}
}
else
continue;
}
};
}
if(sh_vecFreeFields.size() > 0)
shField = sh_vecFreeFields.at(rand() % sh_vecFreeFields.size());
else
{
*bSudokuSuccessfully = false;
return;
}
// Switch: Choose a random field and calculate the coordinates
switch(shSquare)
{
case 1: switch(shField)
{
case 1: *sh_pAxisY = 0; *sh_pAxisX = 0;
break;
case 2: *sh_pAxisY = 0; *sh_pAxisX = 1;
break;
case 3: *sh_pAxisY = 0; *sh_pAxisX = 2;
break;
case 4: *sh_pAxisY = 1; *sh_pAxisX = 0;
break;
case 5: *sh_pAxisY = 1; *sh_pAxisX = 1;
break;
case 6: *sh_pAxisY = 1; *sh_pAxisX = 2;
break;
case 7: *sh_pAxisY = 2; *sh_pAxisX = 0;
break;
case 8: *sh_pAxisY = 2; *sh_pAxisX = 1;
break;
case 9: *sh_pAxisY = 2; *sh_pAxisX = 2;
};
break;
case 2: switch(shField)
{
case 1: *sh_pAxisY = 0; *sh_pAxisX = 3;
break;
case 2: *sh_pAxisY = 0; *sh_pAxisX = 4;
break;
case 3: *sh_pAxisY = 0; *sh_pAxisX = 5;
break;
case 4: *sh_pAxisY = 1; *sh_pAxisX = 3;
break;
case 5: *sh_pAxisY = 1; *sh_pAxisX = 4;
break;
case 6: *sh_pAxisY = 1; *sh_pAxisX = 5;
break;
case 7: *sh_pAxisY = 2; *sh_pAxisX = 3;
break;
case 8: *sh_pAxisY = 2; *sh_pAxisX = 4;
break;
case 9: *sh_pAxisY = 2; *sh_pAxisX = 5;
}
break;
case 3: switch(shField)
{
case 1: *sh_pAxisY = 0; *sh_pAxisX = 6;
break;
case 2: *sh_pAxisY = 0; *sh_pAxisX = 7;
break;
case 3: *sh_pAxisY = 0; *sh_pAxisX = 8;
break;
case 4: *sh_pAxisY = 1; *sh_pAxisX = 6;
break;
case 5: *sh_pAxisY = 1; *sh_pAxisX = 7;
break;
case 6: *sh_pAxisY = 1; *sh_pAxisX = 8;
break;
case 7: *sh_pAxisY = 2; *sh_pAxisX = 6;
break;
case 8: *sh_pAxisY = 2; *sh_pAxisX = 7;
break;
case 9: *sh_pAxisY = 2; *sh_pAxisX = 8;
};
break;
case 4: switch(shField)
{
case 1: *sh_pAxisY = 3; *sh_pAxisX = 0;
break;
case 2: *sh_pAxisY = 3; *sh_pAxisX = 1;
break;
case 3: *sh_pAxisY = 3; *sh_pAxisX = 2;
break;
case 4: *sh_pAxisY = 4; *sh_pAxisX = 0;
break;
case 5: *sh_pAxisY = 4; *sh_pAxisX = 1;
break;
case 6: *sh_pAxisY = 4; *sh_pAxisX = 2;
break;
case 7: *sh_pAxisY = 5; *sh_pAxisX = 0;
break;
case 8: *sh_pAxisY = 5; *sh_pAxisX = 1;
break;
case 9: *sh_pAxisY = 5; *sh_pAxisX = 2;
};
break;
case 5: switch(shField)
{
case 1: *sh_pAxisY = 3; *sh_pAxisX = 3;
break;
case 2: *sh_pAxisY = 3; *sh_pAxisX = 4;
break;
case 3: *sh_pAxisY = 3; *sh_pAxisX = 5;
break;
case 4: *sh_pAxisY = 4; *sh_pAxisX = 3;
break;
case 5: *sh_pAxisY = 4; *sh_pAxisX = 4;
break;
case 6: *sh_pAxisY = 4; *sh_pAxisX = 5;
break;
case 7: *sh_pAxisY = 5; *sh_pAxisX = 3;
break;
case 8: *sh_pAxisY = 5; *sh_pAxisX = 4;
break;
case 9: *sh_pAxisY = 5; *sh_pAxisX = 5;
};
break;
case 6: switch(shField)
{
case 1: *sh_pAxisY = 3; *sh_pAxisX = 6;
break;
case 2: *sh_pAxisY = 3; *sh_pAxisX = 7;
break;
case 3: *sh_pAxisY = 3; *sh_pAxisX = 8;
break;
case 4: *sh_pAxisY = 4; *sh_pAxisX = 6;
break;
case 5: *sh_pAxisY = 4; *sh_pAxisX = 7;
break;
case 6: *sh_pAxisY = 4; *sh_pAxisX = 8;
break;
case 7: *sh_pAxisY = 5; *sh_pAxisX = 6;
break;
case 8: *sh_pAxisY = 5; *sh_pAxisX = 7;
break;
case 9: *sh_pAxisY = 5; *sh_pAxisX = 8;
};
break;
case 7: switch(shField)
{
case 1: *sh_pAxisY = 6; *sh_pAxisX = 0;
break;
case 2: *sh_pAxisY = 6; *sh_pAxisX = 1;
break;
case 3: *sh_pAxisY = 6; *sh_pAxisX = 2;
break;
case 4: *sh_pAxisY = 7; *sh_pAxisX = 0;
break;
case 5: *sh_pAxisY = 7; *sh_pAxisX = 1;
break;
case 6: *sh_pAxisY = 7; *sh_pAxisX = 2;
break;
case 7: *sh_pAxisY = 8; *sh_pAxisX = 0;
break;
case 8: *sh_pAxisY = 8; *sh_pAxisX = 1;
break;
case 9: *sh_pAxisY = 8; *sh_pAxisX = 2;
};
break;
case 8: switch(shField)
{
case 1: *sh_pAxisY = 6; *sh_pAxisX = 3;
break;
case 2: *sh_pAxisY = 6; *sh_pAxisX = 4;
break;
case 3: *sh_pAxisY = 6; *sh_pAxisX = 5;
break;
case 4: *sh_pAxisY = 7; *sh_pAxisX = 3;
break;
case 5: *sh_pAxisY = 7; *sh_pAxisX = 4;
break;
case 6: *sh_pAxisY = 7; *sh_pAxisX = 5;
break;
case 7: *sh_pAxisY = 8; *sh_pAxisX = 3;
break;
case 8: *sh_pAxisY = 8; *sh_pAxisX = 4;
break;
case 9: *sh_pAxisY = 8; *sh_pAxisX = 5;
};
break;
case 9: switch(shField)
{
case 1: *sh_pAxisY = 6; *sh_pAxisX = 6;
break;
case 2: *sh_pAxisY = 6; *sh_pAxisX = 7;
break;
case 3: *sh_pAxisY = 6; *sh_pAxisX = 8;
break;
case 4: *sh_pAxisY = 7; *sh_pAxisX = 6;
break;
case 5: *sh_pAxisY = 7; *sh_pAxisX = 7;
break;
case 6: *sh_pAxisY = 7; *sh_pAxisX = 8;
break;
case 7: *sh_pAxisY = 8; *sh_pAxisX = 6;
break;
case 8: *sh_pAxisY = 8; *sh_pAxisX = 7;
break;
case 9: *sh_pAxisY = 8; *sh_pAxisX = 8;
};
break;
}
}
// Function: Create a new finished sudoku
void createSudokuFinish(short sh_arrSudokuFinish[9][9], bool *bSudokuSuccessfully)
{
short shAxisY;
short shAxisX;
bool bIsSudokuFinished = false;
*bSudokuSuccessfully = true;
// Loop: Go through the sudoku and set all positions to zero
for(shAxisY = 0;shAxisY < 9;shAxisY++)
{
for(shAxisX = 0;shAxisX < 9;shAxisX++)
{
sh_arrSudokuFinish[shAxisY][shAxisX] = 0;
}
shAxisX = 0;
}
// Loop: Provide the numbers
for(short shFirst = 1;shFirst < 10;shFirst++)
{
// Loop: Counts the amount of every number and fill the sudoku
for(short shSecond = 1;shSecond < 10;shSecond++)
{
fillSquares(sh_arrSudokuFinish, &shAxisY, &shAxisX, shSecond, shFirst, bSudokuSuccessfully);
if(*bSudokuSuccessfully == false)
return;
sh_arrSudokuFinish[shAxisY][shAxisX] = shFirst;
}
}
}
// Function: Remove a lot of numbers and create the sudoku to solve
void createSudoku(short sh_arrSudokuFinish[9][9], short sh_arrSudoku[9][9])
{
srand(GetTickCount());
short shCount = 0, shAxisY, shAxisX;
for(short shFirst = 0;shFirst < 9;shFirst++)
{
for(short shSecond = 0;shSecond < 9;shSecond++)
{
sh_arrSudoku[shFirst][shSecond] = sh_arrSudokuFinish[shFirst][shSecond];
}
}
while(shCount <= 50)
{
shAxisY = rand() % 9;
shAxisX = rand() % 9;
if(sh_arrSudoku[shAxisY][shAxisX] != 0)
{
sh_arrSudoku[shAxisY][shAxisX] = 0;
shCount++;
}
}
}
// Function: Get the coordinates and the number
void getInput(short sh_arrInput[3], short sh_arrSudoku[9][9], char *cChoice)
{
printf("\n\nEingabe: e, Hilfe: h, Aufloesen: a. ");
cin >> *cChoice;
if(*cChoice == 'h' || *cChoice == 'a')
return;
do
{
printf("X (1-9): ");
cin >> sh_arrInput[0];
printf("Y (1-9): ");
cin >> sh_arrInput[1];
printf("Number (1-9): ");
cin >> sh_arrInput[2];
}
while(sh_arrInput[0] <= 0 || sh_arrInput[0] >= 10 || sh_arrInput[1] <= 0 || sh_arrInput[1] >= 9 || sh_arrInput[2] <= 0 || sh_arrInput[2] >= 9 || sh_arrSudoku[(sh_arrInput[1] - 1)][(sh_arrInput[0] - 1)] != 0);
}
// Function: Solve a number or the sudoku
void help(short sh_arrSudoku[9][9], short sh_arrSudokuFinish[9][9], char cChoice)
{
if(cChoice == 'h')
{
for(short shAxisY = 0;shAxisY < 9;shAxisY++)
{
for(short shAxisX = 0;shAxisX < 9;shAxisX++)
{
if(sh_arrSudoku[shAxisY][shAxisX] == 0)
{
sh_arrSudoku[shAxisY][shAxisX] = sh_arrSudokuFinish[shAxisY][shAxisX];
return;
}
}
}
}
else
{
for(short shAxisY = 0;shAxisY < 9;shAxisY++)
{
for(short shAxisX = 0;shAxisX < 9;shAxisX++)
{
sh_arrSudoku[shAxisY][shAxisX] = sh_arrSudokuFinish[shAxisY][shAxisX];
}
}
}
}
// Function: Solve the sudoku by player input
void play(short sh_arrSudoku[9][9], short sh_arrSudokuFinish[9][9])
{
short sh_arrInput[3]; // 1: X, 2: Y, 3: Number
sh_arrInput[0] = 0;
sh_arrInput[1] = 0;
sh_arrInput[2] = 0;
char cChoice = ' ';
getInput(sh_arrInput, sh_arrSudoku, &cChoice);
if(cChoice == 'h' || cChoice == 'a')
help(sh_arrSudoku, sh_arrSudokuFinish, cChoice);
else
sh_arrSudoku[sh_arrInput[1] - 1][sh_arrInput[0] - 1] = sh_arrInput[2];
}
// Function: Manage sudoku
void sudoku()
{
COORD cur={0,0};
short sh_arrSudokuFinish[9][9]; //Finished sudoku
short sh_arrSudoku[9][9]; //Sudoku to solve
bool bSudokuSuccessfully = false;
int iAttemps = 0;
// Loop: Create a finished sudoku
while(bSudokuSuccessfully == false)
{
switch(iAttemps % 3)
{
case 3: printf("|");
break;
case 2: printf("/");
break;
case 1: printf("-");
break;
case 0: printf("\\");
};
SetConsoleCursorPosition(GetStdHandle(STD_OUTPUT_HANDLE),cur);
createSudokuFinish(sh_arrSudokuFinish, &bSudokuSuccessfully);
iAttemps++;
}
createSudoku(sh_arrSudokuFinish, sh_arrSudoku);
while(true)
{
showSudoku(sh_arrSudoku);
play(sh_arrSudoku, sh_arrSudokuFinish);
}
}
int main()
{
sudoku();
printf("\n\n");
system("Pause");
return 0;
}
Lösung von: Andy Großhennig (Bundeswehr)
Aktionen
Neue Lösung hinzufügen
Bewertung
Durchschnittliche Bewertung:
Meta
| Zeit: | 4-8 |
| Schwierigkeit: | k.A. |
| Webcode: | w29j-mrgu |
| Autor: | Philipp G. Freimann (BBW (Berufsbildungsschule Winterthur) https://www.bbw.ch) |
Kommentare (1)