package solve;

import data.SudokuBoard;
import data.SudokuController;
import data.SudokuRules;

public class SudokuSolver {
	
	private SudokuRules rules;
	private int freeColumn, freeLine;
	private SudokuController controller;

	/**
	 * 
	 * Constructor
	 * @param rules
	 * @param controller
	 */
	public SudokuSolver(SudokuRules rules, SudokuController controller) {
		this.rules = rules;
		this.controller = controller;
	}
	
	/**
	 * Method startSolve - sucht das erste freie Feld und ruft dann die Methode solve auf
	 * @param board - das Sudokufeld (int[][])
	 */
	public void startSolve(SudokuBoard board) {
		//Suche das erste leere Feld
		while(board.getValue(freeLine,freeColumn)!=0) {
			if(freeColumn<8) {
				freeColumn++;
			}
			else {
				freeColumn=0;
				if(freeLine<8) {
					freeLine++;	
				}
				else {
					break;
				}
				
			}
		}
		//Starte die Suche auf dem ersten freien Feld
		if(freeLine!=8 && freeColumn!=8) {
			if(solve(board,freeLine,freeColumn)) {
				controller.showSolution();
			}
		}
	}
	
	/**
	 * Method solve - die Methode löst das Sudoku mittels Backtracking-Algorithmus
	 * @param board - das Sudokufeld (int[][])
	 * @param line - die aktuelle Zeile
	 * @param column - die aktuelle Spalte
	 * @return - true: Lösung gefunden
	 */
	private boolean solve(SudokuBoard board, int line, int column) {
		//Wenn das Feld noch nicht belegt ist
		if(board.getValue(line,column)==0) {
			//Die Schleife überprüft für das aktuelle Feld jeden Wert von 1-9
			for(int i=1; i<10; i++) {
				//Wenn der Zug gültig ist
				if(rules.validMove(i,line,column)) {
					//Setze den Wert
					board.setWert(i,line,column);
					//Wenn das Feld nicht voll ist --> Sudoku noch nicht gelöst
					if(board.getOccupiedFields()<81) {
						//Nächster Zug, falls dieser "false" zurückgibt --> Nehme den aktuellen Zug zurück
						if(column==8) {	
							if(solve(board,line+1,0)) {
								return true;
							}
							else {
								board.setWert(0,line,column);
							}
						}
						else {	
							if(solve(board,line,column+1)) {
								return true;
							}
							else {
								board.setWert(0,line,column);
							}					
						}	
					}
					else {
						return true;						
					}		
				}	
			}
			return false;
		}
		//Wenn das Feld bereits belegt ist (D.h. das Feld wurde vom Benutzer gesetzt)
		else {
		// Nächster Zug, falls dieser "false" zurückgibt --> Sudoku hat keine Lösung
			if(column==8) {	
				if(solve(board,line+1,0)) {
					return true;
				}
				else {
					return false;
				}
			}
			else {	
				if(solve(board,line,column+1)) {
					return true;
				}	
				else {
					return false;
				}
			}	
		}
	}
}