class SudokuSolver
  SIZE = 9

  def initialize(board)
    @board = board
  end

  def solve
    row, col = find_empty_cell
    return true if row.nil? # No empty cell means solved

    (1..9).each do |num|
      if valid?(num, row, col)
        @board[row][col] = num
        return true if solve
        @board[row][col] = 0 # backtrack
      end
    end
    false
  end

  def print_board
    @board.each do |row|
      puts row.map { |val| val == 0 ? '.' : val }.join(' ')
    end
  end

  private

  def find_empty_cell
    (0...SIZE).each do |r|
      (0...SIZE).each do |c|
        return [r, c] if @board[r][c] == 0
      end
    end
    nil
  end

  def valid?(num, row, col)
    # Check row
    return false if @board[row].include?(num)
    # Check column
    return false if @board.transpose[col].include?(num)
    # Check 3x3 grid
    box_row_start = (row / 3) * 3
    box_col_start = (col / 3) * 3
    (box_row_start...(box_row_start+3)).each do |r|
      (box_col_start...(box_col_start+3)).each do |c|
        return false if @board[r][c] == num
      end
    end
    true
  end
end

# 10 Test Boards
test_boards = [
  # Example 1
  [
    [5,3,0,0,7,0,0,0,0],
    [6,0,0,1,9,5,0,0,0],
    [0,9,8,0,0,0,0,6,0],
    [8,0,0,0,6,0,0,0,3],
    [4,0,0,8,0,3,0,0,1],
    [7,0,0,0,2,0,0,0,6],
    [0,6,0,0,0,0,2,8,0],
    [0,0,0,4,1,9,0,0,5],
    [0,0,0,0,8,0,0,7,9]
  ],
  # The examples below are comment out because of the slow performance of ruby
  # Example 2
  # [
  #   [0,0,0,0,0,0,0,0,0],
  #   [0,0,0,0,0,3,0,8,5],
  #   [0,0,1,0,2,0,0,0,0],
  #   [0,0,0,0,0,0,0,0,7],
  #   [0,0,0,0,1,0,0,0,0],
  #   [3,0,0,0,0,0,0,0,0],
  #   [0,0,0,0,4,0,1,0,0],
  #   [5,7,0,0,0,0,0,0,0],
  #   [0,0,0,0,0,0,0,0,0]
  # ],
  # # Example 3
  # [
  #   [1,0,0,0,0,7,0,9,0],
  #   [0,3,0,0,2,0,0,0,8],
  #   [0,0,9,6,0,0,5,0,0],
  #   [0,0,5,3,0,0,9,0,0],
  #   [0,1,0,0,0,0,0,0,2],
  #   [0,0,6,0,0,3,0,0,0],
  #   [0,6,0,0,0,0,0,0,0],
  #   [0,0,0,0,0,0,0,0,0],
  #   [0,0,0,0,0,0,0,0,0]
  # ],
  # # Example 4
  # [
  #   [0,0,0,2,6,0,7,0,1],
  #   [6,8,0,0,7,0,0,9,0],
  #   [1,9,0,0,0,4,5,0,0],
  #   [8,2,0,1,0,0,0,4,0],
  #   [0,0,4,6,0,2,9,0,0],
  #   [0,5,0,0,0,3,0,2,8],
  #   [0,0,9,3,0,0,0,7,4],
  #   [0,4,0,0,5,0,0,3,6],
  #   [7,0,3,0,1,8,0,0,0]
  # ],
  # # Example 5
  # [
  #   [0,0,0,0,0,0,0,0,0],
  #   [0,0,0,0,0,3,0,8,5],
  #   [0,0,1,0,2,0,0,0,0],
  #   [0,0,0,0,0,0,0,0,7],
  #   [0,0,0,0,1,0,0,0,0],
  #   [3,0,0,0,0,0,0,0,0],
  #   [0,0,0,0,4,0,1,0,0],
  #   [5,7,0,0,0,0,0,0,0],
  #   [0,0,0,0,0,0,0,0,0]
  # ],
  # # Example 6
  # [
  #   [0,0,0,0,0,0,0,0,6],
  #   [0,0,0,0,0,3,0,0,0],
  #   [0,0,1,0,2,0,0,0,0],
  #   [0,0,0,0,6,0,0,0,3],
  #   [4,0,0,8,0,3,0,0,1],
  #   [7,0,0,0,2,0,0,0,6],
  #   [0,6,0,0,0,0,2,8,0],
  #   [0,0,0,4,1,9,0,0,5],
  #   [0,0,0,0,8,0,0,7,9]
  # ],
  # # Example 7
  # [
  #   [9,0,0,0,0,0,0,0,5],
  #   [0,1,0,0,0,5,0,0,0],
  #   [0,0,0,3,0,0,0,8,0],
  #   [0,0,0,0,0,6,0,0,0],
  #   [0,0,0,0,0,0,2,0,0],
  #   [3,0,7,0,0,0,0,0,1],
  #   [0,6,0,0,0,0,0,9,0],
  #   [0,0,0,4,0,0,0,0,0],
  #   [0,0,0,0,0,0,0,0,0]
  # ],
  # # Example 8
  # [
  #   [2,0,0,0,0,0,0,0,0],
  #   [0,0,0,0,0,3,0,8,5],
  #   [0,0,1,0,2,0,0,0,0],
  #   [0,0,0,0,0,0,0,0,7],
  #   [0,0,0,0,1,0,0,0,0],
  #   [3,0,0,0,0,0,0,0,0],
  #   [0,0,0,0,4,0,1,0,0],
  #   [5,7,0,0,0,0,0,0,0],
  #   [0,0,0,0,0,0,0,0,0]
  # ],
  # # Example 9
  # [
  #   [0,0,0,0,7,0,0,0,0],
  #   [6,0,0,1,9,5,0,0,0],
  #   [0,9,8,0,0,0,0,6,0],
  #   [8,0,0,0,6,0,0,0,3],
  #   [4,0,0,8,0,3,0,0,1],
  #   [7,0,0,0,2,0,0,0,6],
  #   [0,6,0,0,0,0,2,8,0],
  #   [0,0,0,4,1,9,0,0,5],
  #   [0,0,0,0,8,0,0,7,0]
  # ],
  # # Example 10
  # [
  #   [0,0,0,4,0,0,0,0,0],
  #   [0,0,0,0,0,3,0,8,5],
  #   [0,2,1,0,0,0,0,0,0],
  #   [0,0,0,0,0,0,0,0,7],
  #   [0,0,0,0,1,0,0,0,0],
  #   [3,0,0,0,0,0,0,0,0],
  #   [0,0,0,0,4,0,1,0,0],
  #   [5,7,0,0,0,0,0,0,0],
  #   [0,0,0,0,0,0,0,0,0]
  # ]
]

test_boards.each_with_index do |board, i|
  puts "Test Sudoku ##{i+1} (Before):"
  solver = SudokuSolver.new(board)
  solver.print_board
  if solver.solve
    puts "Solved Sudoku ##{i+1}:"
    solver.print_board
  else
    puts "No solution found for Sudoku ##{i+1}."
  end
  puts "-----------------------------------------"
end
