Databases
StackOverflow2013
Postsdbo
POSudoku Recursion, accepting zeros as legal
Body
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POSudoku Recursion, accepting zeros as legal
    text
    copied!<p>I am building a recursive Sudoku solver but I have run into an issue. It seems that my legality function is accepting 0's in the final answer. It is not assigning zeros however, zeros are used as a place holder to mark an unfilled value. When I run the program, I get output like this...</p> <pre><code>************************************************** 7 4 3 | 8 2 1 | 0 0 0 0 6 8 | 0 9 0 | 0 1 0 0 0 0 | 0 0 6 | 0 0 4 ---------|---------|--------- 0 0 0 | 0 0 0 | 2 3 9 0 0 0 | 0 0 0 | 0 0 0 4 1 5 | 0 0 0 | 0 0 0 ---------|---------|--------- 9 0 0 | 5 0 0 | 0 0 0 0 2 0 | 0 1 0 | 7 4 0 0 0 0 | 2 0 0 | 9 0 5 ************************************************** ************************************************** 7 4 3 | 8 2 1 | 5 0 0 0 6 8 | 0 9 0 | 0 1 0 0 0 0 | 0 0 6 | 0 0 4 ---------|---------|--------- 0 0 0 | 0 0 0 | 2 3 9 0 0 0 | 0 0 0 | 0 0 0 4 1 5 | 0 0 0 | 0 0 0 ---------|---------|--------- 9 0 0 | 5 0 0 | 0 0 0 0 2 0 | 0 1 0 | 7 4 0 0 0 0 | 2 0 0 | 9 0 5 ************************************************** ************************************************** 7 4 3 | 8 2 1 | 5 6 0 0 6 8 | 0 9 0 | 0 1 0 0 0 0 | 0 0 6 | 0 0 4 ---------|---------|--------- 0 0 0 | 0 0 0 | 2 3 9 0 0 0 | 0 0 0 | 0 0 0 4 1 5 | 0 0 0 | 0 0 0 ---------|---------|--------- 9 0 0 | 5 0 0 | 0 0 0 0 2 0 | 0 1 0 | 7 4 0 0 0 0 | 2 0 0 | 9 0 5 ************************************************** ************************************************** 7 4 3 | 8 2 1 | 5 6 0 2 6 8 | 0 9 0 | 0 1 0 0 0 0 | 0 0 6 | 0 0 4 ---------|---------|--------- 0 0 0 | 0 0 0 | 2 3 9 0 0 0 | 0 0 0 | 0 0 0 4 1 5 | 0 0 0 | 0 0 0 ---------|---------|--------- 9 0 0 | 5 0 0 | 0 0 0 0 2 0 | 0 1 0 | 7 4 0 0 0 0 | 2 0 0 | 9 0 5 ************************************************** </code></pre> <p>As you can see by these printouts of the puzzle as it's being solved, it accepts a zero as the last number in the first column. I can't find anywhere in my code where it would allow that to happen. Also, I noticed when I was compiling that sometimes I would think I would run into memory that I was supposed to be in, but it allows me to go. I feel like my functions sometimes take things out of thin air. </p> <p>Here are my legality functions: </p> <pre><code>bool Board::isRowLegal(int row){ bool present[9] = {}; for(int i = 1; i &lt; theBoard.size(); ++i){ if(theBoard[row][i] != 0){ if(present[(theBoard[row][i]) - 1]){ return false; } present[(theBoard[row][i]) - 1] = true; } } return true; } bool Board::isColumnLegal(int column){ bool present[9] = {}; for(int i = 1; i &lt; theBoard.size(); ++i){ if(theBoard[i][column] != 0){ if(present[(theBoard[i][column]) - 1]){ return false; } present[(theBoard[i][column]) - 1] = true; } } return true; } bool Board::isPanelLegal(int rowStart, int colStart){ // Store the numbers in the panel in one vector. vector&lt;int&gt; currentPanel; for(int i = rowStart; i &lt; rowStart + THREE; ++i){ cout &lt;&lt; endl; for(int j = colStart; j &lt; colStart + THREE; ++j){ cout &lt;&lt; theBoard[i][j]; currentPanel.push_back(theBoard[i][j]); } } bool present[9] = {}; cout &lt;&lt; endl &lt;&lt; currentPanel.size() &lt;&lt; endl; for(int k = 0; k &lt; currentPanel.size(); ++k){ if(currentPanel[k] != 0){ if(present[currentPanel[k] - 1]){ return false; } present[currentPanel[k] - 1] = true; } } return true; } </code></pre> <p>I know it is confusing with the subscripts, but as a general rule, I start at subscript one in order to find the numbers. So the 7 in the first row, first column is coordinate 1, 1. Not 0, 0.</p> <p>I believe it is a bound issue, maybe I am not checking all the numbers in one instance, however my young programming eyes aren't seeing it.</p> <p>Also could someone explain why in the isPanelLegal I have to put present[currentPanel[k] - 1]. I can see why in the others because the vector starts at 1, but in isPanelLegal, the vector starts at zero since I just created it in the first part of the function. It works with the -1 and does not work without it.</p> <p>Recursion part...</p> <pre><code> if(board.isBoardFull()){ cout &lt;&lt; "here" &lt;&lt; endl; board.display(outStream); return true; } for(int i = ONE; i &lt;= NINE; ++i){ for(int j = ONE; j &lt;= NINE; ++j){ //cout &lt;&lt; "original" &lt;&lt; board.getSquare(i, j) &lt;&lt; "coord: " &lt;&lt; i &lt;&lt; ", " &lt;&lt; j &lt;&lt; endl; if(board.getSquare(i, j) == ZERO){ //cout &lt;&lt; "original: " &lt;&lt; board.getSquare(i, j) &lt;&lt; "coord: " &lt;&lt; i &lt;&lt; ", " &lt;&lt; j &lt;&lt; endl; for(int k = ONE; k &lt;= NINE; ++k){ board.setSquare(i, j, k); if(board.isLegal(1, 10, 1, 10)){ board.display(outStream); addSquare(depth, outStream); return true; } board.unsetSquare(i, j); } } } } board.display(outStream); return false; } </code></pre> <p>Thank you.</p>
 

Querying!

 
Guidance
An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload