How do I fix this String problem?

Potterhouse · January 2018

This is supposed to solve this soduko problem.

The rules of this Sudoku:

Each row may only have the numbers 1 through 4 appearing once in it. Each column may only have the numbers 1 through 4 appearing once in it. The bold lines separate the game board into four quadrants. Each quadrant may only have the numbers 1 through 4 appearing once in it. Each puzzle has a unique solution.

Input:

4,,,2
,2,,
,,1,
1,,,3

Output:

koogs · January 2018

and the problem is?

Potterhouse · January 2018

@koogs, It does not complete it, it only says "NONE".

KevinWorkman · January 2018

What happened when you debugged your code? Which line is behaving differently from what you expected?

Potterhouse · January 2018

@KevinWorkman, it prints out NONE, instead of the solved puzzle

TfGuy44 · January 2018

Okay. So your program is not giving you the output you expect. So there is a problem somewhere in the code that causes it to give the wrong output. Your job is to debug the code. Make sure that each step the sketch takes is doing what you would expect it should do.

Start at the beginning. Does your code read the problem correctly? Does it parse the problem properly? Check that it does by having it display for you the parsed problem.

What step does your sketch take next? Does it look at the cells in order? Is it looking at them in the right order? Can you have it tell you which cell it is looking at, and what value is there? What does it do to the cell, if anything? Can you have it tell you what it does?

If you make your code explain what steps it is taking when it executes, you might see that it is doing the wrong thing at some point.

Debugging! Do some!

Chrisir · January 2018

It‘s not your code, correct?

Chrisir · January 2018

SHOULDN‘T you format this as code so that it’s shown in a grid:

Input: 4,,,2 ,2,, ,,1, 1,,,3

Output: 4 1 3 2 3 2 4 1 2 3 1 4 1 4 2 3

?

Potterhouse · January 2018

@Chrisir, it is supposed to come out as a grid.

Chrisir · January 2018

I mean the formatting of your post

Input: 4,,,2 ,2,, ,,1, 1,,,3

Output: 4 1 3 2 3 2 4 1 2 3 1 4 1 4 2 3

TfGuy44 · January 2018

Just checking in here. How is your debugging going? Have you narrowed your problem down to a step that isn't doing the right thing yet?

Chrisir · January 2018

 ----------
| 4     2 |
|   2     |
|     1   |
| 1     3 |
 ----------

and

Chrisir · January 2018

oh, I found the issue in the code.

Nice one.

Chrisir · January 2018

I see, you haven't worked on this yet, except for writing me an e-mail

so let's have a look.

you have the problem

 ----------
| 4     2 |
|   2     |
|     1   |
| 1     3 |
 ----------

and its solution

But the sketch doesn't find this solution. So the program has an error.

You want to find this error (or have me finding it for you. But then you won't learn)

finding an error is called debugging.

Understanding the Path

Since the code is not by you, you need to understand the code first, especially which path processing is taking through the code during executing it.

What do I mean by path processing is taking?

e.g. in this code

 size(400, 400);
 background(192, 64, 0);
 stroke(255);
 line(150, 25, 270, 350);

(full working sketch) the path taken is line by line.

In this code the path is similar but skipping the last two lines because of the if:

size(400, 400);
background(192, 64, 0);
stroke(255);
if (true) 
  line(150, 25, 270, 50);
else                          // skipped !!!!!!!
  line(150, 25, 270, 350);        // skipped !!!!!!!

Similar, here

size(400, 400);
background(192, 64, 0);
stroke(255);
if (false) 
  line(150, 25, 270, 50);  // skipped !!!!!!!!!!!!!!!!!!!!!
else
  line(150, 25, 270, 350);

one line is skipped.

Now, here

 void setup() {
   size(400, 400);
   stroke(255);
   background(192, 64, 0);
 } 

 void draw() {
   line(150, 25, mouseX, mouseY);
 }

the path is more complicate since we have two functions and draw runs again and again endlessly (path goes from last line back to start of draw()). But you got the path idea.

To follow the path is essentially for debugging.

Looking at the importance steps on the path and where your error must lie is important for debugging.

Understanding the functions

Now, to do this, you must understand the code. Start by making a list of the functions:

setup()
solve()
legal() 
parseProblem()
writeMatrix()

let's see whether they return something as a result:

setup() - no
solve() - yes, boolean 
legal() - yes, boolean 
parseProblem() - yes, the matrix 
writeMatrix() - no

let's see who is calling who:

setup() - called by processing itself (like mousePressed) implicitly
solve() - called by setup()
legal() - called by solve()
parseProblem() - called by setup()
writeMatrix() - called by setup()

we can express the dependency graphically: The indents symbolize who is calling whom:

setup() - called by processing itself (like mousePressed()) implicitly
    solve() - called by setup()
         legal() - by solve()
    parseProblem() - by setup()
    writeMatrix() - by setup()

Understanding the single functions

setup() is straight forward. Debugging: probably no error
parseProblem() sets up the Matrix. Do you realize that this: String theProblem = "004 032 112 221 301 333"; is not a matrix but a line of commands setting up the matrix? Read : Place "4" at position 0,0 in the matrix, place 2 at position 0,3 in the matrix etc. etc.; very good code. parseProblem() has the job to convert this to a matrix. This way you get:
```
 ----------
| 4     2 |
|   2     |
|     1   |
| 1     3 |
 ----------
```
writeMatrix() is straight forward. Debugging: probably no error, because one matrix is shown nicely already (the initial matrix). But writeMatrix() is a suspect: we could have a correct matrix internally that is not shown correctly. Not the case here.
solve() seems complex. Probably suspect: source of error.
legal() seems complex. It's used by solve() in an important way. Probably suspect: source of error.

The function solve()

Now, let's look at solve(). Main candidate for error. The thing is that it calls itself. This is confusing. It's called recursion. See Wikipedia here.

Here is an example of making a grid recursively. This is another sketch, nothing to do with our task (or almost nothing):

int num=0; 


void setup() {
  size(322, 322); 
  textAlign(CENTER);
  drawText(0, 0);
}

void drawText(int i, int j) {

  if (i == 4) {  // last cell in the line
    i = 0;         // new line 
    if (++j == 4)  // increase j and check against 4 
      return;          // end of grid, leave function
  }

  text(num, i*32+42, j*32+42);
  num++;

  drawText(i+1, j);  // next cell to the right (i+1)
}

Please look at solve() closely and understand it. It's moving through the fields cell by cell and trying to place val 1,2,3 or 4 there in the for-loop. The function legal() is used to check the move:

    if (legal(i, j, val, cells)) {

In solve(), we have another technique working:

backtracking!!! See https://en.wikipedia.org/wiki/Backtracking

or more specifically I'd call it recursive backtracking algorithm.

As the name suggest, it can try moves on the matrix and can take them back (backtracking) and try another move.

Here is an example of how it is working:

depth 9 (at end)
 ----------
| 1 3 4 2 |
| 3 2     |
| 2 4 1   |
| 4 1   3 |
 ----------
depth 8 (at end)
 ----------
| 1 3   2 |
| 3 2     |
| 2 4 1   |
| 4 1   3 |
 ----------
depth 7 (at end)    taking back "1" !!!!!!!!!!!!!!!!
 ----------
| 1 3   2 |
| 3 2     |
| 2 4 1   |
| 4     3 |
 ----------
depth 6 (at end)       taking back "4" !!!!!!!!!!!!!!!!
 ----------
| 1 3   2 |
| 3 2     |
| 2   1   |
| 4     3 |
 ----------
depth 5 (at start)     taking back "3" and replace it with 4 !!!!!!!!!!!!!!!!
 ----------
| 1 4   2 |
| 3 2     |
| 2   1   |
| 4     3 |
 ----------
depth 6 (at start)
 ----------
| 1 4   2 |
| 3 2     |
| 2   1   |
| 4     3 |
 ----------
depth 7 (at start)
 ----------
| 1 4   2 |
| 3 2     |
| 2 3 1   |
| 4     3 |
 ----------
depth 8 (at start)
 ----------
| 1 4   2 |
| 3 2     |
| 2 3 1   |
| 4 1   3 |
 ----------
depth 9 (at start)
 ----------
| 1 4 3 2 |
| 3 2     |
| 2 3 1   |
| 4 1   3 |
 ----------

As you can see he's working a way to a solution (he's doing it columnwise) but he has to take back a few moves from the second column and try again with another value. That's backtracking.

Remark: with your problem

    //String theProblem = "004 032 112 221 301 333"; // OK - the original problem

no backtracking would occur because it's not necessary to take back a move.

But it would occur here:

        // String theProblem = "001 032 112 221 304 333"; // swapped 4 and 1 (positions 0,0 and 3,0)

Idea

Since setup() gives "None" as a result, solve() is returning false.

This could be caused by legal(). So legal() would return false too often.

As said, this line is checking the move by using legal():

  if (legal(i, j, val, cells)) {

idea is now to replace this line.

if legal() is returning false too often, we try instead of if (legal(i, j, val, cells)) { now just if (true) {

Immediately we get:

solution =========
 ----------
| 4 1 1 2 |
| 1 2 1 1 |
| 1 1 1 1 |
| 1 1 1 3 |
 ----------

This is interesting and teaches us:

the grid is filled completely now
the rules are not followed (many 1 in one column etc.). The result is wrong. But there is a result.
legal() is the key for keeping the rules (hence its name)
legal() could be causing the error, when it returns false too often

So your goal is now to analyze the function legal().

TfGuy44 · January 2018

So what does legal() do?

It determines if you are allowed to place a given value in a given cell on a given board.

Thus, this function needs to make sure that the rules of which values can go in a cell are all obeyed.

There are three such rules.

No value can appear twice in the same row.

No value can appear twice in the same column.

No value can appear twice in the same quadrant.

Does the code in legal() check all three of these rules?

You will have to look at what it is doing - line by line - and understand what the code does!

When you find the problem, you will understand why it's the problem - because you will have found a discrepancy between what you think the code should be doing and what it is actually doing.

Chrisir · January 2018

He just sent me an complete new program for Sudoku as a private message..... crazy.......

koogs · January 2018

Did you learn nothing from the last Potterhouse question?

Potterhouse · January 2018

I figured it out, thank you for the guidance, @Chrisir, and @TfGuy44

Chrisir · January 2018

That is not a reply.

Please post your entire code.

Howdy, Stranger!

Categories

In this Discussion

How do I fix this String problem?

Best Answers

Answers