# LeetCode 37. Sudoku Solver

## Description:

Write a program to solve a Sudoku puzzle by filling the empty cells.

A sudoku solution must satisfy all of the following rules:

• Each of the digits 1-9 must occur exactly once in each row.
• Each of the digits 1-9 must occur exactly once in each column.
• Each of the the digits 1-9 must occur exactly once in each of the nine 3x3 sub-boxes of the grid.

Empty cells are indicated by the character ‘.’.

## Note:

• The given board contain only digits 1-9 and the character ‘.’.
• You may assume that the given Sudoku puzzle will have a single unique solution.
• The given board size is always 9x9.

## Solution:

import operator

# the 9 blocks on sudoku board are denoted by integral id, i.e. 0, 1, 2, ..., 8, respectively
# these two methods provides translation between absolute position and corresponding block id

def GetBlockTopLeft(blockId):
row = int(blockId / 3)
col = blockId - row * 3;
return 3 * row, 3 * col

def GetBlockId(pos):
row = int(pos[0] / 3)
col = int(pos[1] / 3)
return row * 3 + col

# determines what number can be filled in each cell of the sudoku problem
class Freedom:
# we store the freedom of each row, each col and each block
# for each cell, the number that can be filled in is the intersection
# of the number that can be filled within its row, its col and its block

rowFreedom = None
colFreedom = None
blockFreedom = None

def Init(self, board):
self.rowFreedom = [set(range(1, 10)) for _ in range(9)]
self.colFreedom = [set(range(1, 10)) for _ in range(9)]
self.blockFreedom = [set(range(1, 10)) for _ in range(9)]

for i in range(9):
for j in range(9):
if board[i][j] != '.':
self.rowFreedom[i].remove(ord(board[i][j]) - ord('0'))
if board[j][i] != '.':
self.colFreedom[i].remove(ord(board[j][i]) - ord('0'))

for i in range(9):
topLeft = GetBlockTopLeft(i);
for j in range(3):
for k in range(3):
if board[topLeft[0] + j][topLeft[1] + k] !=  '.':
self.blockFreedom[i].remove(ord(board[topLeft[0] + j][topLeft[1] + k]) - ord('0'))

# one good thing to use set intersection is that it only takes linear time
def GetFreedom(self, pos):
return self.rowFreedom[pos[0]].intersection(self.colFreedom[pos[1]]).intersection(self.blockFreedom[GetBlockId(pos)])

def StepForward(self, pos, step):
self.rowFreedom[pos[0]].remove(step)
self.colFreedom[pos[1]].remove(step)
self.blockFreedom[GetBlockId(pos)].remove(step)

def StepBack(self, pos, step):

class Solution:
def solveSudoku(self, board):
"""
:type board: List[List[str]]
:rtype: void Do not return anything, modify board in-place instead.
"""
freedom = Freedom()
freedom.Init(board)

# find out the cells to be filled
iterList = []

for i in range(9):
for j in range(9):
if board[i][j] == '.':
pos = (i, j)
iterList.append((pos, len(freedom.GetFreedom(pos))))

# we want to sort the cells by degree of freedom
# and start backtracking with the position with the least freedom
iterList.sort(key = operator.itemgetter(1))
# stores the result
resultDict = {}
# we want to pass this variable by reference
solved = [False]

self.RecursiveSolve(iterList, 0, freedom, resultDict, solved)

# modify the board
for key, val in resultDict.items():
board[key[0]][key[1]] = repr(val)

def RecursiveSolve(self, iterList, depth, freedom, resultDict, solved):

# we have reached a solution
if depth == len(iterList):
solved[0] = True
return

curPos = iterList[depth][0]

# compute the possible candidates
# if there is none, then the current guess is wrong
possibility = freedom.GetFreedom(curPos)
if len(possibility) == 0:
return

for guess in possibility:
# store the candidate
resultDict[curPos] = guess
# update freedom info
freedom.StepForward(curPos, guess)
self.RecursiveSolve(iterList, depth + 1, freedom, resultDict, solved)
# if a solution is reached, set solved[0] to be true so that we can exit
# the loop
if solved[0]:
return
# if that was not a valid solution, we need to roll back the modification
# done to the freedom info
freedom.StepBack(curPos, guess)
# delete the candidate
del resultDict[curPos]

if depth == 0:
raise RuntimeError('unable to solve')


inline pair<int, int> GetBlockTopLeft(int blockId){
int row = blockId / 3;
int col = blockId - 3 * row;
return make_pair(3 * row, 3 * col);
}

inline int GetBlockId(const pair<int, int> &pos){
int row = pos.first / 3;
int col = pos.second / 3;
return 3 * row + col;
}

class Solution {

struct Freedom {
vector<set<int>> rowFreedom;
vector<set<int>> colFreedom;
vector<set<int>> blockFreedom;

void Init(const vector<vector<char>>& board) {
vector<int> allInt;
for (auto i = 1; i < 10; ++i)allInt.push_back(i);

rowFreedom.resize(9, set<int>{allInt.begin(), allInt.end()});
colFreedom.resize(9, set<int>{allInt.begin(), allInt.end()});
blockFreedom.resize(9, set<int>{allInt.begin(), allInt.end()});

for(auto i = 0; i < 9; ++i){
for(auto j = 0; j < 9; ++j){
if(board[i][j] != '.')rowFreedom[i].erase(board[i][j] - '0');
if(board[j][i] != '.')colFreedom[i].erase(board[j][i] - '0');
}
}

for(auto i = 0; i < 9; ++i){
auto topLeft = GetBlockTopLeft(i);

for(auto j = 0; j < 3; ++j){
for(auto k = 0; k < 3; ++k){
if(board[topLeft.first + j][topLeft.second + k] != '.'){
blockFreedom[i].erase(board[topLeft.first + j][topLeft.second + k] - '0');
}
}
}

}

}

vector<int> GetFreedom(const pair<int, int> &pos) const{
vector<int> phase1;
set_intersection(rowFreedom[pos.first].begin(), rowFreedom[pos.first].end(),
colFreedom[pos.second].begin(), colFreedom[pos.second].end(), back_inserter(phase1));
vector<int> phase2;
set_intersection(phase1.begin(), phase1.end(),
blockFreedom[GetBlockId(pos)].begin(), blockFreedom[GetBlockId(pos)].end(), back_inserter(phase2));
return phase2;
}

void StepForward(const pair<int, int> &pos, int step){
rowFreedom[pos.first].erase(step);
colFreedom[pos.second].erase(step);
blockFreedom[GetBlockId(pos)].erase(step);
}

void StepBack(const pair<int, int> &pos, int step){
rowFreedom[pos.first].insert(step);
colFreedom[pos.second].insert(step);
blockFreedom[GetBlockId(pos)].insert(step);
}

};

void RecursiveSolve(const vector<pair<pair<int, int>, int>> &iterList,
int depth, Freedom &freedom, map<pair<int, int>, int> &resultMap, bool &solved) const{
if(depth == (int)iterList.size()){
solved = true;
return;
}

auto curPos = iterList[depth].first;

auto possibility = move(freedom.GetFreedom(curPos));
if(possibility.empty())return;

for(const auto &guess : possibility){
resultMap.insert(make_pair(curPos, guess));
freedom.StepForward(curPos, guess);
RecursiveSolve(iterList, depth + 1, freedom, resultMap, solved);
if(solved)return;
freedom.StepBack(curPos, guess);
resultMap.erase(curPos);
}

if(depth == 0)throw runtime_error{"unable to solve"};
}

public:

void solveSudoku(vector<vector<char>> &board) {
Freedom freedom;
freedom.Init(board);

vector<pair<pair<int, int>, int>> iterList;

for(auto i = 0; i < 9; ++i){
for(auto j = 0; j < 9; ++j){
if(board[i][j] == '.') {
auto pos = make_pair(i, j);
iterList.emplace_back(make_pair(pos, (int) freedom.GetFreedom(pos).size()));
}
}
}

sort(iterList.begin(), iterList.end(),
[](const pair<pair<int, int>, int> & left,
const pair<pair<int, int>, int> &right){
return left.second < right.second;
});

map<pair<int, int>, int> resultMap;
bool solved = false;

RecursiveSolve(iterList, 0, freedom, resultMap, solved);

for(const auto &iter : resultMap){
board[iter.first.first][iter.first.second] = iter.second + '0';
}

}
};