/* The "constexpr" specifier declares that it is possible to evaluate the value of the function or variable at compile time.
Such variables and functions can then be used where only compile time constant expressions are allowed.
(provided that appropriate function arguments are given). */
/* The "noexcept" operator performs a compile-time check that returns true
if an expression is declared to not throw any exceptions. */
#include <array>
#include <bitset>
#include <iostream>
#include <vector>
constexpr std::size_t
get_cell(std::size_t row, std::size_t col) noexcept {
return (row / 3) * 3 + col / 3;
}
constexpr std::size_t
get_next_row(std::size_t row, std::size_t col) noexcept {
return row + (col + 1) / 9;
}
constexpr std::size_t
get_next_col(std::size_t col) noexcept {
return (col + 1) % 9;
}
class Solution {
public:
void solveSudoku(std::vector<std::vector<char>> &board) const noexcept {
/* Note: input is guaranteed to be a valid board using only '1'-'9' and '.' with a unique solution.
Solution should modify board, not return a new one. */
std::array<std::bitset<9>, 9> row_contains = {0, 0, 0, 0, 0, 0, 0, 0, 0};
std::array<std::bitset<9>, 9> col_contains = {0, 0, 0, 0, 0, 0, 0, 0, 0};
std::array<std::bitset<9>, 9> cell_contains = {0, 0, 0, 0, 0, 0, 0, 0, 0};
for (std::size_t row = 0; row < 9; ++row) {
for (std::size_t col = 0; col < 9; ++col) {
char digit;
if ((digit = board[row][col]) != '.') {
std::size_t digit_idx = digit - '1';
row_contains[row].set(digit_idx);
col_contains[col].set(digit_idx);
std::size_t cell = get_cell(row, col);
cell_contains[cell].set(digit_idx);
}
}
}
solve(board, 0, 0, row_contains, col_contains, cell_contains);
}
private:
static constexpr std::pair<std::size_t, std::size_t>
next_empty_position(std::vector<std::vector<char>> &board, std::size_t row, std::size_t col) noexcept {
while (row != 9) {
if (board[row][col] == '.') {
return {row, col};
}
row = get_next_row(row, col);
col = get_next_col(col);
}
return {9, 0};
}
static bool
solve(std::vector<std::vector<char>> &board, std::size_t const row_start, std::size_t const col_start,
std::array<std::bitset<9>, 9> &row_contains,
std::array<std::bitset<9>, 9> &col_contains,
std::array<std::bitset<9>, 9> &cell_contains) noexcept {
auto [row, col] = next_empty_position(board, row_start, col_start);
// end of board
if (row == 9) return true;
std::size_t const cell = get_cell(row, col);
std::bitset<9> const contains = row_contains[row] | col_contains[col] | cell_contains[cell];
if (contains.all()) return false;
for (std::size_t digit_idx = 0; digit_idx < 9; ++digit_idx) {
if (!contains[digit_idx]) {
board[row][col] = static_cast<char>(digit_idx + '1');
row_contains[row].set(digit_idx);
col_contains[col].set(digit_idx);
cell_contains[cell].set(digit_idx);
if (solve(board, row, col, row_contains, col_contains, cell_contains)) {
return true;
}
row_contains[row].reset(digit_idx);
col_contains[col].reset(digit_idx);
cell_contains[cell].reset(digit_idx);
}
}
board[row][col] = '.';
return false;
}
};
void print_board(std::vector<std::vector<char>> board) {
for (std::size_t row = 0; row < 9; ++row) {
for (std::size_t col = 0; col < 9; ++col) {
std::cout << board[row][col] << ", ";
}
std::cout << "\n";
}
}
std::vector<std::vector<char>> flat_board_to_vec_vec(std::array<char, 81> const flat_board) {
std::vector<std::vector<char>> board;
board.reserve(9);
for (std::size_t row = 0; row < 9; ++row) {
std::vector<char> this_row;
this_row.reserve(9);
for (std::size_t col = 0; col < 9; ++col) {
this_row.push_back(flat_board[row * 9 + col]);
}
board.push_back(this_row);
}
return board;
}
int main() {
// initial sudoku board
std::array<char, 81> const initial_board = {'5', '3', '.', '.', '7', '.', '.', '.', '.',
'6', '.', '.', '1', '9', '5', '.', '.', '.',
'.', '9', '8', '.', '.', '.', '.', '6', '.',
'8', '.', '.', '.', '6', '.', '.', '.', '3',
'4', '.', '.', '8', '.', '3', '.', '.', '1',
'7', '.', '.', '.', '2', '.', '.', '.', '6',
'.', '6', '.', '.', '.', '.', '2', '8', '.',
'.', '.', '.', '4', '1', '9', '.', '.', '5',
'.', '.', '.', '.', '8', '.', '.', '7', '9'};
// solution for this sudoku
std::array<char, 81> const flat_expected = {'5', '3', '4', '6', '7', '8', '9', '1', '2',
'6', '7', '2', '1', '9', '5', '3', '4', '8',
'1', '9', '8', '3', '4', '2', '5', '6', '7',
'8', '5', '9', '7', '6', '1', '4', '2', '3',
'4', '2', '6', '8', '5', '3', '7', '9', '1',
'7', '1', '3', '9', '2', '4', '8', '5', '6',
'9', '6', '1', '5', '3', '7', '2', '8', '4',
'2', '8', '7', '4', '1', '9', '6', '3', '5',
'3', '4', '5', '2', '8', '6', '1', '7', '9'};
std::vector<std::vector<char>> board = flat_board_to_vec_vec(initial_board);
std::vector<std::vector<char>> const expected = flat_board_to_vec_vec(flat_expected);
Solution soln;
std::cout << "initial\n";
print_board(board);
std::cout << "expected\n";
print_board(expected);
soln.solveSudoku(board);
std::cout << (board == expected ? "success!" : "UH OH :(") << std::endl;
std::cout << "actual\n";
print_board(board);
return 0;
} Write, Run & Share C++ code online using OneCompiler's C++ online compiler for free. It's one of the robust, feature-rich online compilers for C++ language, running on the latest version 17. Getting started with the OneCompiler's C++ compiler is simple and pretty fast. The editor shows sample boilerplate code when you choose language as C++ and start coding!
OneCompiler's C++ online compiler supports stdin and users can give inputs to programs using the STDIN textbox under the I/O tab. Following is a sample program which takes name as input and print your name with hello.
#include <iostream>
#include <string>
using namespace std;
int main()
{
string name;
cout << "Enter name:";
getline (cin, name);
cout << "Hello " << name;
return 0;
}
C++ is a widely used middle-level programming language.
When ever you want to perform a set of operations based on a condition If-Else is used.
if(conditional-expression) {
//code
}
else {
//code
}
You can also use if-else for nested Ifs and If-Else-If ladder when multiple conditions are to be performed on a single variable.
Switch is an alternative to If-Else-If ladder.
switch(conditional-expression){
case value1:
// code
break; // optional
case value2:
// code
break; // optional
......
default:
code to be executed when all the above cases are not matched;
}
For loop is used to iterate a set of statements based on a condition.
for(Initialization; Condition; Increment/decrement){
//code
}
While is also used to iterate a set of statements based on a condition. Usually while is preferred when number of iterations are not known in advance.
while (condition) {
// code
}
Do-while is also used to iterate a set of statements based on a condition. It is mostly used when you need to execute the statements atleast once.
do {
// code
} while (condition);
Function is a sub-routine which contains set of statements. Usually functions are written when multiple calls are required to same set of statements which increases re-usuability and modularity. Function gets run only when it is called.
return_type function_name(parameters);
function_name (parameters)
return_type function_name(parameters) {
// code
}