<p>Write a program to solve a Sudoku puzzle by filling the empty cells.</p>

<p>A sudoku solution must satisfy <strong>all of the following rules</strong>:</p>

<ol>
	<li>Each of the digits <code>1-9</code> must occur exactly once in each row.</li>
	<li>Each of the digits <code>1-9</code> must occur exactly once in each column.</li>
	<li>Each of the digits <code>1-9</code> must occur exactly once in each of the 9 <code>3x3</code> sub-boxes of the grid.</li>
</ol>

<p>The <code>&#39;.&#39;</code> character indicates empty cells.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img src="https://upload.wikimedia.org/wikipedia/commons/thumb/f/ff/Sudoku-by-L2G-20050714.svg/250px-Sudoku-by-L2G-20050714.svg.png" style="height:250px; width:250px" />
<pre>
<strong>Input:</strong> board = [[&quot;5&quot;,&quot;3&quot;,&quot;.&quot;,&quot;.&quot;,&quot;7&quot;,&quot;.&quot;,&quot;.&quot;,&quot;.&quot;,&quot;.&quot;],[&quot;6&quot;,&quot;.&quot;,&quot;.&quot;,&quot;1&quot;,&quot;9&quot;,&quot;5&quot;,&quot;.&quot;,&quot;.&quot;,&quot;.&quot;],[&quot;.&quot;,&quot;9&quot;,&quot;8&quot;,&quot;.&quot;,&quot;.&quot;,&quot;.&quot;,&quot;.&quot;,&quot;6&quot;,&quot;.&quot;],[&quot;8&quot;,&quot;.&quot;,&quot;.&quot;,&quot;.&quot;,&quot;6&quot;,&quot;.&quot;,&quot;.&quot;,&quot;.&quot;,&quot;3&quot;],[&quot;4&quot;,&quot;.&quot;,&quot;.&quot;,&quot;8&quot;,&quot;.&quot;,&quot;3&quot;,&quot;.&quot;,&quot;.&quot;,&quot;1&quot;],[&quot;7&quot;,&quot;.&quot;,&quot;.&quot;,&quot;.&quot;,&quot;2&quot;,&quot;.&quot;,&quot;.&quot;,&quot;.&quot;,&quot;6&quot;],[&quot;.&quot;,&quot;6&quot;,&quot;.&quot;,&quot;.&quot;,&quot;.&quot;,&quot;.&quot;,&quot;2&quot;,&quot;8&quot;,&quot;.&quot;],[&quot;.&quot;,&quot;.&quot;,&quot;.&quot;,&quot;4&quot;,&quot;1&quot;,&quot;9&quot;,&quot;.&quot;,&quot;.&quot;,&quot;5&quot;],[&quot;.&quot;,&quot;.&quot;,&quot;.&quot;,&quot;.&quot;,&quot;8&quot;,&quot;.&quot;,&quot;.&quot;,&quot;7&quot;,&quot;9&quot;]]
<strong>Output:</strong> [[&quot;5&quot;,&quot;3&quot;,&quot;4&quot;,&quot;6&quot;,&quot;7&quot;,&quot;8&quot;,&quot;9&quot;,&quot;1&quot;,&quot;2&quot;],[&quot;6&quot;,&quot;7&quot;,&quot;2&quot;,&quot;1&quot;,&quot;9&quot;,&quot;5&quot;,&quot;3&quot;,&quot;4&quot;,&quot;8&quot;],[&quot;1&quot;,&quot;9&quot;,&quot;8&quot;,&quot;3&quot;,&quot;4&quot;,&quot;2&quot;,&quot;5&quot;,&quot;6&quot;,&quot;7&quot;],[&quot;8&quot;,&quot;5&quot;,&quot;9&quot;,&quot;7&quot;,&quot;6&quot;,&quot;1&quot;,&quot;4&quot;,&quot;2&quot;,&quot;3&quot;],[&quot;4&quot;,&quot;2&quot;,&quot;6&quot;,&quot;8&quot;,&quot;5&quot;,&quot;3&quot;,&quot;7&quot;,&quot;9&quot;,&quot;1&quot;],[&quot;7&quot;,&quot;1&quot;,&quot;3&quot;,&quot;9&quot;,&quot;2&quot;,&quot;4&quot;,&quot;8&quot;,&quot;5&quot;,&quot;6&quot;],[&quot;9&quot;,&quot;6&quot;,&quot;1&quot;,&quot;5&quot;,&quot;3&quot;,&quot;7&quot;,&quot;2&quot;,&quot;8&quot;,&quot;4&quot;],[&quot;2&quot;,&quot;8&quot;,&quot;7&quot;,&quot;4&quot;,&quot;1&quot;,&quot;9&quot;,&quot;6&quot;,&quot;3&quot;,&quot;5&quot;],[&quot;3&quot;,&quot;4&quot;,&quot;5&quot;,&quot;2&quot;,&quot;8&quot;,&quot;6&quot;,&quot;1&quot;,&quot;7&quot;,&quot;9&quot;]]
<strong>Explanation:</strong>&nbsp;The input board is shown above and the only valid solution is shown below:

<img src="https://upload.wikimedia.org/wikipedia/commons/thumb/3/31/Sudoku-by-L2G-20050714_solution.svg/250px-Sudoku-by-L2G-20050714_solution.svg.png" style="height:250px; width:250px" />
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>board.length == 9</code></li>
	<li><code>board[i].length == 9</code></li>
	<li><code>board[i][j]</code> is a digit or <code>&#39;.&#39;</code>.</li>
	<li>It is <strong>guaranteed</strong> that the input board has only one solution.</li>
</ul>

constexpr int rowSkip = 9; // 9 best without aligning
class Solution {
public:

    inline
    const int countBits(const uint16_t val) const noexcept
    {
        int result = 0;
        constexpr uint16_t one = 1;
        for(int i=1;i<10;i++)
            result += (val>>i)&one;
        return result;
    }
    // if a cell has a value defined, remove it from all other cells possibilities
    // (horizontal line, vertical line, the 3x3 tile)
    void removePossibility(uint16_t * table, const int i, const int j, const int num) noexcept
    {
        const int row = i;
        const int col = j;
        const int tileRow = i / 3;
        const int tileCol = j / 3;
        // selected cell now has only 1 possibility which is num
        const uint16_t one = 1;
        #pragma GCC ivdep
        for(int i=1;i<=9;i++)
        {
            if(num != i)
                table[row*rowSkip+col] &= ~(one<<i);
        }

        for(int i=0;i<9;i++)
        {
            // remove from row
            if(i != col)
                table[row*rowSkip+i] &= ~(one<<num);

            // remove from col
            if(i != row)
                table[i*rowSkip+col] &= ~(one<<num);

            // remove from 3x3 tile
            const int iX = i % 3;
            const int iY = i / 3;
            const int iXX = tileCol * 3 + iX;
            const int iYY = tileRow * 3 + iY;

            // this makes redundant erasing after row/col but it should be ok
            if(iYY != row && iXX != col)
                table[iYY*rowSkip+iXX] &= ~(one<<num);
        }
    }

    // checks neighbors to find highest possible numbers for selected cell
    const std::vector<char> findHighestPossibility(const uint16_t * table, const int i, const int j) const noexcept
    {
        // for each duplicate found in neighbors possibility lists, remove 1 from relevant number
        // then find the highest number's index
        alignas(64)
        char poss[10]={-100,-100,-100,-100,-100,-100,-100,-100,-100,-100};
        const int row = i;
        const int col = j;
        const int tileRow = i / 3;
        const int tileCol = j / 3;
        constexpr uint16_t one = 1;
        #pragma GCC ivdep
        for(int i=1;i<10;i++)
        {
            
            if( ((table[row*rowSkip+col]>>i) & one) == one)
                    poss[i]=-10;
        }
        for(int i=0;i<9;i++)
        {
            // check row
            if(i != col)
            {
                #pragma GCC ivdep
                for(int ii=1;ii<10;ii++)
                {
                    if( ((table[row*rowSkip+i]>>ii) & one) == one)
                        if(poss[ii]!=-100)
                            poss[ii]++;
                }
            }
            // check col
            if(i != row)
            {
                #pragma GCC ivdep
                for(int ii=1;ii<10;ii++)
                {
                    if( ((table[i*rowSkip+col]>>ii) & one) == one)
                        if(poss[ii]!=-100)
                            poss[ii]++;
                }
            }

            // check 3x3 tile
            const int iX = i % 3;
            const int iY = i / 3;
            const int iXX = tileCol * 3 + iX;
            const int iYY = tileRow * 3 + iY;

            // this makes redundant decrement but it should be ok since its a bias on only 4 cells
            if(iYY != row && iXX != col)
            {
                #pragma GCC ivdep
                for(int ii=1;ii<10;ii++)
                {
                    if( ((table[iYY*rowSkip+iXX]>>ii) & one) == one)
                        if(poss[ii]!=-100)
                            poss[ii]++;
                }
            }
        }

        int iFound = -1;
        int tmp = -1;
        for(int i=1;i<=9;i++)
        {
            if(poss[i-1]!=-100)
            if(tmp<poss[i-1])
            {
                tmp = poss[i-1];
                iFound = i-1;
            }
        }
        std::vector<char> result;

        std::vector<std::pair<int, int>> pairs;
        for (int i=0;i<10;i++)
            if(poss[i]!=-100)
                pairs.push_back(std::pair<int,int>(i,poss[i]));

        std::sort(pairs.begin(), pairs.end(), [=](std::pair<int, int>& a, std::pair<int, int>& b)
        {
            return a.second > b.second;
        }
        );


        for(auto e:pairs)
            result.push_back(e.first);

        return result;
    }

    inline
    const bool checkRowVal(const uint16_t * table, const int row) const noexcept
    {
        std::vector<char> tmp(9);
        constexpr uint16_t one = 1;
        for(int i=0;i<9;i++)
        {
            for(int ii=1;ii<10;ii++)
            {
                if( ((table[row*rowSkip+i]>>ii) & one) == one)
                    tmp[i]=ii;
            }
    
        }
        for(int i=0;i<9;i++)
        {
            if(tmp[i]<1 || tmp[i]>9)
                return false;
        }
        return true;
    }

    inline
    const bool checkRow(const uint16_t * table, const int row) const noexcept
    {
        std::vector<char> tmp(9);
        constexpr uint16_t one = 1;
        for(int i=0;i<9;i++)
        {
            for(int ii=1;ii<10;ii++)
            {
                if( ((table[row*rowSkip+i]>>ii) & one) == one)
                    tmp[i]=ii;
            }
           
        }
        for(int i=0;i<9;i++)
            for(int j=0;j<9;j++)
            {
                if(i!=j && tmp[i]==tmp[j])
                    return false;
            }
        return true;
    }

    inline
    const bool checkCol(const uint16_t * table, const int col) const noexcept
    {
        std::vector<char> tmp(9);
        constexpr uint16_t one = 1;
        for(int i=0;i<9;i++)
        {
            for(int ii=1;ii<10;ii++)
            {
                if( ((table[i*rowSkip+col]>>ii) & one) == one)
                    tmp[i]=ii;
            }
        }
        for(int i=0;i<9;i++)
            for(int j=0;j<9;j++)
            {
                if(i!=j && tmp[i]==tmp[j])
                    return false;
            }
        return true;
    }

    inline
    const bool checkTile(const uint16_t * table, const int tile) const noexcept
    {
        std::vector<char> tmp(9);
        constexpr uint16_t one = 1;
        const int tx = tile % 3;
        const int ty = tile / 3;
        const int txx=tx * 3;
        const int tyy=ty * 3;
        for(int i=0;i<9;i++)
        {
            const int ix = i%3;
            const int iy = i/3;
            const int indexX = ix + txx;
            const int indexY = iy + tyy;

            for(int ii=1;ii<10;ii++)
            {
                if( ((table[indexX+indexY*rowSkip]>>ii) & one) == one)
                    tmp[i]=ii;
            }
        
        }
        for(int i=0;i<9;i++)
            for(int j=0;j<9;j++)
            {
                if(i!=j && tmp[i]==tmp[j])
                    return false;
            }
        return true;
    }

    inline
    const bool isValid(const uint16_t *  table) const noexcept
    {
        for(int i=0;i<9;i++)
            for(int j=0;j<9;j++)
                if(countBits(table[i*rowSkip+j]) != 1)
                    return false;
     

        for(int i=0;i<9;i++)
        {
            if(!checkRowVal(table,i))
                return false;
            if(!checkRow(table,i))
                return false;
            if(!checkCol(table,i))
                return false;
            if(!checkTile(table,i))
                return false;
        }
        return true;
    }

    
    void recursivePath(uint16_t * cache, int & cacheIndex, const std::vector<std::vector<int>> & posi,const int id, uint16_t * table, std::vector<uint16_t> * result, bool * complete)
    {
        //static int t=0;
        //t++;

        if(isValid(table))
        {
            if(!*complete)
            {
                for(int i=0;i<rowSkip*9;i++)
                    (*result)[i] = table[i];
                *complete=true;//std::cout<<t<<std::endl;
            }
        }
        else if(id<81)
        {
            const int i = posi[id][1] / rowSkip;
            const int j = posi[id][1] % rowSkip;
            auto val = findHighestPossibility(table, i, j);
            
            for(auto & e:val)
            {               
                if(*complete)
                    return;
                if(id+1<81)
                {
                    if(cacheIndex<50000)
                    {
                        for(int i=0;i<rowSkip*9;i++)
                            cache[cacheIndex*rowSkip*9+i] = table[i]; 
                        uint16_t * c = &cache[cacheIndex*rowSkip*9];
                        removePossibility(c,i,j,e);
                        cacheIndex++;
                        recursivePath(cache,cacheIndex,posi,id+1,c,result,complete);
                    }
                    else
                    {
                        std::vector<uint16_t> table2(rowSkip*9);
                        for(int i=0;i<rowSkip*9;i++)
                            table2[i]=table[i];
                        removePossibility(table2.data(),i,j,e);
                        cacheIndex++;
                        recursivePath(cache,cacheIndex,posi,id+1,table2.data(),result,complete);
                    }
                }
            }
        }
    }
    #pragma GCC push_options
    #pragma GCC optimize ("-march=native")
    #pragma GCC optimize ("-ftree-vectorize")
    #pragma GCC optimize ("-fno-math-errno")
    void solveSudoku(vector<vector<char>>& board) {

        // create & fill possibility table (3D, 9 possibilities per cell, 1,..,9)
        std::vector<uint16_t> table;
        std::vector<uint16_t> result;
        std::vector<uint16_t> cache(50000*rowSkip*9+16);
        size_t ofset = 0;
        while(  (((size_t)cache.data()) + ofset) % 16 != 0)
            ofset++;

        int cacheIndex=0;
        bool complete = false;
        table.resize(rowSkip*9);
        const uint16_t one = 1;
        for(int i=0;i<9;i++)
        {

            for(int j=0;j<9;j++)
            {
                for(int k=1;k<=9;k++)
                    table[i*rowSkip+j] |= (one<<k);                    
            }
        }
        result = table;

        for(int i=0;i<9;i++)
        {
            for(int j=0;j<9;j++)
            {
                if(board[i][j]>='1' && board[i][j]<='9')
                    removePossibility(table.data(),i,j,board[i][j]-'0');
            }
        }

        // sort paths on their number of possibilities (single possibilities first)
        std::vector<std::vector<int>> posi;
        for(int i=0;i<9;i++)
        {
            for(int j=0;j<9;j++)
            {
                posi.push_back({countBits(table[i*rowSkip+j]),i*rowSkip+j});
            }
        }
        std::sort(posi.data(),posi.data()+posi.size(),[&](std::vector<int>&e1,std::vector<int>&e2){
            return e1[0]<e2[0];
        });

        recursivePath(cache.data()+ofset,cacheIndex,posi,0,table.data(),&result,&complete);

   
        for(int i=0;i<9;i++)
        {
            for(int j=0;j<9;j++)
            {
                for(int ii=1;ii<10;ii++)
                {
                    if( ((result[i*rowSkip+j]>>ii) & one) == one)
                    {
                        board[i][j]=ii+'0';
                        break;
                    }
                }

            }
        }
    }
    #pragma GCC pop_options
};
68340