#include <vector>
#include <string>
#include <iostream>

bool possible(unsigned i, char n, std::string& grid) //check if is possible placing element 'n' in 'i' position of the string
{
  //the controls must be done relative to columns and rows, so it's necessary converting 'i' to the relative col and row
  unsigned c = i % 9;
  unsigned r = i / 9;
  unsigned c0 = (c / 3) * 3, r0 = (r / 3) * 3;
  
  for(unsigned k = 0; k < 9; k++)
    if(grid[9 * r + k] == n || grid[9 * k + c] == n || grid[9 * (r0 + k / 3) + (c0 + k % 3)] == n) 
      return false;
  return true;
}

bool backtrack(std::string& grid) //recursively try to fill the scheme with possible solutions, till it fills the whole scheme
{
  for(unsigned i = 0; i < 81; i++)
    if(grid[i] == '0')
    {
      for(char n = '1'; n <= '9'; n++)
      if(possible(i, n, grid))
        {
          grid[i] = n;
          if(backtrack(grid)) return true;
          grid[i] = '0';
        }
      return false;
    }
  return true;
}

std::string solve_sudoku(std::string puzzleString)
{
  backtrack(puzzleString);
  return puzzleString;
}

#include <vector>
#include <string>

/* Sudokus are good examples for backtracking 
*  The algorithm try to place numbers in the empty spots untill it can or untill it solves the puzzle
*/

/* The first function determine if, in the grid "grid" at position x and y an n is acceptable. 
*  The k is used to iterate each subset: row, column and square, where x0 and y0 are the coordinates of the top left corner of the square
*/
bool possible(unsigned x, unsigned y, int n, std::vector<std::vector<int>>& grid)
{
  unsigned x0 = (x / 3) * 3, y0 = (y / 3) * 3;
  for(unsigned k = 0; k < 9; k++)
    if(grid[y][k] == n || grid[k][x] == n || grid[y0 + k / 3][x0 + k % 3] == n) 
      return false;
  return true;
}

/* The backtracking function is a recursive function! each call keeps track of it's own x and y coordinates.
*  The function operates on a referenced grid. It scans each xy couple and, if it's zero, it tryes to put a number, checked with the "possible" funciton.
*  If the number is ok, then the function call itself.
*  Now, if the recursion find a solution then returns true so all the parent calls know the solution has been found. Otherwise, the parent function try to
*  go ahead and try another possible number.
*/
bool backtrack(std::vector<std::vector<int>>& grid)
{
  for(unsigned y = 0; y < 9; y++)
    for(unsigned x = 0; x < 9; x++)
      if(grid[y][x] == 0)
      {
        for(unsigned n = 1; n <= 9; n++)
          if(possible(x, y, n, grid))
          {
            grid[y][x] = n;
            if(backtrack(grid)) return true;
            grid[y][x] = 0;
          }
        return false;
      }
  return true;
}

/* The main function parses the string (Why the string tho?) and then parses the solution.
*  In this case, it won't check if a puzzle is impossible to solbe
*/
std::string solve_sudoku(std::string puzzleString)
{
  std::vector<std::vector<int>> puzzle(9, std::vector<int>(9, 0));
  
  for(unsigned i = 0; i < 81; i++)
    puzzle[i / 9][i % 9] = puzzleString[i] - '0';
  
  backtrack(puzzle);
  
  std::string out = "";
  for(auto& i : puzzle)
    for(auto& j : i)
      out += std::to_string(j);
  return out;
}