QuestionQuestion

Transcribed TextTranscribed Text

Data Structures and Objects Project 2 — Sudoku Solver Goal Develop and implement a stack-based Sudoku puzzle solver. Details You are most likely familiar with the Sudoku puzzle game. It consists of a 9-by-9 grid; initially, some of the positions are filled with numbers and others are blank. 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. One method to solve a Sudoku puzzle is trial-and-error. If a valid guess can be made, make it and repeat. If no valid guess can be made, go back to the previous guess and change it; if no other guesses can be made, go back to the guess before that. Continue until either all boxes are filled or all guesses are exhausted (which shouldn’t happen because that means there is no solution.) Create a stack of integers which represent the location of cells being filled in. The top location on the stack represents the cell currently being filled in. Note that there will be at most 64 locations to track, since any Sudoku puzzle must have at least 17 cells filled in initially. Note: If you’re clever, you only need one integer to represent the location, not two. 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. Once the data is read, use the following algorithm to solve the puzzle. Data Structures and Objects Algorithm 1 The main Sudoku algorithm Preconditions bord contains an unsolved Sudoku puzzle Postconditions bord contains a solved Sudoku puzzle 1: procedure Solve 2: Select the best empty cell and place its location on the stack 3: while true do 4: Let (, j) be the location on top of the stack 5: Select the next valid choice for bord[][j] 6: if no such choice exists then 7: Mark bord[][j] as not filled in 8: Pop the stack 9: if the stack is empty then 10: Return; the puzzle has no solution 11: end if 12: continue 13: end if 14: Select the best empty cell and place its location on the stack 15: if no such cell exists then 16: break . Puzzle is now solved 17: end if 18: end while 19: Output the solution 20: end procedure .Keeping track of choices You should use bit manipulation to keep track of information for each cell. All of the information for one cell can be kept in 14 bits: • One bit to indicate if the cell has been filled in • Nine bits to keep track of which digits you are allowed to place in the cell • Four bits to hold the current choice for the cell Although it’s not strictly necessary, you can fit all of the information into the short int data type. You’ll want to use the masking operations at various points in the program to turn bits on and turn them off. You’ll also want to use the left shift operation to look at the valid choices for a cell. .Selecting the best empty cell Hypothetically, you can pick any empty cell for your next choice. However, to minimize the work the computer performs in backtracking, there is a preferred cell. The best cell to choose has the fewest valid choices for its digit. 2 of 5 Data Structures and Objects The following algorithm selects the best empty cell and places its location on the stack. Algorithm 2 Finding the best empty cell Preconditions bord contains an unsolved Sudoku puzzle Postconditions the best location is pushed onto the stack the best location is marked as filled in 1: procedure FindBest 2: for each empty cell bord[][j] do . Initialize to allow all digits as choices 3: Mark all digits as valid choices 4: end for 5: for each filled in cell bord[][j] do . Remove invalid choices 6: for each unfilled cell in row  do 7: Mark digit in bord[][j] as an invalid choice 8: end for 9: for each unfilled cell in column j do 10: Mark digit in bord[][j] as an invalid choice 11: end for 12: for each unfilled cell in the 3x3 block containing bord[][j] do 13: Mark digit in bord[][j] as an invalid choice 14: end for 15: end for 16: Set o ← 10 17: for each empty cell bord[][j] do 18: Count 1-bits in valid choices for bord[][j] 19: if cont < o then 20: o ← cont 21: best ←  22: jbest ← j 23: end if 24: end for 25: if o = 10 then 26: return false . No empty cells remain 27: end if 28: Mark bord[best][jbest] as filled in 29: Push (best, jbest) onto the stack 30: return true 31: end procedure 3 of 5 Data Structures and Objects Example 1 .Input 4.......1 .2.7..59. .98.437.. ..1.2..7. ..53.49.. .8..9.2.. ..798.12. .52..7.3. 8.......7 .Output Solution: 476 259 381 123 768 594 598 143 762 931 825 476 265 374 918 784 691 253 347 986 125 652 417 839 819 532 647 Example 2 .Input ......... 47..9..36 8...4...1 ...2.4... .25...48. 1.3...2.7 21.....48 ....7.... .9.3.2.7. .Output Solution: 361 827 954 472 195 836 859 643 721 786 234 519 925 716 483 143 958 267 217 569 348 538 471 692 694 382 175 4 of 5 Data Structures and Objects Example 3 .Input ..423...9 3.....27. 6..9..... ..3....54 4...86.9. ..9....26 1..7..... 9.....41. ..634...5 .Output Solution: 754 238 169 391 654 278 682 917 543 863 129 754 427 586 391 519 473 826 148 795 632 935 862 417 276 341 985 Example 4 .Input 1.......9 .5.8...6. ....9.8.4 43..81... 6...2...1 ...65..43 5.6.3.... .7...8.3. 2.......7 .Output Solution: 148 276 359 759 843 162 362 195 874 437 981 625 695 324 781 821 657 943 516 732 498 974 518 236 283 469 517

Solution PreviewSolution 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 bord 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 bord contains an unsolved Sudoku puzzle
* Postconditions bord 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 bord contains an unsolved Sudoku puzzle
* Postconditions bord 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.

50% discount

Hours
Minutes
Seconds
$75.00 $37.50
for this solution

or FREE if you
register a new account!

PayPal, G Pay, ApplePay, Amazon Pay, and all major credit cards accepted.

Find A Tutor

View available C-Family Programming Tutors

Get College Homework Help.

Are you sure you don't want to upload any files?

Fast tutor response requires as much info as possible.

Decision:
Upload a file
Continue without uploading

SUBMIT YOUR HOMEWORK
We couldn't find that subject.
Please select the best match from the list below.

We'll send you an email right away. If it's not in your inbox, check your spam folder.

  • 1
  • 2
  • 3
Live Chats