• Post Reply Bookmark Topic Watch Topic
  • New Topic

which is a better sudoku logic?  RSS feed

 
Raed Tabani
Ranch Hand
Posts: 50
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I'm trying to populate a 9x9 soduku grid. so far I've made a shrinking(remove choosen elements) arraylist of numbers(1-9) to populate
the rows, and the arraylist itself gets repopulated after each row is complete. but before placing any number, and subsequently removing it from the Arraylist, the compiler need to
check vertically ,column fixed but row changing from(0-8), to see if such number
exists. my first question is, which of these two is better logically and programtically:

1- a-randomly pick an available number from arrayList
b-using a for loop fix the column and check each row from 0-8 for similar number
c-case a match is found, re pick a number and start loop again
d-case it's unique, break loop and place number

2- a-before randomly picking any number, check what numbers are already placed vertically.
b-exclude placed numbers from list of available numbers to place(Please see other question below)
c-place number


my second question, is regarding the second method and more precisely step b, how to exclude placed numbers from list of numbers available for placement?
my first thought was to build a list of placed numbers and check weather the randomly picked number is a match, if so then pick a different number etc
but I cant help but feel that this could be achieved with the help of arrayLists, one that is increasing(placed numbers) and one is decreasing
it's almost as if one is giving elements to the other, which would look something like the picture


secondMethod.png
[Thumbnail for secondMethod.png]
 
Stephan van Hulst
Saloon Keeper
Posts: 6981
110
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
For each row, you should generate a set containing the numbers 1 through 9. Then, for a column, you need to get the difference between your row set, and the column set. Pick a random value from that difference set, put it in your grid and subtract it from your row set.

Set difference (a\b) can be achieved like this:

Collection<Integer> difference = new ArrayList<>(a);
difference.removeAll(b);
 
Piet Souris
Rancher
Posts: 1783
55
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Don't forget you have the 9 squares as well.

I did not use arraylists for my sudoku, but BitSets instead,
and found these to be ideal for the job at hand. See the API,
and look for methods that come in very handy.

Greetz,
Piet

 
Stephan van Hulst
Saloon Keeper
Posts: 6981
110
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Yeah Piet is right, I forgot about the squares.

What I did in a past implementation was to have a Sudoku consist of unique cells, and of collections of cells that form a group. You can then determine which groups overlap where, and which cells may never have the same value.
 
Raed Tabani
Ranch Hand
Posts: 50
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I totally forgot about the 9 squares ! it's been a while since I played sudoku
but after giving it some thought, I think it's doable with just the same methods(especially the second) and I think this is what Stephan was referring to, which is,
to generate certain collections of cells at different stages, so that at any given time you are only comparing it with rows and columns without the need for an extra filter(for within the collection)
I made some pics to demonstrate
1stGroup.png
[Thumbnail for 1stGroup.png]
2ndGroup.png
[Thumbnail for 2ndGroup.png]
3rdGroup.png
[Thumbnail for 3rdGroup.png]
 
Raed Tabani
Ranch Hand
Posts: 50
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
and lastly this group
4tgroup.png
[Thumbnail for 4tgroup.png]
 
Raed Tabani
Ranch Hand
Posts: 50
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
@ stephan
Collection<Integer> difference = new ArrayList<>(a);
difference.removeAll(b);
did the job for me

@Piet
this is my first time hearing about bitsets. I got some reading to do
 
Raed Tabani
Ranch Hand
Posts: 50
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I'm stuck, I don't know if I can do it or if it's doable this way...so far what I've done is:
1- populate soduku grid Collection by Collection, instead of row by row, with the same order in the picture .
2- 1st Collections added easily, which are upperLeft,Middle and bottomRight.
3- adding the fourth collection was challenging and it's where I'm stuck atm...my logic was to build four Dynamic ArrayLists:

1- an ArrayList called collectionNumbers which is populated with integer values from 1-9
2- an ArrayList called toBeExcludedNumbers, which is generated by checking vertically and horizontally for any given cell
3- an ArrayList called availableNumbers which = collectionNumbers-toBeExcludedNumebrs
4- an arrayList called placedNumbers, which adds and subsequently removes placed numbers from CollectionNumber to make sure a number is never provided twice in same collection

at first I tried populating cells within a given collection row by row, but I found that I was always stuck at final row as the numbers that been placed completely disregard numbers present in neighboring cells but at different rows. so I decide that I would populate my collections the same way I populate my gird ie in four steps starting with upperLeft,Middle and bottomRight. . and that did work at times and didn't at others which I assume for the same reason, due to random placement of previous numbers I'm left, at times, with unplaceable ones.
so I came to the conclusion, it's undoable this way? I need help....

 
Piet Souris
Rancher
Posts: 1783
55
  • Likes 2
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
hi Raed,

interesting problem, isn't it? You're bound to get stuck from time to time,
by filling each cell at random, given the digits left.

You can google for clever algorithms, no doubt you'll find them in abundance.

But what about doing it using brute force? Just try every possibility until
you either get stuck or you are finished. A start would be to fill the first row,
or square, or column at random, or using your strategy of filling the first
three squares at rondom (they are indeed unconstrained), and brute force
from there? If you get stuck, then return on the path until you can try
another possibility. In other words: Depth-First-Search.

The experience you will gain is very useful. Think about how you would do
brute force, given the empty cells. If you have an empty cell, what digits
are still possible? How would you pick one of these digits, and how do you
proceed? And what if you find that no digits are possible? Then what?

Well, it'll keep you busy for at least today!

Greetz,
Piet
 
Raed Tabani
Ranch Hand
Posts: 50
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Piet Souris wrote:

The experience you will gain is very useful. Think about how you would do
brute force, given the empty cells. If you have an empty cell, what digits
are still possible? How would you pick one of these digits, and how do you
proceed? And what if you find that no digits are possible? Then what?

Well, it'll keep you busy for at least today!

Greetz,
Piet

Hi Piet,
very interesting and time consuming indeed!
I think,like you just said this path boils down to "how to pick one of these digits" , so far I've been doing it randomly
but what I'm thinking instead, of these available numbers, which will not be available ie can't be placed in the next cell to be filled? and that number is placed
I'm not sure how easy it will be to implement this logic in code but I'm feeling it will keep me busy for a while
 
Piet Souris
Rancher
Posts: 1783
55
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
hi Raed,

well, it is not an easy task, filling a complete sudoku. But, as I said,
a task that will give you quite some interesting things to experiment
with.

Okay, some words about how I did it.

First of all, my program simply solves sudoku's. I 'borrowed' the
Google Sudoku layout, and after the user had set up a sudoku, then,
as soon as the user pressed 'finished set up', I start a Thread
with an arraylist of empty cells. I use a dedicated class for a cell.

Now, I just go from element 0 to element last, filling in possible
digits, until I reach a point where a cell cannot be filled for lack
of digits, or otherwise I'm done.

For the administration, I use arrays of size 9, three of 'm,
one for the nine columns, one for the nine rows and one for the nine
squares. The elements of these three arrays are, as I said earlier,
BitSets. I use BitSets of length 10, bit 0 is unused, I only
use the bits 1-9.

Now, suppose I have an empty cell. From instance members I know
the row R, column C and square S.
The BitSets for row R, column C and square S are br[R], bc[C] and
bs[S]. Now, a 1 in a BitSet, on position p, means that digit p is
still possible. A 0 means that digit p is not possible.

Now, what would I get if I do;


What about: possible.nextSetBit(0)? And what would it mean
if: possible.cardinality() == 0? And if I set the value of the cell
to digit D, what does that mean for the row, column and square
BitSets in question?

Well, all the above can be done with ArrayLists, Sets and the like.
But I found the use of BitSets to be ideal for this.

Hope I gave you some ideas, Think about it.

Greetz,
Piet
 
Don't get me started about those stupid light bulbs.
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!