/**
 * Licensed to the Apache Software Foundation (ASF) under one
 * or more contributor license agreements.  See the NOTICE file
 * distributed with this work for additional information
 * regarding copyright ownership.  The ASF licenses this file
 * to you under the Apache License, Version 2.0 (the
 * "License"); you may not use this file except in compliance
 * with the License.  You may obtain a copy of the License at
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

package org.apache.hadoop.examples.dancing;

import java.io.*;
import java.util.*;

import org.apache.hadoop.thirdparty.com.google.common.base.Charsets;

/**
 * This class uses the dancing links algorithm from Knuth to solve sudoku
 * puzzles. It has solved 42x42 puzzles in 1.02 seconds.
 */
public class Sudoku {

  /**
   * The preset values in the board
   * board[y][x] is the value at x,y with -1 = any
   */ 
  private int[][] board;
  
  /**
   * The size of the board
   */
  private int size;
  
  /**
   * The size of the sub-squares in cells across
   */
  private int squareXSize;
  
  /**
   * The size of the sub-squares in celss up and down
   */
  private int squareYSize;
  
  /**
   * This interface is a marker class for the columns created for the
   * Sudoku solver.
   */
  protected static interface ColumnName {
    // NOTHING
  }

  /**
   * A string containing a representation of the solution.
   * @param size the size of the board
   * @param solution a list of list of column names
   * @return a string of the solution matrix
   */
  static String stringifySolution(int size, List<List<ColumnName>> solution) {
    int[][] picture = new int[size][size];
    StringBuffer result = new StringBuffer();
    // go through the rows selected in the model and build a picture of the
    // solution.
    for(List<ColumnName> row: solution) {
      int x = -1;
      int y = -1;
      int num = -1;
      for(ColumnName item: row) {
        if (item instanceof ColumnConstraint) {
          x = ((ColumnConstraint) item).column;
          num = ((ColumnConstraint) item).num;
        } else if (item instanceof RowConstraint) {
          y = ((RowConstraint) item).row;
        }
      }
      picture[y][x] = num;
    }
    // build the string
    for(int y=0; y < size; ++y) {
      for (int x=0; x < size; ++x) {
        result.append(picture[y][x]);
        result.append(" ");
      }
      result.append("\n");
    }
    return result.toString();
  }

  /**
   * An acceptor to get the solutions to the puzzle as they are generated and
   * print them to the console.
   */
  private static class SolutionPrinter 
  implements DancingLinks.SolutionAcceptor<ColumnName> {
    int size;

    public SolutionPrinter(int size) {
      this.size = size;
    }

    /**
     * A debugging aid that just prints the raw information about the 
     * dancing link columns that were selected for each row.
     * @param solution a list of list of column names
     */
    void rawWrite(List solution) {
      for (Iterator itr=solution.iterator(); itr.hasNext(); ) {
        Iterator subitr = ((List) itr.next()).iterator();
        while (subitr.hasNext()) {
          System.out.print(subitr.next().toString() + " ");
        }
        System.out.println();
      }      
    }
    
    public void solution(List<List<ColumnName>> names) {
      System.out.println(stringifySolution(size, names));
    }
  }

  /**
   * Set up a puzzle board to the given size.
   * Boards may be asymmetric, but the squares will always be divided to be
   * more cells wide than they are tall. For example, a 6x6 puzzle will make 
   * sub-squares that are 3x2 (3 cells wide, 2 cells tall). Clearly that means
   * the board is made up of 2x3 sub-squares.
   * @param stream The input stream to read the data from
   */
  public Sudoku(InputStream stream) throws IOException {
    BufferedReader file = new BufferedReader(
        new InputStreamReader(stream, Charsets.UTF_8));
    String line = file.readLine();
    List<int[]> result = new ArrayList<int[]>();
    while (line != null) {
      StringTokenizer tokenizer = new StringTokenizer(line);
      int size = tokenizer.countTokens();
      int[] col = new int[size];
      int y = 0;
      while(tokenizer.hasMoreElements()) {
        String word = tokenizer.nextToken();
        if ("?".equals(word)) {
          col[y] = - 1;
        } else {
          col[y] = Integer.parseInt(word);
        }
        y += 1;
      }
      result.add(col);
      line = file.readLine();
    }
    size = result.size();
    board = result.toArray(new int [size][]);
    squareYSize = (int) Math.sqrt(size);
    squareXSize = size / squareYSize;
    file.close();
  }
  
  /**
   * A constraint that each number can appear just once in a column.
   */
  static private class ColumnConstraint implements ColumnName {
    ColumnConstraint(int num, int column) {
      this.num = num;
      this.column = column;
    }
    int num;
    int column;
    public String toString() {
      return num + " in column " + column;
    }
  }
  
  /**
   * A constraint that each number can appear just once in a row.
   */
  static private class RowConstraint implements ColumnName {
    RowConstraint(int num, int row) {
      this.num = num;
      this.row = row;
    }
    int num;
    int row;
    public String toString() {
      return num + " in row " + row;
    }
  }

  /**
   * A constraint that each number can appear just once in a square.
   */
  static private class SquareConstraint implements ColumnName {
    SquareConstraint(int num, int x, int y) {
      this.num = num;
      this.x = x;
      this.y = y;
    }
    int num;
    int x;
    int y;
    public String toString() {
      return num + " in square " + x + "," + y;
    }
  }

  /**
   * A constraint that each cell can only be used once.
   */
  static private class CellConstraint implements ColumnName {
    CellConstraint(int x, int y) {
      this.x = x;
      this.y = y;
    }
    int x;
    int y;
    public String toString() {
      return "cell " + x + "," + y;
    }
  }
  
  /**
   * Create a row that places num in cell x, y.
   * @param rowValues a scratch pad to mark the bits needed
   * @param x the horizontal offset of the cell
   * @param y the vertical offset of the cell
   * @param num the number to place
   * @return a bitvector of the columns selected
   */
  private boolean[] generateRow(boolean[] rowValues, int x, int y, int num) {
    // clear the scratch array
    for(int i=0; i < rowValues.length; ++i) {
      rowValues[i] = false;
    }
    // find the square coordinates
    int xBox = x / squareXSize;
    int yBox = y / squareYSize;
    // mark the column
    rowValues[x*size + num - 1] = true;
    // mark the row
    rowValues[size*size + y*size + num - 1] = true;
    // mark the square
    rowValues[2*size*size + (xBox*squareXSize + yBox)*size + num - 1] = true;
    // mark the cell
    rowValues[3*size*size + size*x + y] = true;
    return rowValues;
  }
  
  private DancingLinks<ColumnName> makeModel() {
    DancingLinks<ColumnName> model = new DancingLinks<ColumnName>();
    // create all of the columns constraints
    for(int x=0; x < size; ++x) {
      for(int num=1; num <= size; ++num) {
        model.addColumn(new ColumnConstraint(num, x));
      }
    }
    // create all of the row constraints
    for(int y=0; y < size; ++y) {
      for(int num=1; num <= size; ++num) {
        model.addColumn(new RowConstraint(num, y));
      }
    }
    // create the square constraints
    for(int x=0; x < squareYSize; ++x) {
      for(int y=0; y < squareXSize; ++y) {
        for(int num=1; num <= size; ++num) {
          model.addColumn(new SquareConstraint(num, x, y));
        }
      }
    }
    // create the cell constraints
    for(int x=0; x < size; ++x) {
      for(int y=0; y < size; ++y) {
        model.addColumn(new CellConstraint(x, y));
      }
    }
    boolean[] rowValues = new boolean[size*size*4]; 
    for(int x=0; x < size; ++x) {
      for(int y=0; y < size; ++y) {
        if (board[y][x] == -1) {
          // try each possible value in the cell
          for(int num=1; num <= size; ++num) {
            model.addRow(generateRow(rowValues, x, y, num));
          }
        } else {
          // put the given cell in place
          model.addRow(generateRow(rowValues, x, y, board[y][x]));
        }
      }
    }
    return model;
  }
  
  public void solve() {
    DancingLinks<ColumnName> model = makeModel();
    int results = model.solve(new SolutionPrinter(size));
    System.out.println("Found " + results + " solutions");
  }
  
  /**
   * Solves a set of sudoku puzzles.
   * @param args a list of puzzle filenames to solve
   */
  public static void main(String[] args) throws IOException {
    if (args.length == 0) {
      System.out.println("Include a puzzle on the command line.");
    }
    for(int i=0; i < args.length; ++i) {
      Sudoku problem = new Sudoku(new FileInputStream(args[i]));
      System.out.println("Solving " + args[i]);
      problem.solve();
    }
  }

}