/* Useful imports */

import edu.neu.ccs.*;
import edu.neu.ccs.gui.*;
import edu.neu.ccs.codec.*;
import edu.neu.ccs.console.*;
import edu.neu.ccs.filter.*;
import edu.neu.ccs.jpf.*;
import edu.neu.ccs.parser.*;
import edu.neu.ccs.pedagogy.*;
import edu.neu.ccs.quick.*;
import edu.neu.ccs.util.*;

import java.awt.*;
import java.awt.event.*;
import java.awt.geom.*;
import java.awt.font.*;
import java.awt.image.*;
import javax.swing.*;
import javax.swing.border.*;
import java.io.*;
import java.util.*;
import java.math.*;
import java.beans.*;
import java.lang.reflect.*;
import java.net.URL;
import java.util.regex.*;
import java.text.ParseException;


public class SudokuModel
    implements Stringable
{

    // Static definitions //
    
    /**
     * 9 puzzle rows in rows 1 to 9.
     * 
     * 9 puzzle cols in rows 10 to 18.
     * 
     * 9 puzzle blocks in rows 19 to 27.
     * 
     * By convention, row 0 and col 0 of this array
     * will be null.
     */
    private static CellPosition[][] celllist =
        new CellPosition[28][10];
    
    
    /** Initialize celllist. */
    static {
        int r;
        int c;
        int m;
        int k;
        CellPosition cell;
        
        for (int row = 1; row <= 9; row++) {
            for (int col = 1; col <= 9; col++) {
                cell = new CellPosition(row, col);
                
                k = row;
                
                celllist[k][col] = cell;
                
                k = col + 9;
                
                celllist[k][row] = cell;
                
                r = (row - 1) / 3;
                c = (col - 1) / 3;
                k = 3 * r + c + 19;
                
                r = (row - 1) % 3;
                c = (col - 1) % 3;
                m = 3 * r + c + 1;
                
                celllist[k][m] = cell;
            }
        }
    }
    
    
    // Member definitions //
    
    /**
     * The Sudoku GUI object.
     * 
     * Note: The purpose for maintaining a reference to the GUI
     * is to provide that reference to the table object and to
     * all blocks within the table.  The model does not use the
     * GUI in an active fashion.
     */
    private SudokuBase GUI = null;
    
    
    /** The view table associated with the model. */
    private SudokuTable table = null;
    
    
    /**
     * The cell data associated with the model.
     * 
     * By convention, row 0 and col 0 of this array
     * will be zero.
     */
    private int[][] celldata = new int[10][10];
    
    
    /**
     * The hint data associated with the model.
     * 
     * By convention, row 0 and col 0 of this array
     * will be null.
     */
    private SudokuHint[][] hints = new SudokuHint[10][10];
    
    
    /** Whether or not to prune triplets. */
    private boolean doPruneTriplets = true;
    
    /** Whether or not to prune hint sets. */
    private boolean doPruneHintSets = true;
    
    /** Whether or not to prune unique hints. */
    private boolean doPruneUniqueHints = true;
    
    
    // Constructors //
    
    /** The default constructor. */
    public SudokuModel() {
        initializeModel();
    }
    
    
    /** The constructor called by the Sudoku GUI object. */
    public SudokuModel(SudokuBase GUI) {
        this.GUI = GUI;
        
        initializeModel();
    }
    
    
    // Methods //
    
    /** Get the Sudoku puzzle GUI object. */
    public SudokuBase getSoduku() {
        return GUI;
    }
    
    
    /** Get the Sudoku puzzle table panel. */
    public SudokuTable getSudokuTable() {
        return table;
    }
    
    
    /** Initialize the model. */
    private void initializeModel() {
        table = new SudokuTable(this);
        
        for (int row = 1; row <= 9; row++)
            for (int col = 1; col <= 9; col++) {
                hints[row][col] = new SudokuHint();
                hints[row][col].setAll(true);
            }
    }
    
    
    /** Remove all cell data. */
    public void removeEverything() {
        for (int row = 1; row <= 9; row++)
            for (int col = 1; col <= 9; col++) {
                celldata[row][col] = 0;
                hints[row][col].setAll(true);
            }
    }
    
    
    /**
     * Get the cell data in the model.
     * 
     * A value from 1 to 9 should appear in the view.
     * A value of 0 signifies empty.
     * 
     * @param row the row between 1 and 9
     * @param col the col between 1 and 9
     */
    public int getCellData(int row, int col) {
        if ((row >= 1) && (row <= 9))
            if ((col >= 1) && (col <= 9))
                return celldata[row][col];
        
        return 0;
    }
    
    
    /**
     * Get the cell data in the model.
     * 
     * A value from 1 to 9 should appear in the view.
     * A value of 0 signifies empty.
     * 
     * @param position the cell position
     */
    public int getCellData(CellPosition position) {
        if (position == null)
            return 0;
        
        int row = position.row;
        int col = position.col;
        
        return getCellData(row, col);
    }
    
    
    /**
     * Set the cell data in the model but do
     * not update the view.
     * 
     * @param row the row between 1 and 9
     * @param col the col between 1 and 9
     * @param val the cell value between 0 and 9 with 0 = empty
     */
    public void setCellData(int row, int col, int val) {
        if ((val < 1) || (val > 9))
            val = 0;
        
        if ((row >= 1) && (row <= 9))
            if ((col >= 1) && (col <= 9))
                celldata[row][col] = val;
    }
    
    
    /**
     * Set the cell data in the model but do
     * not update the view.
     * 
     * @param position the cell position
     * @param val the cell value between 0 and 9 with 0 = empty
     */
    public void setCellData(CellPosition position, int val) {
        if (position == null)
            return;
        
        int row = position.row;
        int col = position.col;
        
        setCellData(row, col, val);
    }
    
    
    /**
     * Get the cell hint in the model.
     * 
     * @param row the row between 1 and 9
     * @param col the col between 1 and 9
     */
    public SudokuHint getCellHint(int row, int col) {
        if ((row >= 1) && (row <= 9))
            if ((col >= 1) && (col <= 9))
                return hints[row][col];
        
        return null;
    }
    
    
    /**
     * Get the cell hint in the model.
     * 
     * @param position the cell position
     */
    public SudokuHint getCellHint(CellPosition position) {
        if (position == null)
            return null;
        
        int row = position.row;
        int col = position.col;
        
        return getCellHint(row, col);
    }
    
    
    /** Initialize the hints prior to pruning. */
    public void initializeHints() {
        for (int row = 1; row <= 9; row++)
            for (int col = 1; col <= 9; col++) {
                hints[row][col].setAll(true);
            }
        
        for (int row = 1; row <= 9; row++)
            for (int col = 1; col <= 9; col++) {
                int data = celldata[row][col];
                
                if (data > 0) {
                    hints[row][col].setOneHint(data);
                    pruneBasic(row, col, data);
                }
            }
    }
    
    
    /** Set whether or not to prune triplets when pruning. */
    public void setPruneTriplets(boolean setting) {
        doPruneTriplets = setting;
    }
    
    
    /** Set whether or not to prune hint sets when pruning. */
    public void setPruneHintSets(boolean setting) {
        doPruneHintSets = setting;
    }
    
    
    /** Set whether or not to prune unique hints when pruning. */
    public void setPruneUniqueHints(boolean setting) {
        doPruneUniqueHints = setting;
    }
    
    
    /**
     * Prune hints by eliminating hints made impossible
     * by data or hints in other rows or cols.
     * 
     * This method repeats the pruning process until no
     * more hints can be pruned.
     * 
     * The pruning algorithms used depend on the settings
     * made via the methods:
     *     setPruneTriplets
     *     setPruneHintSets
     *     setPruneUniqueHints
     * 
     * Returns true if at least one hint was pruned.
     */
    public boolean pruneComplete() {
        boolean haspruned = false;
        
        while (pruneOneCycle())
            haspruned = true;
        
        return haspruned;
    }
    
    
    /** 
     * Performs one cycle of pruning hints.
     * 
     * The pruning algorithms used depend on the settings
     * made via the methods:
     *     setPruneTriplets
     *     setPruneHintSets
     *     setPruneUniqueHints
     * 
     * Returns true if at least one hint was pruned.
     */
    public boolean pruneOneCycle() {
        boolean haspruned = false;
        
        if (doPruneTriplets)
            haspruned |= pruneTriplets();
        
        if (doPruneHintSets)
            haspruned |= pruneHintSets();
        
        if (doPruneUniqueHints)
            haspruned |= pruneUniqueHints();
        
        return haspruned;
    }
    
    
    /**
     *  Prune the data hint from the row, col, and block
     *  containing (row, col) except for the cell itself.
     */
    private boolean pruneBasic(int row, int col, int data) {
        boolean haspruned = false;
        
        for (int r = 1; r <= 9; r++)
            if (r != row)
                haspruned |= hints[r][col].pruneHint(data);
        
        for (int c = 1; c <= 9; c++)
            if (c != col)
                haspruned |= hints[row][c].pruneHint(data);
        
        int row1 = 3 * ((row - 1) / 3) + 1;
        int row3 = row1 + 2;
        
        int col1 = 3 * ((col - 1) / 3) + 1;
        int col3 = col1 + 2;
        
        for (int r = row1; r <= row3; r++)
            for (int c = col1; c <= col3; c++)
                if (! ((r == row) && (c == col)))
                    haspruned |= hints[r][c].pruneHint(data);
        
        return haspruned;
    }
    
    
    /** Prune the row and col triplets. */
    private boolean pruneTriplets() {
        boolean haspruned = false;
        
        for (int data = 1; data <= 9; data++) {
            haspruned |= pruneRowTriplet(data);
            haspruned |= pruneColTriplet(data);
        }
        
        return haspruned;
    }
    
    
    /** Prune hints with the given data value via row comparison. */
    private boolean pruneRowTriplet(int data) {
        boolean haspruned = false;
        
        for (int rowgroup = 1; rowgroup <= 3; rowgroup++)
            haspruned |= pruneRowTriplet(data, rowgroup);
        
        return haspruned;
    }
    
    
    /**
     * Prune hints with the given data value via row comparison.
     * 
     * The rowgroup is between 1 and 3.
     * 
     * The startrow is 3 * (rowgroup - 1) + 1.  The other rows
     * are the next two rows.
     */
    private boolean pruneRowTriplet
        (int data, int rowgroup)
    {
        boolean haspruned = false;
        
        boolean[][] datainhint = new boolean[10][4];
        
        int row1 = 3 * (rowgroup - 1) + 1;
        int row3 = row1 + 2;
        
        for (int row = row1; row <= row3; row++) {
            for (int col = 1; col <= 9; col++) {
                int colgroup = ((col - 1) / 3) + 1;
                
                datainhint[row][colgroup] |=
                    hints[row][col].getHint(data);
            }
        }
        
        for (int colgroup = 1; colgroup <= 3; colgroup++) {
            int sum = 0;
            int row = 0;
            
            for (int r = row1; r <= row3; r++)
                if (datainhint[r][colgroup]) {
                    sum++;
                    row = r;
                }
            
            if (sum == 1) {
                for (int col = 1; col <= 9; col++)
                    if (colgroup != (((col - 1) / 3) + 1))
                        haspruned |= hints[row][col].pruneHint(data);
            }
        }
        
        return haspruned;
    }
    
    
    /** Prune hints with the given data value via col comparison. */
    private boolean pruneColTriplet(int data) {
        boolean haspruned = false;
        
        for (int colgroup = 1; colgroup <= 3; colgroup++)
            haspruned |= pruneColTriplet(data, colgroup);
        
        return haspruned;
    }
    
    
    /**
     * Prune hints with the given data value via col comparison.
     * 
     * The colgroup is between 1 and 3.
     * 
     * The startcol is 3 * (colgroup - 1) + 1.  The other cols
     * are the next two cols.
     */
    private boolean pruneColTriplet
        (int data, int colgroup)
    {
        boolean haspruned = false;
        
        boolean[][] datainhint = new boolean[4][10];
        
        int col1 = 3 * (colgroup - 1) + 1;
        int col3 = col1 + 2;
        
        for (int col = col1; col <= col3; col++) {
            for (int row = 1; row <= 9; row++) {
                int rowgroup = ((row - 1) / 3) + 1;
                
                datainhint[rowgroup][col] |=
                    hints[row][col].getHint(data);
            }
        }
        
        for (int rowgroup = 1; rowgroup <= 3; rowgroup++) {
            int sum = 0;
            int col = 0;
            
            for (int c = col1; c <= col3; c++)
                if (datainhint[rowgroup][c]) {
                    sum++;
                    col = c;
                }
            
            if (sum == 1) {
                for (int row = 1; row <= 9; row++)
                    if (rowgroup != (((row - 1) / 3) + 1))
                        haspruned |= hints[row][col].pruneHint(data);
            }
        }
        
        return haspruned;
    }
    
    
    /**
     * Returns an array of the hints corresponding to the
     * cell positions in the given array that are not yet
     * filled with data in the model.
     * 
     * Assumes cells has data in slots 1 to 9.
     * 
     * Returns an array of length 0 if all cell positions
     * already have data in the model.
     */
    private SudokuHint[] getHints(CellPosition[] cells) {
        int N = 0;
        
        for (int m = 1; m <= 9; m++) {
            int row = cells[m].row;
            int col = cells[m].col;
            
            if (celldata[row][col] == 0)
                N++;
        }
        
        SudokuHint[] array = new SudokuHint[N];
        
        if (N == 0)
            return array;
        
        int K = 0;
        
        for (int m = 1; m <= 9; m++) {
            int row = cells[m].row;
            int col = cells[m].col;
            
            if (celldata[row][col] == 0) {
                array[K] = hints[row][col];
                K++;
            }
        }
        
        return array;
    }
    
    
    /**
     * Prune the hints corresponding to each row of the
     * celllist array by using getHints to obtain the
     * hints for cells without data and then applying
     * the one argument form of pruneHintSets.
     */
    private boolean pruneHintSets() {
        boolean haspruned = false;
        
        SudokuHint[] hintlist;
        
        for (int i = 1; i <= 27; i++) {
            hintlist = getHints(celllist[i]);
            haspruned |= pruneHintListLoop(hintlist);
        }
        
        return haspruned;
    }
    
    
    /**
     * Prune the hints in the array of hints
     * provided that certain set-like conditions hold.
     * 
     * If there is a hint with 1 data value { a },
     * then prune { a } from all other hints.
     * 
     * If there is a hint with 2 data values { a, b }
     * and there is another hint that is a subset of
     * this hint, then prune { a, b } from all other
     * hints.
     * 
     * If there is a hint with 3 data values { a, b, c }
     * and there are another 2 hints that are subsets of
     * this hint, then prune { a, b, c } from all other
     * hints.
     * 
     * Etc, etc.
     * 
     * This method manages the loop to prune repeatedly
     * until pruning sets cannot be done further.
     */
    private boolean pruneHintListLoop(SudokuHint[] hintlist) {
        boolean haspruned = false;
        
        if (hintlist.length == 0)
            return haspruned;
        
        while (pruneHintListOnce(hintlist))
            haspruned = true;
        
        return haspruned;
    }
    
    
    /**
     * Prune the hints in the array of hints
     * provided that certain set-like conditions hold.
     * 
     * If there is a hint with 1 data value { a },
     * then prune { a } from all other hints.
     * 
     * If there is a hint with 2 data values { a, b }
     * and there is another hint that is a subset of
     * this hint, then prune { a, b } from all other
     * hints.
     * 
     * If there is a hint with 3 data values { a, b, c }
     * and there are another 2 hints that are subsets of
     * this hint, then prune { a, b, c } from all other
     * hints.
     * 
     * Etc, etc.
     * 
     * This method manages one cycle in the prune loop.
     */
    private boolean pruneHintListOnce(SudokuHint[] hintlist) {
        boolean haspruned = false;
        
        Arrays.sort(hintlist);
        
        int N = hintlist.length;
        
        int n = 0;
        
        while (n < N) {
            int k = hintlist[n].count();
            
            boolean ok = (0 < k) && ((k-1) <= n);
            
            if (! ok) {
                n++;
                continue;
            }
            
            boolean[] issubset = new boolean[N];
            
            issubset[n] = true;
            int m = 1;
            
            for (int i = 0; i < n; i++) {
                if (hintlist[i].count() > 0)
                    if (hintlist[n].contains(hintlist[i])) {
                        issubset[i] = true;
                        m++;
                    }
            }
            
            if (m == k) {
                for (int i = 0; i < N; i++)
                    if (! issubset[i])
                        haspruned |= hintlist[i].pruneHint(hintlist[n]);
                
                if (haspruned)
                    return haspruned;
            }
            
            n++;
        }
        
        return haspruned;
    }

    
    /**
     * Prune hints that are unique in a row, col, or block.
     */
    private boolean pruneUniqueHints() {
        boolean haspruned = false;
        
        for (int i = 1; i <= 27; i++)
            haspruned |= pruneUniqueHints(i);
        
        return haspruned;
    }
    
    
    /**
     * Prune hints that are unique in a row, col, or block
     * corresponding to celldata[i].
     */
    private boolean pruneUniqueHints(int i) {
        boolean haspruned = false;
        
        for (int data = 1; data <= 9; data++)
            haspruned |= pruneUniqueHints(i, data);
        
        return haspruned;
    }
    
    
    /**
     * Prune hints of value data
     * that are unique in a row, col, or block
     * corresponding to celldata[i].
     */
    private boolean pruneUniqueHints(int i, int data) {
        boolean haspruned = false;
        
        int sum = 0;
        int row = 0;
        int col = 0;
        int r = 0;
        int c = 0;
        
        for (int k = 1; k <= 9; k++) {
            row = celllist[i][k].row;
            col = celllist[i][k].col;
            
            if (celldata[row][col] == 0)
                if (hints[row][col].getHint(data)) {
                    sum++;
                    r = row;
                    c = col;
                }
        }
        
        if (sum == 1) {
            // prune all others hints from (r,c) itself
            for (int d = 1; d <= 9; d++)
                if (d != data)
                    haspruned |= hints[r][c].pruneHint(d);
            
            // prune data from direct neighbors of (r,c)
            haspruned |= pruneBasic(r, c, data);
        }
        
        return haspruned;
    }
    
    
    /**
     * Converts the Sudoku data from 9 rows with 9 cols
     * to 9 lines of text each with 9 digits.  Empty
     * cells are coded with digit 0 and non-empty cells
     * with their numeric value.
     */
    public String toString() {
        StringBuffer buffer = new StringBuffer(128);
        
        String string = "";
        
        for (int row = 1; row <= 9; row++) {
            for (int col = 1; col <= 9; col++)
                buffer.append(Integer.toString(celldata[row][col]));
            
            buffer.append('\n');
        }
        
        return buffer.toString();
    }
    
    
    /**
     * Identical to toString().
     * 
     * Used to implement Stringable.
     */
    public String toStringData() {
        return toString();
    }
    
    
    /**
     * Fills the cell data of this model using digit data
     * from the given string.
     * 
     * First clears all cell data in the model to 0.
     * 
     * Then uses the first 9 lines in the string to get 9
     * digits each to determine the corresponding cell
     * data in each col of each row.
     * 
     * Ignores non-digits other than the newlines used to
     * separate lines.  Gracefully handles the situation
     * of fewer than 9 lines or fewer than 9 digits per
     * line by simply leaving the corresponding cells at
     * the default of 0.
     * 
     * Permits the data to have no separators at all or
     * to have separators such as blanks or commas.
     * 
     * The call fromStringData(null) will clear the model.
     * 
     * Never throws ParseException.
     * 
     * Used to implement Stringable.
     */
    public void fromStringData(String data) {
        for (int row = 1; row <= 9; row++)
            for (int col = 1; col <= 9; col++)
                celldata[row][col] = 0;
        
        if (data == null)
            return;
        
        String[] lines = TextTools.extractNonEmptyLines(data);
        
        int rows = lines.length;
        
        for (int row = 1; row <= 9; row++) {
            int r = row - 1;
            
            if (r >= rows)
                break;
            
            int cols = lines[r].length();
            
            int c = 0;
            int col = 1;
            
            while (c < cols) {
                char x = lines[r].charAt(c);
                
                if (('0' <= x) && (x <= '9')) {
                    int digit = ((int) x) - ((int) '0');
                    setCellData(row, col, digit);
                    
                    col++;
                    if (col > 9)
                        break;
                }
                
                c++;
            }
        }
    }
    
    
    /** The main method that launches a SudokuBase. */
    public static void main(String[] args) {
        SudokuBase sudoku = new SudokuBase();
        
        sudoku.frame("Sudoku Puzzle");
    }
}