## Question

## Transcribed Text

## Solution Preview

These solutions may offer step-by-step problem-solving explanations or good writing examples that include modern styles of formatting and construction of bibliographies out of text citations and references. Students may use these solutions for personal skill-building and practice. Unethical use is strictly forbidden.

/** File: main.cpp

* Author:

*

* Develop and implement a stack-based Sudoku puzzle solver.

*

* When solved, each row must have all of the integers 1 – 9,

* each column must have all of the integers 1 – 9 and

* each of the nine 3-by-3 blocks must have all of the integers 1 – 9.

*

*/

#include <cstdlib>

#include <iostream>

#include <stack>

#include <fstream>

#include <iomanip>

using namespace std;

const short int BOARD_SIZE = 9;

const short int BLOCK_SIZE = 3;

const short int EMPTY_CELL = 0;

const int UNFILLED_INDEX = 15;

const int DIGIT_NUM = 9;

const short int MASK_0_CHOICE = 0xE1FF; // 1110000111111111

const short int MASK_ALL = 0xFFFF; // 1111111111111111

const short int MASK_0_CHOICE_TOGGLE = ~MASK_0_CHOICE; // 0001111000000000

const short int MASK_000F = 0x000F; // 0000000000001111

const short int MASK_ALL_AS_VALID_CHOICE = 0x01FF; // 0000000111111111

/**

* update 4 bits of current choice

* @param val the short int value

* @param currentChoice the choice to be filled in

* @return the updated value

*/

short int setChoice(short int val, int currentChoice);

/**

* get current choice from the short int value

* @param val the value

* @return the choice

*/

short int getChoice(short int val);

/**

* read data from cin

* @param board 2d array of number

*/

void readData(short int board[BOARD_SIZE][BOARD_SIZE], fstream & fin);

/**

* read date from an input stream

* for debugging

* @param board 2d array of number

* @param fin input stream

*/

void readData(short int board[BOARD_SIZE][BOARD_SIZE]);

/**

* print formated result to screen

* @param board 2 d array of numbers

*/

void printResult(short int board[BOARD_SIZE][BOARD_SIZE]);

/**

* print simple table

* for input data printing

* @param board 2d array of number

*/

void printData(short int board[BOARD_SIZE][BOARD_SIZE]);

/**

* print hex value of all filled cells for debugging

* @param board 2d array of number

*/

void printHex(short int board[BOARD_SIZE][BOARD_SIZE]);

/**

* print hex value of all cella for debugging

* @param board 2d array of number

*/

void printHexAll(short int board[BOARD_SIZE][BOARD_SIZE]);

/**

* set a bit to 0

* @param val the number

* @param position the position for setting

* @return a new value

*/

short int unsetNBit(short int val, int position);

/**

* set a bit to 1

* @param val the number

* @param position the position for setting

* @return a new value

*/

short int setNBit(short int val, int position);

/**

* count the number of valid choice in 9 first digits

* @param val the short int value

* @return number of valid choices

*/

int validChoiceCounter(short int val);

/**

* Preconditions bord contains an unsolved Sudoku puzzle

* Postconditions the best location is pushed onto the stack

* the best location is marked as filled in

* @param board 2d array of number

* @param st stack of indices of best cells

*/

bool findBest(short int board[BOARD_SIZE][BOARD_SIZE], stack<int> & st);

/**

* get the next valid choice

* @param val a short int number

* @return index of selected digit

*/

int getValidChoice(short int val);

/**

* Preconditions bord contains an unsolved Sudoku puzzle

* Postconditions bord contains a solved Sudoku puzzle

* @param board 2d aray of number

* @return true when the board is solved

*/

bool solve(short int board[BOARD_SIZE][BOARD_SIZE]);

int main(int argc, char** argv) {

/**

* Read the data from cin. Input consists of nine lines of

* nine characters. If a cell is filled in, its

* character will be a digit 1 – 9. If it is blank,

* its character is a period.

*/

/*

* Pro tip: You only need a single char variable for

* the input; no strings necessary.

*/

short int board[BOARD_SIZE][BOARD_SIZE];

readData(board);

//printData(board);

if (solve(board)) {

printResult(board);

}

return 0;

}

/**

* Preconditions bord contains an unsolved Sudoku puzzle

* Postconditions bord contains a solved Sudoku puzzle

* @param board 2d aray of number

* @return true when the board is solved

*/

bool solve(short int board[BOARD_SIZE][BOARD_SIZE]) {

// 2: Select the best empty cell and place its location on the stack

stack<int> st;

// printHexAll(board);

// cout << "******************\n";

findBest(board, st);

// printHexAll(board);

// cout <<"--------------------------------\n";

int i, j;

int top;

int validChoice;...

By purchasing this solution you'll be able to access the following files:

Solution.zip.