数独sukudo

问题的类别是回溯。

注意边界、剪枝的问题。

具体的问题描述看leetcode这里

需要特别注意的是，leetcode这里的输入是按照第一行、第二行、第三行来进行的，而不是，第一个九宫格，第二个九宫格。

// .h
//
// Created on 3/14/18.
//

#ifndef AGORITHM_SUDOKU2_H
#define AGORITHM_SUDOKU2_H

#include <vector>

class Sudoku2 {
public:
    using VIS_RECORD=std::vector<std::vector<int>>;

    static void test();

    static void solveSudoku(std::vector<std::vector<char>> &board);

    static void visit(VIS_RECORD &row, VIS_RECORD &col, VIS_RECORD &mat, int r, int c, int num,
                      std::vector<std::vector<char>> &board, bool &found);

private:
    static void initVis(VIS_RECORD &row, VIS_RECORD &col, VIS_RECORD &mat, const std::vector<std::vector<char>> &board);

    static int getOrderForMat(int r, int c);

    static int getPosOfCell(int r, int c);

    template<typename T>
    static void printBoard(const std::vector<std::vector<T>> &board);
};


#endif //AGORITHM_SUDOKU2_H

// .cpp
//
// Created on 3/14/18.
//

#include <iostream>
#include "Sudoku2.h"

using namespace std;

void Sudoku2::solveSudoku(std::vector<std::vector<char>> &board) {
    const int N = board.size();

    vector<vector<int>> visRow(N, vector<int>(N, 0));   // visRow[i][j] == 1 if row i has number j
    auto visCol = visRow;                               // visCol[i][j] == 1 if col i has number j
    auto visMat = visRow;                               // visMat[i][j] == 1 if mat i has number j

    initVis(visRow, visCol, visMat, board);

    bool found = false;
    for (int i = 0; i < N; i++) {
        visit(visRow, visCol, visMat, 0, 0, i, board, found);
    }
}

void Sudoku2::visit(Sudoku2::VIS_RECORD &row, Sudoku2::VIS_RECORD &col, Sudoku2::VIS_RECORD &mat, const int r,
                    const int c, int num, std::vector<std::vector<char>> &board, bool &found) {
    if (!found) {
        int o = getOrderForMat(r, c);
        if ((!row[r][num] && !col[c][num] && !mat[o][num] && (board[r][c] == '.')) || (board[r][c] - '1' == num)) {
            const int N = board.size();

            bool diff = (board[r][c] - '1' != num);
            if (diff) {
                row[r][num] = col[c][num] = mat[o][num] = 1;
                board[r][c] = num + '1';
            }


            if (r == N - 1 && c == N - 1) {
                found = true;
                return;
            }

            if (c < N - 1) {
                for (int i = 0; (i < N) && !found; i++) {   // visit next cell of same unit with possible values
                    if (i != num) {
                        visit(row, col, mat, r, c + 1, i, board, found);
                    }
                }
            }

            if (c == N - 1) {   // the last cell of k'th unit
                for (int i = 0; (i < N) && !found; i++) {   // visit first cell of next unit with possible values
                    visit(row, col, mat, r + 1, 0, i, board, found);
                }
            }

            if (diff && !found) {
                row[r][num] = col[c][num] = mat[o][num] = 0;
                board[r][c] = '.';
            }
        }
    }
}

int Sudoku2::getOrderForMat(int r, int c) {
    return r / 3 * 3 + c / 3;
}

int Sudoku2::getPosOfCell(int r, int c) {
    return c % 3 + r % 3 * 3;
}

void Sudoku2::initVis(Sudoku2::VIS_RECORD &row, Sudoku2::VIS_RECORD &col, Sudoku2::VIS_RECORD &mat,
                      const std::vector<std::vector<char>> &board) {
    const int N = board.size();
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (board[i][j] != '.') {
                int x = board[i][j] - '1';

                int o = getOrderForMat(i, j);
                mat[o][x] = 1;

                row[i][x] = 1;
                col[j][x] = 1;
            }
        }
    }
}

template<typename T>
void Sudoku2::printBoard(const std::vector<std::vector<T>> &board) {
    for (auto &v: board) {
        for (auto ch: v) {
            cout << ch << " ";
        }
        cout << endl;
    }
    cout << endl;
}

void Sudoku2::test() {
    vector<vector<char>> board1 = {
            {'.', '.', '9', '7', '4', '8', '.', '.', '.'},
            {'7', '.', '.', '.', '.', '.', '.', '.', '.'},
            {'.', '2', '.', '1', '.', '9', '.', '.', '.'},
            {'.', '.', '7', '.', '.', '.', '2', '4', '.'},
            {'.', '6', '4', '.', '1', '.', '5', '9', '.'},
            {'.', '9', '8', '.', '.', '.', '3', '.', '.'},
            {'.', '.', '.', '8', '.', '3', '.', '2', '.'},
            {'.', '.', '.', '.', '.', '.', '.', '.', '6'},
            {'.', '.', '.', '2', '7', '5', '9', '.', '.'}
    };

    auto fn = [](vector<vector<char>> &board) {
        solveSudoku(board);
        printBoard(board);
    };
    fn(board1);
}