package si.sudoku;

import java.util.ArrayList;
import java.util.List;
import sac.graph.AStar;
import sac.graph.BestFirstSearch;
import sac.graph.GraphSearchAlgorithm;
import sac.graph.GraphSearchConfigurator;
import sac.graph.GraphState;
import sac.graph.GraphStateImpl;

public class Sudoku extends GraphStateImpl{
	public static int n=3;
	public static int n2=n*n;
	private byte[][] board=null;
	public int zeros=n2*n2;

	public Sudoku() {
		board=new byte[n2][n2];
		for(int i=0;i<n2;i++){
			for(int j=0;j<n2;j++){
				board[i][j]=0;
			}
		}
	}

	public Sudoku(Sudoku parent) {
		board=new byte[n2][n2];
		for(int i=0;i<n2;i++){
			for(int j=0;j<n2;j++){
				board[i][j]=parent.board[i][j];
			}
		}
		zeros=parent.zeros;
	}

	private void refreshZeros() {
		zeros=0;
		for(int i=0;i<n2;i++){
			for(int j=0;j<n2;j++){
				if(board[i][j]==0) {
					zeros++;
				}
			}
		}
	}

	@Override
	public String toString() {
		String txt="";
		for(int i=0;i<n2;i++){
			for(int j=0;j<n2;j++){
				txt+=board[i][j];
				if (j==8){
					txt+="\n";
				}
				else {
					txt+=",";
				}
			}
		}
		return txt;
	}


	public void fromStringN3(String txt)
	{
		int k=0;
		for(int i=0;i<n2;i++){
			for(int j=0;j<n2;j++){
				board[i][j]=Byte.valueOf(txt.substring(k,k+1));
				k++;
			}
		}
		refreshZeros();
	}

	public boolean isLegal()
	{
		byte[] group = new byte[n2];
		for(int i=0;i<n2;i++){
			for(int j=0;j<n2;j++){
				group[j]=board[i][j];
			}
			if(!isGroupLegal(group)) {
				return false;
			}
		}

		for(int i=0;i<n2;i++){
			for(int j=0;j<n2;j++){
				group[j]=board[j][i];
			}
			if(!isGroupLegal(group)) {
				return false;
			}
		}

        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
            int q = 0;
                for(int k=0;k<n;k++){
                    for(int l=0;l<n;l++){
                        group[q++] = board[i*n+k][j*n+l];
                    }
                }
                if(!isGroupLegal(group)) {
                	return false;
                }
            }
        }

		return true;
	}


	private boolean isGroupLegal(byte[] group)
	{
		boolean[] visited = new boolean[n2];
		for(int i=0;i<n2;i++){
			visited[i] = false;
		}

		for(int i=0;i<n2;i++){
			if(group[i]==0)
			{
				continue;
			}
			if(visited[group[i]-1])
			{
				return false;
			}
			visited[group[i] - 1] = true;
		}
		return true;
	}


	@Override
	public List<GraphState> generateChildren() {
		List<GraphState> children = new ArrayList<GraphState>();

		int i=0, j = 0;

		zeroFound:
		for(i=0;i<n2;i++) {
			for(j=0;j<n2;j++) {
				if(board[i][j]==0) {
					break zeroFound;
				}
			}
		}

		if(i==n2) {
			return children;
		}

		for(int k=0;k<n2;k++) {
			Sudoku child=new Sudoku(this);
			child.board[i][j]=(byte) (k+1);
			if(child.isLegal()) {
				children.add(child);
				child.zeros--;
			}
		}

		return children;
	}


	@Override
	public int hashCode() {
		// TODO Auto-generated method stub
		//return super.hashCode();
		return toString().hashCode();
	}

	@Override
	public boolean isSolution() {
		return ((zeros==0)&&(isLegal()));
	}

	public static void main(String[] args){
		Sudoku s=new Sudoku();

		//String sudoku= "003020600900305001001806400008102900700000008006708200002609500800203009005010300";	//poprawne
		String sudoku= "000000600900305001001806400008102900700000008006708200002609500800203009005010300";
		s.fromStringN3(sudoku);
		System.out.println(s);

		Sudoku.setHFunction(new HEmptyPlaces());
		GraphSearchConfigurator conf = new GraphSearchConfigurator();
		conf.setWantedNumberOfSolutions(Integer.MAX_VALUE);
		GraphSearchAlgorithm i = new BestFirstSearch(s,conf);
		i.execute();
		List<GraphState> solutions = i.getSolutions();

		for(GraphState sol : solutions) {
			System.out.println(sol);
			System.out.println("--------");
		}
		System.out.println("Time:" + i.getDurationTime());
		System.out.println("Closed:" + i.getClosedStatesCount());
		System.out.println("Open:" + i.getOpenSet().size());
		System.out.println("Open:" + i.getSolutions().size());
	}

}