How do I fix this String problem?

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:

4 1 3 2
3 2 4 1
2 3 1 4
1 4  3 2
Tagged:

Answers

  • and the problem is?

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

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

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

  • edited January 2018 Answer ✓

    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!

  • edited January 2018

    It‘s not your code, correct?

  • 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

    ?

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

  • edited 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

  • 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?

  • edited January 2018
     ----------
    | 4     2 |
    |   2     |
    |     1   |
    | 1     3 |
     ----------
    

    and

    4 1 3 2 
    3 2 4 1 
    2 3 1 4 
    1 4 2 3
    
  • edited January 2018

    oh, I found the issue in the code.

    Nice one.

  • edited January 2018 Answer ✓

    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

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

    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().

  • Answer ✓

    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.

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

  • Did you learn nothing from the last Potterhouse question?

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

  • That is not a reply.

    Please post your entire code.

Sign In or Register to comment.