The Big Programming Thread - Page 400

Prev 1 398 399 400 401 402 1032 Next

Thread Rules
1. This is not a "do my homework for me" thread. If you have specific questions, ask, but don't post an assignment or homework problem and expect an exact solution.
2. No recruiting for your cockamamie projects (you won't replace facebook with 3 dudes you found on the internet and $20)
3. If you can't articulate why a language is bad, don't start slinging shit about it. Just remember that nothing is worse than making CSS IE6 compatible.
4. Use [code] tags to format code blocks.

pebble444

Italy2503 Posts

November 25 2013 11:48 GMT

#7981

Thank you for your advice RoyGBiv_13 and obesechicken13.

I have successfully made a website/blog, the host is blogger, which works well for now. Didn' t have to learn any html or java to set it up, while i' m not indipendent it works ok since my objective is to have a virtual place.

Shield

Bulgaria4824 Posts

November 25 2013 18:28 GMT

#7982

Sudoku

1.Enumerate all empty cells in typewriter order (left to right, top to bottom)

2.Our “current cell” is the first cell in the enumeration.

3.Enter a 1 into the current cell. If this violates the Sudoku condition, try entering a 2, then a 3, and so forth, until
a. the entry does not violate the Sudoku condition, or until
b. you have reached 9 and still violate the Sudoku condition.

4.In case a: if the current cell was the last enumerated one, then the puzzle is solved. If not, then go back to step 2 with the “current cell” being the next cell.
In case b: if the current cell is the first cell in the enumeration, then the Sudoku puzzle does not have a solution. If not, then erase the 9 from the corrent cell, call the previous cell in the enumeration the new “current cell”, and continue with step 3.

Is this even legitimate algorithm? I've tried to implement it but it runs forever.

I feel like this part

In case b: if the current cell is the first cell in the enumeration, then the Sudoku puzzle does not have a solution. If not, then erase the 9 from the current cell, call the previous cell in the enumeration the new “current cell”, and continue with step 3.

messes up everything.

I'm so stuck at implementing a sudoku solver that isn't hard to write. I'm aware of Knuth's dancing links but I think it'd be hard for me to implement.

Edit: it's possible I've made a mistake but I'm unfortunately blind to see it

Zocat

Germany2229 Posts

November 25 2013 18:52 GMT

#7983

It shouldnt mess up everything.

Imagine you change the algorithm to only check if the Sudoku condition is violated when there are 0 empty cells (so basically we change step 3). And imagine to go the recursive route.
What your algorithm does now is:
One enum with empty cells; some given enum with the initial values.
You take the 1st empty cell and set it to 1, now call the algorithm again with this new enum as the given enum.

Repeat and you will have a board where you only have the given values, and every other field has a 1.
You now check the Sudoku condition - which obviously fails.
So you remove the last 1 and set it to 2. This obviously fails again etc etc.
It might happen that every possible combination fails where you have a 1 in your initial empty field. You now set it to 2 and repeat.
If you reach 9 and it STILL doesnt work - you have no solution, since you checked every possible combination on the entire board.

Step 3 is only a speed up, since you dont need to check other combinations if you already know it's going to fail.

Edit: To clarify: Your algorithm is iterative, I mentioned the recursive approach(calling itself again), to maybe give you an insight how it works.
In your algorithm (if you change the check condition to complete only after every field is filled) you will also brute force every possible combination.

Maybe post your code, dunno.
I would "break" the loop at the highlighted part.

BlazingSonic

Germany51 Posts

November 25 2013 19:14 GMT

#7984

I might have a few tultra noob questions here. I just started to learn processing at an university. Very basic stuff. Is there anything you guys can tell me to make the process of learning this easier/ better? Are there any decent guides/ tutorials that explain it in a comprehensible way? Should I look at other languages to get a better understanding of the overall thing? Any advice you could give would be really appreciated as I don´t want to suck at this from the beginning xD

Shield

Bulgaria4824 Posts

November 25 2013 19:16 GMT

#7985

Since I don't know yet if I'm allowed to post code because of university's stuff, I'll just go with pseudo-code.

This is what I have now:


     for row = 0 to 9
         for column = 0 to 9
             if grid[row][column] is 0
                 grid[row][column] = 1

                 currentValue = grid[row][column]

                 while (!checkGrid) // the whole grid is validated
                      if currentValue < 9
                          grid[row][column]++
                          currentValue++
                      else
                          // this is to see if 9 is ok to be there
                          if (checkGrid)
                              break
                          else
                              // if not, then dead end
                              grid[row][column] = 0
                          
                              // if the previous cell is not on the same row
                              if (column is 0)
                                  column = 8
                                  row = row - 1
                              else 
                                   column = column - 1
                                   // the place I get stuck?

                                   // reset the previous cell's value to 0 
                                   // so the next iteration detects it as empty
                                   grid[row][column = 0

                                   // subtract column again because of 'for' loop's iteration
                                   column = column - 1
 
                                   break
     return true (this is when all  loops end, so solution is found?)

I hope I've expressed clearly what I do. I've added some comments just in case.

Edit: I've fixed some mistakes

Edit #2: I'm aware I don't go back to the previous empty cell and that I go back to just the previous cell (regardless if it is empty), but it doesn't work even in this case

spinesheath

Germany8679 Posts

November 25 2013 19:30 GMT

#7986

I'd just use a stack of things that are/identify cells, makes it a lot easier to move back to the previous cell.
If you don't know where you enter an infinite loop, just run the program with a breakpoint and check it out by executing a couple of steps.

Don't do things like

grid[row][column]++
currentValue++

Grab the currentValue inside of the while loop istead. Modifying the original and the copy is bad. Modify the original and make a new copy. This is likely where your bug comes from too, you probably don't have the right currentValue after moving back a cell (didn't verify though).

Shield

Bulgaria4824 Posts

November 25 2013 19:43 GMT

#7987

On November 26 2013 04:30 spinesheath wrote:
I'd just use a stack of things that are/identify cells, makes it a lot easier to move back to the previous cell.
If you don't know where you enter an infinite loop, just run the program with a breakpoint and check it out by executing a couple of steps.

Don't do things like

grid[row][column]++
currentValue++

Can you please clarify how you'd use the "stack of things that are/identify cells"? I've also noticed it may be one of my problems.

spinesheath

Germany8679 Posts

November 25 2013 19:56 GMT

#7988

On November 26 2013 04:43 darkness wrote:

Show nested quote +

grid[row][column]++
currentValue++

Can you please clarify how you'd use the "stack of things that are/identify cells"? I've also noticed it may be one of my problems.

There are plenty of options, partially depending on your implementation.
For example you could have a stack of pointers/references to the cells if your language supports that. Potentially with the cells being classes instead of ints.
Or you could have a stack of (row, column) pairs.
Or, preferably if you implement the sudoku grid as a single array of length 81, just a stack of ints as the indices in the sudoku grid array.

As you work your way through the algorithm, whenever you start working on a new cell, you push the cell identifier on top of the stack and work with the top of the stack. Whenever you need to go to the previous cell, you just pop the top of the stack.

dae

Canada1600 Posts

November 25 2013 20:41 GMT

#7989

A simple optimization for sudoku solving is keep track of the number of different valid entries for each cell. For each step the "next" cell you go to solve is the one that has the least number of possible choices for it.

This adds a bit of overhead of adding/removing possible options from cells as you try out options, but it massively reduces in size the backtracking tree.

Of course this way you cant just iterate over all the cells, and have to maintain some sort of queue.

centirius

Sweden40 Posts

November 25 2013 20:43 GMT

#7990

On November 26 2013 04:16 darkness wrote:
Since I don't know yet if I'm allowed to post code because of university's stuff, I'll just go with pseudo-code.

I think you should consider splitting this into multiple smaller functions, both to make it much easier to test individual parts and simpler to understand.
I'd consider a structure like this but you'd obviously have to write the code to check if a grid is valid etc yourself:


public SolveSudoku(Grid)
{
    if(tryToSolve(Grid))
        return;
    else
        throw new InvalidInputException()
}

private boolean checkGrid(Grid)
{
   if(sudokuconditions)  
       return true;
   else
       return false;
}

private int getNextOpenPosition(Grid)
{
    //find position, if grid is full return -1
}

private boolean tryToSolve(Grid)
{  
    int currentPosition = getNextOpenPosition(Grid) 
    if(currentPosition == -1)                        //grid is full
           return true;
    for(int i = 1; i < 10; i ++)
    {
          Grid[currentPosition] = i;
          if(checkGrid(Grid))                        //the number inserted does not break any rules
              if(tryToSolve(Grid))                //do the same for the next position on the grid
                   return true; //if the next position works, and consequently everything after that

                                         // else just keep the loop going and try the next number
    }
    return false;   //no numbers work, return false (means a previous number was wrong)
}

Of course, I'm not sure what language you're using so you might have to pass the grid back when you reach the end of the recursion, depending on how it handles array references and such.
This has not been tested btw, but is mostly to illustrate how much simpler it can get if you split up the different parts into different functions.

Edit: damn formatting is annoying

gedatsu

1286 Posts

November 25 2013 21:01 GMT

#7991

I wrote a sudoku solver for an introductory programming course a few years ago, the main structure looked like this:

int[][] board = new int[9][9];

main {
  initialize preset values to 1-9. all other cells should be set to 0
  if (solve(0)) {
    //solution is now stored in board.
  }
}

boolean solve(int cell) {
  if (cell > 80) return true;
  int row = cell/9;
  int col = cell%9;
  if board[row][col] != 0 return solve(cell+1);
  for (int i = 1; i < 10; i++) {
    if (okToPlace(i,row,col)) {
      board[row][col] = i;
      if (solve(cell+1)) return true;
      board[row][col] = 0;
    }
  }
  return false;
}

boolean okToPlace(int i, int row, int col) {
  return true if placing i in board[row][col] is legal with regards to all existing values
  else return false
}

Of course, this thing is pretty slow and very dumb. It is a much more interesting challenge to write a solver that doesn't brute force a solution.

Shield

Bulgaria4824 Posts

November 26 2013 17:51 GMT

#7992

@gedatsu
What I don't understand is why there is no backtracking if all 9 numbers fail. E.g. cell - 1 to go back to the previous cell. Maybe I'm missing something?

gedatsu

1286 Posts

November 26 2013 18:03 GMT

#7993

On November 27 2013 02:51 darkness wrote:
@gedatsu
What I don't understand is why there is no backtracking if all 9 numbers fail. E.g. cell - 1 to go back to the previous cell. Maybe I'm missing something?

If all 9 numbers fail, you will reset the value to 0, exit the loop and return false. That means the calling function will have to take another step in its own loop, i.e. a different value is tried in the preceding cell.

Fawkes

Canada1935 Posts

November 26 2013 18:32 GMT

#7994

Does anybody know how I can keep track or make "sets/lists" of checkboxes on a form?

Right now my form has 3 sets of checkboxes which are used to answer 3 different questions. I am writing javascript code to do validation on these "sets", however I am unsure on how to pull them. The validation I am trying to write is to ensure at least one is checked. I do believe I understand how to do this part, I am just unsure on how I can group the checkboxes or pull them in the groups that I want without hardcoding like what I mention below:

For the first set, I initially just used if statements and hardcode their names because the set of checkboxes was small and it would be only 5 nested ifs, however for the later sets of checkboxes, there may be 20+ options so this seems unfeasible. I tried looking at the DOM element.getElementsByTagName(), however this would return every single checkbox on the form if I understand it correctly.

centirius

Sweden40 Posts

November 26 2013 18:52 GMT

#7995

On November 27 2013 03:32 Fawkes wrote:
Does anybody know how I can keep track or make "sets/lists" of checkboxes on a form?

Right now my form has 3 sets of checkboxes which are used to answer 3 different questions. I am writing javascript code to do validation on these "sets", however I am unsure on how to pull them. The validation I am trying to write is to ensure at least one is checked. I do believe I understand how to do this part, I am just unsure on how I can group the checkboxes or pull them in the groups that I want without hardcoding like what I mention below:

For the first set, I initially just used if statements and hardcode their names because the set of checkboxes was small and it would be only 5 nested ifs, however for the later sets of checkboxes, there may be 20+ options so this seems unfeasible. I tried looking at the DOM element.getElementsByTagName(), however this would return every single checkbox on the form if I understand it correctly.

I'm far from an expert on javascript, but if there is no built in way to do this, you could put the checkboxes inside a div and then loop through everything in the div.
pseudocode:



<html>
<div id="boxgrp1">
<input type = checkbox>
<input type = checkbox>
</div>
</html>

javascript (not sure if this is the correct syntax/correct methods to call, but something similar should be possible.)

var children = document.getElementById('boxgrp1').childNodes;
for(int i = 0; i < children.length; i++)
{
     var theCheckbox = children[i];
     //do whatever you wanted to do
}

tl;dr : put each group of checkboxes in a seperate div, give each div an id and use javascript to find the div and get it's content.

devilesk

United States140 Posts

November 26 2013 19:13 GMT

#7996

On November 27 2013 03:52 centirius wrote:

Show nested quote +

I'm far from an expert on javascript, but if there is no built in way to do this, you could put the checkboxes inside a div and then loop through everything in the div.
pseudocode:



<html>
<div id="boxgrp1">
<input type = checkbox>
<input type = checkbox>
</div>
</html>

javascript (not sure if this is the correct syntax/correct methods to call, but something similar should be possible.)

var children = document.getElementById('boxgrp1').childNodes;
for(int i = 0; i < children.length; i++)
{
     var theCheckbox = children[i];
     //do whatever you wanted to do
}

tl;dr : put each group of checkboxes in a seperate div, give each div an id and use javascript to find the div and get it's content.

You could also group checkboxes by giving them the same class name

http://jsfiddle.net/qyE97/ from http://stackoverflow.com/questions/11787665/making-sure-at-least-one-checkbox-is-checked

supereddie

Netherlands151 Posts

November 26 2013 20:20 GMT

#7997

Just set the name attribute of the checkboxes that belong to the same 'set' to the same value (the same way how radio groups work).


<input type="checkbox" name="set1" id="q1" value="1" /><label for="q1">My question 1</label> 
<input type="checkbox" name="set1" id="q2" value="1" /><label for="q2">My question 2</label>

Then you can use getElementsByName in javascript to enumerate over them and do your check.

supereddie

Netherlands151 Posts

November 26 2013 20:20 GMT

#7998

*deleted*

Fawkes

Canada1935 Posts

November 26 2013 20:40 GMT

#7999

On November 27 2013 05:20 supereddie wrote:

Show nested quote +

Just set the name attribute of the checkboxes that belong to the same 'set' to the same value (the same way how radio groups work).


<input type="checkbox" name="set1" id="q1" value="1" /><label for="q1">My question 1</label> 
<input type="checkbox" name="set1" id="q2" value="1" /><label for="q2">My question 2</label>

Then you can use getElementsByName in javascript to enumerate over them and do your check.

The problem with this, I am currently using isset($_POST['namegoeshere']) to do the confirmation page for my form, currently all my checkboxes have different names which let me do this. This uses the name attribute doesn't it? What would happen if I changed a set of checkboxes to the same name and tried to do that.

If I had a line in my scripts that did document.apply.firstname.value == "", apply is the form name, is firstname refering to the object that has name firstname or the variable in the form?

tofucake

Hyrule19228 Posts

November 26 2013 20:45 GMT

#8000

set the name to namegoeshere[] and then they get posted as an array

Prev 1 398 399 400 401 402 1032 Next

Please or register to reply.

The Big Programming Thread - Page 400

Completed

Ongoing

Upcoming