using System;
using System.Collections.Generic;
using System.Diagnostics;

namespace Sudoku
{

/* Solves a Sudoku puzzle. The algorithm isn't genius; I wrote this to work the same way
 * that I solve difficult puzzles by hand, which is to fill in each blank with all the numbers
 * that could possibly go there based on the current row, block, and column constraints.
 * Since difficult puzzles won't reveal any definite answers immediately, I'll need to
 * guess about the value of a particular cell, and see how the additional constraint
 * affects the other values. I usually have to recurse a few times, and it can get
 * difficult to hold all the state in my head, or messy if I attempt to represent it on
 * paper. Eventually I'll hit a state that's impossible, in which case I need to revise
 * my most recent guess, or I'll complete the puzzle.
 * 
 * In this program, the board is represented as a 9x9 grid of integers. The bits set in
 * each integer determine the values that could possibly go in that cell. The low bit
 * represents the first digit, 1.
 */

class Program
{
  /// <summary>The value of a cell that can contain any digit.</summary>
  const ushort FullCell = 0x1FF;
  // a Sudoku board is NxN cells where N is K^2, and K is a positive integer
  const int BlockSize=3, BoardLength=BlockSize*BlockSize, BoardSize = BoardLength*BoardLength, Digits=BoardLength;
  
  static void Main(string[] args)
  {
    // ensure that there's enough space to display the board
    Console.BufferWidth = Math.Max(Console.BufferWidth, BoardLength*Digits + BoardLength + 2);
    Console.WindowWidth = Console.BufferWidth;

    // set the initial board state
    SetState(@"
-------------
|  2| 4 | 1 |
| 89| 1 | 7 |
|  1|   |  8|
|---+---+---|
|   |  4|  9|
|7  |281|  4|
|2  |3  |   |
|---+---+---|
|9  |   |3  |
| 2 | 7 |64 |
| 3 | 5 |8  |
-------------");

    PushState(); // save the original data
    if(Solve())
    {
      PrintBoard(); // display the solution
      Console.WriteLine("Puzzle solved!");
    }
    else
    {
      PopState(); // display the original data
      PrintBoard();
      Console.WriteLine("Unable to solve this puzzle!");
    }
    Console.WriteLine("Press a key to exit...");
    Console.ReadKey();
  }

  /// <summary>Gets the cell value at the given coordinates.</summary>
  static ushort Get(int x, int y)
  {
    return state[y*BoardLength+x];
  }

  /// <summary>Sets the cell value at the given index, and updates affected cells.</summary>
  /// <returns>Returns true if this results in a valid board.</returns>
  static bool Set(int i, ushort value)
  {
    return Set(i%BoardLength, i/BoardLength, value);
  }

  /// <summary>Sets the cell value at the given coordinates, and updates affected cells.</summary>
  /// <returns>Returns true if this results in a valid board.</returns>
  static bool Set(int column, int row, ushort value)
  {
    int index = row*BoardLength+column;

    // prevent infinite recursion by returning if the value already matches
    if(state[index] == value) return true;

    state[index] = value;
    if(IsDefinite(value)) // if the new value is definite, it will affect other cells
    {
      for(int x=0; x<BoardLength; x++) // update the other cells in the row
      {
        if(x != column && !TryUpdateConstraint(x, row, value)) return false;
      }

      for(int y=0; y<BoardLength; y++) // update the other cells in the column
      {
        if(y != row && !TryUpdateConstraint(column, y, value)) return false;
      }

      int blockX = column/BlockSize, blockY = row/BlockSize;
      for(int y=0; y<BlockSize; y++) // update the other cells in the block
      {
        for(int x=0; x<BlockSize; x++)
        {
          int rx = blockX*BlockSize+x, ry = blockY*BlockSize+y;
          if((rx != column || ry != row) && !TryUpdateConstraint(rx, ry, value)) return false;
        }
      }
    }

    return true;
  }
  
  /// <summary>Tries to update a cell at the given coordinates, given a new
  /// value that was inserted into a related cell.
  /// </summary>
  static bool TryUpdateConstraint(int x, int y, ushort value)
  {
    ushort mask = Get(x, y);
    if(mask != 0) // if the cell already has a value, update it. (the only time it won't
    {             // have a value is during the initial setting of the board state)
      mask &= (ushort)~value;
      return mask != 0 && Set(x, y, mask); // if it becomes zero, the puzzle becomes unsolvable, so return false
    }
    else return true; // if the cell has no value, assume it'll be set later
  }

  /// <summary>Returns the number of bits set in the given cell value. This is equal to the
  /// number of possible digits that could go in the cell.
  /// </summary>
  static int BitCount(ushort value)
  {
    int count = 0;
    while(value != 0)
    {
      if((value&1) != 0) count++;
      value >>= 1;
    }
    return count;
  }

  /// <summary>Returns a mask corresponding to the Nth possible digit for a given cell.</summary>
  /// <param name="value">The cell value.</param>
  /// <param name="bit">The number of the bit to return, from 0 to BitCount(value)-1.</param>
  static ushort GetBitValue(ushort value, int bit)
  {
    ushort mask = 1;
    Debug.Assert(bit >= 0 && BitCount(value) > bit); // make sure the bit index is within range
    while(true)
    {
      while((value&mask) == 0) mask <<= 1;
      if(bit-- == 0) break;
      mask <<= 1;
    }
    return mask;
  }

  /// <summary>Gets the index of the first unsolved cell -- ie, the first cell without a
  /// definite value.
  /// </summary>
  /// <returns>True if an unsolved cell was found, and false if not.</returns>
  static bool GetUnsolved(out int index)
  {
    for(int i=0; i<BoardSize; i++)
    {
      if(!IsDefinite(state[i]))
      {
        index = i;
        return true;
      }
    }
    index = -1;
    return false;
  }

  /// <summary>Saves the current board state on a stack.</summary>
  static void PushState()
  {
    stack.Push(state);
    state = (ushort[])state.Clone();
  }

  /// <summary>Restores the previous board state.</summary>
  static void PopState()
  {
    state = stack.Pop();
  }

  /// <summary>Attempts to solve the puzzle and returns true if it could be solved.</summary>
  static bool Solve()
  {
    // we'll find the first unsolved cell. if there isn't one, the puzzle is
    // already solved.
    int index;
    if(!GetUnsolved(out index)) return true;

    // try each possible digit in the unsolved cell (and update surrounding cells),
    // and recursively attempt to solve the resulting puzzle. if we come to an impossible
    // state, we'll backtrack.
    for(int b=BitCount(state[index])-1; b >= 0; b--)
    {
      PushState();
      if(Set(index, GetBitValue(state[index], b)) && Solve()) return true;
      PopState();
    }

    // if no digits in the unsolved cell are possible, this puzzle is unsolvable
    return false;
  }

  /// <summary>Determines whether the given cell value is definite -- ie, it has only one bit set.</summary>
  static bool IsDefinite(ushort value)
  {
    return (value & (value-1)) == 0 && value != 0;
  }

  /// <summary>Prints the board to the screen.</summary>
  static void PrintBoard()
  {
    string separator = new string('-', BoardLength*Digits + BoardLength+1);
    for(int y=0; y<BoardLength; y++)
    {
      if(y%BlockSize == 0) Console.WriteLine(separator);
      for(int x=0; x<BoardLength; x++)
      {
        Console.Write(x%BlockSize == 0 ? '|' : ' ');
        Console.Write(ToString(Get(x, y)));
      }
      Console.Write("|\n");
    }
    Console.WriteLine(separator);
  }

  /// <summary>Sets the current state based on a string description of the board.</summary>
  /// <param name="s">A string containing board information. Spaces and digits are filled in
  /// as board cells. All other characters are ignored.
  /// </param>
  static void SetState(string s)
  {
    // initialize the board to have every cell able to contain any digit
    for(int i=0; i<BoardSize; i++) state[i] = FullCell;

    int bi=0;
    for(int si=0; bi<BoardSize; si++)
    {
      char c = s[si];
      if(c == ' ') bi++;
      else if(char.IsDigit(c) && !Set(bi++, (ushort)(1 << (c-'1'))))
      {
        // this puzzle is impossible. empty the cell to prevent it from appearing solved
        state[bi-1] = (ushort)0;
      }
    }
    Debug.Assert(bi == BoardSize); // make sure the whole board was filled
  }

  /// <summary>Converts a cell value to string containing the digits that could possibly exist in that cell. The string
  /// will be padded with spaces to the maximum string length.
  /// </summary>
  static string ToString(ushort cell)
  {
    const string chars = "123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";
    char[] buf = new char[Digits];

    int j=0;
    for(int i=0; i<Digits; i++) // for each digit, if the bit is set, add it to the buffer
    {
      if(((cell >> i) & 1) != 0) buf[j++] = chars[i];
    }
    
    string digits = new string(buf, 0, j);
    // return the digits, centered within a 9-character string
    return new string(' ', (Digits-j)/2) + digits + new string(' ', (Digits-j+1)/2);
  }
  
  /// <summary>The current board state.</summary>
  static ushort[] state = new ushort[BoardSize];
  /// <summary>A stack of saved board states.</summary>
  static Stack<ushort[]> stack = new Stack<ushort[]>();
}

} // namespace Sudoku