Sudoku is a popular logic-based number placement game. The aim of the puzzle is
ID: 3807503 • Letter: S
Question
Sudoku is a popular logic-based number placement game. The aim of the puzzle is to enter a numerical digit from 1 through 9 in each cell of a 9×9 grid made up of 3×3 sub grids (called “boxes”). The game starts with various digits given in some cells (the “givens”). When finished, each row, column, and 3x3 regions must contain all 9 digits with no repetition.
There are 3 simple rules you must follow when playing Sudoku. Fill in the grid so that:
1. every row
2. every column
3. every 3x3 box contains the digits 1 through 9.
For this project, you will implement a class Sudoku
which has the following member functions:
1. Sudoku(std::string): The parameterized constructor accepts a filename (string) as input. The file contains an unsolved sudoku puzzle. This constructor initializes the sudoku grid from the data contained in the input file. Please see the section Sudoku File Format for the appropriate format.
2. Save(std::string): Accepts an output filename as argument and saves the sudoku grid to the output file in the format described in the section Sudoku File Format.
3. Overloaded<< operator for printing out the sudoku grid.
•If A is a Sudoku object,std::cout << A;should print the content of A in the format specified in section Sudoku File Format.
4. Overloaded( ) operator for accessing the grid values at a specified row, column pair
• If A is a Sudoku object,A(2, 3);should return the grid value of A at row = 2 and column = 3.
•If the grid value is not a number between 1 and 9, it should return 0.
•The row and the column indices should be within the range of 0 and 8. Otherwise, it shouldthrow an OutOfBounds exception.
5. Solve() for solving the sudoku puzzle
•If A is a Sudoku object, A.Solve(); solves the puzzle resulting in a complete and valid grid forA.
•You can assume the input puzzle is always solvable.
Sudoku File Format:
The following is an example sudoku input file (say 0 sudokugrid.txt).
*****329*
*865*****
*2***1***
**37*51**
9*******8
**29*83**
***4***8*
*****647*
*471*****
Overall, it’s a 9×9 grid containing numbers (between 1 and 9) and the character. It is unsolved and the’s indicate the cells that need to be filled correctly. After solving, the above sudoku grid should look like
the following:
154873296
386592714
729641835
863725149
975314628
412968357
631457982
598236471
247189563
The project needs a header file(.hpp) to declare everything for the class and a .cpp with the definitions
Explanation / Answer
Ans: The .cpp and hpp codes are below
// solver.cpp
#include <iostream>
//includes .hpp
#include "sudokusolver.hpp"
int main()
{
Solver solver;
//true
while (true)
{
//puzzle
State puzzle;
std::cin >> puzzle;
if (!std::cin)
{
//break
break;
}
std::vector<State> solutions = solver.Solve(puzzle);
//bool
bool first = true;
for (State& s : solutions)
{
if (!first)
std::cout << ",";
std::cout << s;
}
std::cout << std::endl;
}
//returns
return 0;
}
sudokusolver.hpp
#pragma once
#include <cassert>
#include <cstdint>
#include <functional>
#include <sstream>
#include <vector>
// include callbackQueue.hpp
#include "callbackQueue.hpp"
// includes state.hpp
#include "state.hpp"
// includes staticData.hpp
#include "staticData.hpp"
class Solver
{
private:
using u8 = std::uint8_t;
using u16 = std::uint16_t;
using u64 = std::uint64_t;
State mState;
std::vector<State>* mCurrSolutions = nullptr;
CallbackQueue mDirtyCells;
bool mContradiction = false;
void ProcessCell(u8 cellNo)
{
u16 cell = mState.GetCell(cellNo);
for (u8 neighbourNo : GetCellNeighbours(cellNo))
{
u16 neighbour = mState.GetCell(neighbourNo);
if ((neighbour & cell) != 0u)
{
neighbour &= ~cell;
if ((neighbour & (neighbour - u16(1))) == 0u) // TODO: try getting rid of all instances of u8(1) etc.
{
if (neighbour == 0u)
{
mContradiction = true;
return;
}
mDirtyCells.Push(neighbourNo);
}
}
mState.SetCell(neighbourNo, neighbour);
}
}
static bool CellIsPair(u16 cell) // cell != 0 is assumed
{
cell &= (cell - u16(1));
if (cell == 0)
return false;
cell &= (cell - u16(1));
return (cell == 0);
}
void LockedPairsInGroup(const std::array<u8, 9>& group)
{
u16 lockedPair = 511;
for (u8 i = 0u; i != 9u; ++i)
{
u16 cell = mState.GetCell(group[i]);
if (CellIsPair(cell))
{
lockedPair = cell;
break;
}
}
if (lockedPair == 511)
return;
u8 count = 0u;
for (u8 i = 0u; i != 9u; ++i)
{
u16 cell = mState.GetCell(group[i]);
count += (cell == lockedPair);
}
if (count != 2)
{
mContradiction |= (count > 2);
return;
}
for (auto cellNo : group)
{
u16 cell = mState.GetCell(cellNo);
if ((cell & lockedPair) != 0u)
{
if (cell == lockedPair)
continue; // TODO: duplicating counter here?
cell &= ~lockedPair;
if ((cell & (cell - u16(1))) == 0u)
{
if (cell == 0u)
{
mContradiction = true;
return;
}
mDirtyCells.Push(cellNo); // TODO: try going back to normal strategy at first occurrence here
}
}
mState.SetCell(cellNo, cell);
}
}
void LockedPairs()
{
for (auto& group : GetGroups())
{
LockedPairsInGroup(group);
if (!mDirtyCells.Empty())
return;
}
}
std::string GetDirtyCellsInBinary() const
{
std::string result(81, '0');
auto dirtyCells = mDirtyCells;
while (true)
{
u8 cellNo = dirtyCells.Pop();
if (cellNo == u8(255))
break;
result[cellNo] = '1';
}
return result;
}
void ProcessCurrState()
{
while (!mDirtyCells.Empty())
{
ProcessCurrStateRaw();
if (mContradiction)
return;
LockedPairs();
if (mContradiction)
return;
}
}
void ProcessCurrStateRaw()
{
while (!mDirtyCells.Empty())
{
u8 cellNo = mDirtyCells.Pop();
ProcessCell(cellNo);
if (mContradiction)
return;
}
}
void MarkFinalCellsDirty()
{
for (u8 cellNo = 0u; cellNo != 81u; ++cellNo)
{
u16 cell = mState.GetCell(cellNo);
if ((cell & (cell - u16(1))) == 0u)
{
mDirtyCells.Push(cellNo);
}
}
}
void Guess(u8 cellNo, u16 cell)
{
mState.SetCell(cellNo, cell);
mDirtyCells.Push(cellNo);
}
void SolveImpl()
{
ProcessCurrState();
ProcessingExhausted();
}
void ProcessingExhausted()
{
if (mContradiction)
{
mContradiction = false;
return;
}
u8 guessCellNo = mState.PickNonFinalisedCell();
if (guessCellNo == u8(255))
{
mCurrSolutions->push_back(mState);
return;
}
u16 cell = mState.GetCell(guessCellNo);
u16 newCell = u16(1) << u16(8);
State backupState = mState;
while (newCell > u16(0))
{
if ((newCell & cell) != u16(0))
{
Guess(guessCellNo, newCell);
SolveImpl();
mState = backupState;
mDirtyCells.Clear();
}
newCell >>= u16(1);
}
}
public:
State ShallowSolve(const State& state)
{
mState = state;
MarkFinalCellsDirty();
ProcessCurrState();
return mState;
}
std::vector<State> Solve(const State& state)
{
std::vector<State> solutions;
mCurrSolutions = &solutions;
mState = state;
MarkFinalCellsDirty();
SolveImpl();
mCurrSolutions = nullptr;
return solutions;
}
};
////callback_queue.hpp///////
#pragma once
#include <array>
#include <cstddef>
#include <cstdint>
class CallbackQueue
{
private:
using u8 = std::uint8_t;
using u64 = std::uint64_t;
std::array<u64, 2> mFlags = {{0u, 0u}};
public:
bool Empty() const { return mFlags[0] == 0u && mFlags[1] == 0u; } // TODO: empty flag? #performance
void Clear() { mFlags[0] = mFlags[1] = 0u; }
u8 Size() const { return __builtin_popcountll(mFlags[0]) + __builtin_popcountll(mFlags[1]); }
void Push(u8 x)
{
assert(x < 81u);
u8 i = 0u;
if (x >= 64u)
{
++i;
x -= 64u;
}
u64 bit = 1ull << x;
mFlags[i] |= bit;
}
void PushFlags(std::array<u64, 2> flags) { mFlags[0] |= flags[0]; mFlags[1] |= flags[1]; }
void PushFlags(u64 flags) { mFlags[0] |= flags; } // TODO: remove
u8 Pop()
{
if (mFlags[0] != 0ull)
{
u8 ret = __builtin_ctzll(mFlags[0]);
mFlags[0] &= ~(1ull << ret);
return u8(ret);
}
else if (mFlags[1] != 0ull)
{
u8 ret = __builtin_ctzll(mFlags[1]);
mFlags[1] &= ~(1ull << ret);
return u8(64u + ret);
}
return u8(255);
}
void PopElement(u8 element)
{
if (element < 64u)
{
mFlags[0] &= ~(1u << element);
}
else
{
element -= 64u;
mFlags[1] &= ~(1u << element);
}
}
};
//////state.hpp//////
#pragma once
#include <array>
#include <cassert>
#include <cstdint>
#include <iostream>
class State
{
private:
using u8 = std::uint8_t;
using u16 = std::uint16_t;
std::array<u16, 81> mCells;
public:
State()
{
// Set all flags to true
for (auto& c : mCells)
{
c = 511;
}
}
u16 GetCell(u16 cellNo) const
{
return mCells[cellNo];
}
void SetCell(u16 cellNo, u16 state)
{
mCells[cellNo] = state;
}
u8 PickNonFinalisedCell()
{
u8 bestCellNo = 255;
u8 bestPossibilities = 255;
for (u8 i = 0u; i != 81u; ++i)
{
u16 cell = GetCell(i);
u8 possibilities = NumPossibilities(cell);
// Shortcut: can't do better than 2
if (possibilities == u8(2))
{
return i;
}
if (possibilities > u8(1) && possibilities < bestPossibilities)
{
bestCellNo = i;
bestPossibilities = possibilities;
}
}
return bestCellNo;
}
// TODO: there are other ways to do this, investigate their #performance
static u8 NumPossibilities(u16 cell)
{
return __builtin_popcount(cell);
}
static u8 CellToNum(u16 cell)
{
if (cell == 0 || (cell & (cell - u16(1))) != 0)
{
return 0;
}
u8 n = 9;
u16 nn = 1;
while (nn != cell)
{
nn <<= 1;
--n;
}
return n;
}
static u16 NumToCell(u8 n)
{
if (u8(1) <= n && n <= u8(9))
{
--n;
return u16(1) << (u8(8) - n);
}
assert(n == 0);
return 511;
}
std::ostream& PrettyPrint(std::ostream& os) const
{
std::array<std::array<char, 41>, 41> grid;
for (auto& r : grid)
{
for (auto& c : r)
c = ':';
}
for (u8 i = 0u; i != 81u; ++i)
{
int row = i / 9;
int col = i % 9;
int r = 4 * row + 1;
if (row >= 3)
r += 2;
if (row >= 6)
r += 2;
int c = 4 * col + 1;
if (col >= 3)
c += 2;
if (col >= 6)
c += 2;
u16 cell = GetCell(i);
for (u8 k = 0u; k != 9; ++k)
{
int ki = k / 3;
int kj = k % 3;
grid[r + ki][c + kj] = ((cell & (1 << k)) ? char('1' + k) : ' ');
}
}
for (auto& r : grid)
{
for (auto& c : r)
os << c;
os << std::endl;
}
os << std::endl << std::endl << std::endl;
return os;
}
friend std::ostream& operator<<(std::ostream& os, const State& state)
{
for (u8 i = 0u; i != 81u; ++i)
{
os << int(State::CellToNum(state.GetCell(i)));
}
return os;
}
friend std::istream& operator>>(std::istream& is, State& state)
{
for (u8 i = 0u; i != 81u; ++i)
{
u8 n;
is >> n;
if (!(u8('0') <= n && n <= u8('9')))
{
// Invalid
return is;
}
state.SetCell(i, State::NumToCell(n - u8('0')));
}
return is;
}
};
///////staticdata.hpp//////////
#pragma once
#include <array>
#include <bitset>
#include <cstdint>
std::array<std::array<uint8_t, 9>, 27> CreateGroups()
{
std::array<std::array<uint8_t, 9>, 27> ret;
// rows
for (int i = 0; i != 9; i++)
{
for (int j = 0; j != 9; j++)
{
ret[i][j] = 9 * i + j;
}
}
// columns
for (int i = 9; i != 18; i++)
{
for (int j = 0; j != 9; j++)
{
ret[i][j] = (i - 9) + 9 * j;
}
}
// blocks
for (int i = 18; i != 27; i++)
{
for (int j = 0; j != 9; j++)
{
int ni = i - 18;
ret[i][j] = 27 * (ni / 3) + 3 * (ni % 3) + 9 * (j / 3) + (j % 3);
}
}
return ret;
}
const std::array<std::array<uint8_t, 9>, 27>& GetGroups()
{
static const std::array<std::array<uint8_t, 9>, 27> groups = CreateGroups();
return groups;
}
std::uint32_t GetCellGroups(uint8_t cellNo)
{
return (
(1u << (cellNo / 9u)) |
(1u << (9u + cellNo % 9u)) |
(1u << (18u + 3u * (cellNo / 27u) + (cellNo % 9u) / 3u)));
}
std::array<std::array<std::uint8_t, 20>, 81> CreateCellNeighbours()
{
using u8 = std::uint8_t;
std::array<std::array<u8, 20>, 81> neighbours;
const auto& groups = GetGroups();
for (u8 i = 0u; i != 81u; ++i)
{
std::bitset<81> set;
for (u8 groupNo : (u8[]){u8(i / 9u), u8(9u + i % 9u), u8(18u + 3u * (i / 27u) + (i % 9u) / 3u)})
{
for (auto neighbour : groups[groupNo])
{
set.set(neighbour);
}
}
auto& nn = neighbours[i];
u8 k = 0u;
for (u8 j = 0u; j != 81u; j++)
{
if (set.test(j) && i != j)
{
nn[k] = j;
++k;
}
}
}
return neighbours;
}
const std::array<std::uint8_t, 20>& GetCellNeighbours(std::uint8_t cellNo)
{
static const std::array<std::array<std::uint8_t, 20>, 81> cellNeighbours = CreateCellNeighbours();
return cellNeighbours[cellNo];
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.