Submission
Status:
[-SSSSSSSSS]
Subtask/Task Score:
{0/100}
Score: 0
User: fishia
Problemset: เรียงสตริง
Language: cpp
Time: 0.003 second
Submitted On: 2026-10-11 20:45:50
#include <iostream>
#include <vector>
#include <numeric>
#include <random>
#include <algorithm>
#include <cctype>
#include <string>
class SudokuGame {
private:
std::vector<std::vector<int>> solution;
std::vector<std::vector<int>> puzzle;
std::vector<std::vector<bool>> fixedCells;
std::mt19937 rng;
// Fill one diagonal 3x3 box with a shuffled set of digits.
// These boxes are independent, so they provide a valid starting point for solving the grid.
void fillBox(int rowStart, int colStart) {
std::vector<int> nums = {1, 2, 3, 4, 5, 6, 7, 8, 9};
std::shuffle(nums.begin(), nums.end(), rng);
int idx = 0;
for (int r = 0; r < 3; ++r) {
for (int c = 0; c < 3; ++c) {
solution[rowStart + r][colStart + c] = nums[idx++];
}
}
}
// Checks if placing 'num' at grid[row][col] violates row, column, or subgrid rules
bool isValidPlacement(const std::vector<std::vector<int>>& grid, int row, int col, int num) const {
for (int i = 0; i < 9; ++i) {
// Check row (ignoring current cell)
if (i != col && grid[row][i] == num) return false;
// Check column (ignoring current cell)
if (i != row && grid[i][col] == num) return false;
// Check 3x3 subgrid (ignoring current cell)
int boxRow = 3 * (row / 3) + i / 3;
int boxCol = 3 * (col / 3) + i % 3;
if ((boxRow != row || boxCol != col) && grid[boxRow][boxCol] == num) return false;
}
return true;
}
// Complete the grid recursively, trying shuffled digits and backtracking when needed.
// The cells inside the diagonal boxes are already filled by fillBox().
bool fillRemaining(int r = 0, int c = 0) {
if (c >= 9) { c = 0; r++; }
if (r >= 9) return true;
if (r < 3) {
if (c < 3) c = 3;
} else if (r < 6) {
if (c == 3 * (r / 3)) c += 3;
} else {
if (c == 6) {
r++;
c = 0;
if (r >= 9) return true;
}
}
std::vector<int> nums = {1, 2, 3, 4, 5, 6, 7, 8, 9};
std::shuffle(nums.begin(), nums.end(), rng);
for (int num : nums) {
if (isValidPlacement(solution, r, c, num)) {
solution[r][c] = num;
if (fillRemaining(r, c + 1)) return true;
solution[r][c] = 0;
}
}
return false;
}
public:
SudokuGame() : solution(9, std::vector<int>(9, 0)),
puzzle(9, std::vector<int>(9, 0)),
fixedCells(9, std::vector<bool>(9, false)),
rng(std::random_device{}()) {}
// Build a complete solution first, then hide random cells to make the playable puzzle.
void generateNewGame(int cluesCount = 35) {
solution = std::vector<std::vector<int>>(9, std::vector<int>(9, 0));
fixedCells = std::vector<std::vector<bool>>(9, std::vector<bool>(9, false));
for (int i = 0; i < 9; i += 3) {
fillBox(i, i);
}
fillRemaining();
puzzle = solution;
std::vector<int> positions(81);
std::iota(positions.begin(), positions.end(), 0);
std::shuffle(positions.begin(), positions.end(), rng);
// Remove enough cells to leave the requested number of starting clues.
int cellsToRemove = 81 - cluesCount;
for (int i = 0; i < cellsToRemove; ++i) {
int pos = positions[i];
puzzle[pos / 9][pos % 9] = 0;
}
for (int r = 0; r < 9; ++r) {
for (int c = 0; c < 9; ++c) {
if (puzzle[r][c] != 0) {
fixedCells[r][c] = true;
}
}
}
}
void printGrid() const {
std::cout << "\n A B C D E F G H I\n";
for (int r = 0; r < 9; ++r) {
std::cout << r + 1 << ") ";
for (int c = 0; c < 9; ++c) {
if (puzzle[r][c] == 0) {
std::cout << ".";
} else {
std::cout << puzzle[r][c];
}
if (c == 2 || c == 5) {
std::cout << "|";
} else if (c < 8) {
std::cout << " ";
}
}
std::cout << "\n";
if (r == 2 || r == 5) {
std::cout << " -----+-----+-----\n";
}
}
std::cout << "\n";
}
// Apply a player's move after checking coordinates, clue protection, and Sudoku rules.
bool makeMove(char colChar, int rowNum, int val) {
colChar = std::toupper(colChar);
int col = colChar - 'A';
int row = rowNum - 1;
// Validate boundary ranges
if (row < 0 || row > 8 || col < 0 || col > 8) {
std::cout << ">> Invalid coordinate! Column must be A-I, Row 1-9.\n";
return false;
}
// Prevent modifying starting clues
if (fixedCells[row][col]) {
std::cout << ">> Cannot edit initial starting clues!\n";
return false;
}
// erasing cells with 0
if (val == 0) {
puzzle[row][col] = 0;
std::cout << ">> Cleared cell " << colChar << rowNum << ".\n";
return true;
}
if (val < 1 || val > 9) {
std::cout << ">> Value must be between 1 and 9 (or 0 to erase).\n";
return false;
}
//Verify no duplicate in row, column, or 3x3 box
if (!isValidPlacement(puzzle, row, col, val)) {
std::cout << ">> Invalid move! " << val << " conflicts with an existing number in the same row, column, or 3x3 subgrid.\n";
return false;
}
puzzle[row][col] = val;
std::cout << ">> Placed " << val << " at " << colChar << rowNum << ".\n";
return true;
}
bool isSolved() const {
return puzzle == solution;
}
// Fill the first empty cell using the stored solution.
void giveHint() {
for (int r = 0; r < 9; ++r) {
for (int c = 0; c < 9; ++c) {
if (puzzle[r][c] == 0) {
puzzle[r][c] = solution[r][c];
std::cout << ">> Hint filled cell " << static_cast<char>('A' + c) << (r + 1)
<< " with " << solution[r][c] << "!\n";
return;
}
}
}
}
};
int main() {
// Create a new puzzle, then process commands until solved, quit, or stdin ends.
SudokuGame game;
game.generateNewGame(35);
std::cout << "========================================\n";
std::cout << " INTERACTIVE SUDOKU \n";
std::cout << "========================================\n";
std::cout << "Commands:\n";
std::cout << " - Move: Enter coordinate + number (e.g., 'A1 5')\n";
std::cout << " - Clear cell: Set value to 0 (e.g., 'A1 0')\n";
std::cout << " - Hint: Type 'hint'\n";
std::cout << " - Quit: Type 'quit'\n";
while (true) {
game.printGrid();
if (game.isSolved()) {
std::cout << "Congratulations! You solved the Sudoku puzzle!\n";
break;
}
std::cout << "Enter move > ";
std::string input;
if (!(std::cin >> input)) break;
if (input == "quit") {
std::cout << "Thanks for playing!\n";
break;
}
if (input == "hint") {
game.giveHint();
continue;
}
int value;
if (std::cin >> value) {
if (input.length() >= 2) {
char col = input[0];
int row = input[1] - '0';
game.makeMove(col, row, value);
} else {
std::cout << ">> Invalid input format. Use format like 'A1 5'.\n";
}
} else {
std::cin.clear();
std::cin.ignore(10000, '\n');
std::cout << ">> Invalid command.\n";
}
}
return 0;
}