Sign in to follow this  
Mad_Coder

What's this algorithms name\category be

Recommended Posts

I want to know how many solutions a sudoku puzzle can have in a single subsquare from with the numbers 1-9 in it, so I made an algorithm like process to doing it and was wondering if there are similiar algorithms to solving how to find all combinations of a bunch of numbers? The algorithm I am demonstrating is simplified using a 2X2 subsquare but shows the purpose still: NOTES:
  • X = blank square
  • When I write out a possible solution like shown below:
  • Solutions For XX XX 34 -> 3(1st)4(2nd) 21 -> 2(3rd)1(4th) I will write it out on a single line starting at the top left of the top row and go thorough to the second number of the row and go to the second row and do the same like this: 2321
  1. First I write all the numbers possible in ascending order as shown in our example of a 4X4 square with the numbers 1-4: 1234 Since out goal is to go through every combination untill the last combination is the equivelant of a circular loop ( or bitshift ) like 4321 we have a particular order we will go at so here are the rules:
    • We need to always keep track of:
    • The unchanging numbers and the changing numbers
  2. Next we start out with all numbers to not change but the last two to the most right, 3 and 4 which we'll swap to 1243
  3. now we have every combination for 12XX we need every combination for 1XXX: we keep 1 unchanges and swap one of the two numbers with the second number,2. We will first to the lower number 3 so keeping the result after that ascending so 1324 and then switch it around with 1342. Now that we have all the combinations for 13XX, lets get all of them for 1XXX by switching 3 with four and geting 1432 and 1423.
  4. now we do this entire process but changing 1 ( the most left, first number) with a number one greater untill we are at 4321 so 2431 2413 2314 2341 2134 2143 3412 3421 3214 3241 3124 3142 4123 4132 4213 4231 4312 4321

Share this post


Link to post
Share on other sites
If you just consider one subsquare with no other constraints, then any of the digits can be placed in any square; this is equivalent to arranging the symbols 1 .. 9 in any order. Each of these orderings is called a permutation, and there are 9! (9 factorial) of these for 9 symbols.

In C++, you can iteratively generate all permutations of a container using the standard library algorithm std::next_permutation.

Share this post


Link to post
Share on other sites
Oh, great deal thanks! I just figure out if there are 4 combinations for a 2 x 2 sub square, then the number of combinations with N subsquares will be 4^N, so I can just just do std::next_permutation((numbers.first(),numbers.last()))^N to get the total number of combinations for N number of subsquare with X numbers of numbers if this is correct.

Thanks Again,

This is is horrible that I haven't even gone over factorials yet in a math course and I want to do algorthims to find combination and not use sorting methods that are a load of garbage such as elementry sorting-bubble sorting etc...

Share this post


Link to post
Share on other sites
There are 24 combinations for a 2x2 subsquare, not 4. If you're hoping to scan through every possible set of 9 3x3 subsquares, each subsquare independently taking on every possible permutation (making (9!)^9 results in total), I hope you're prepared to wait until long, long past the heat death of the universe.

Also, std::next_permutation just returns one of the permutations; you have to call it for each permutation.

If you haven't done factorials or anything like that in math, you might just have to wait. This should get covered fairly early on in high school.

And if you want to use an intelligent sorting method, use the one that's built into the standard library: std::sort.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this