Raed Tabani

Ranch Hand

Posts: 50

posted 2 years ago

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

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

Stephan van Hulst

Saloon Keeper

Posts: 7806

142

posted 2 years ago

- 1

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:

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

`Collection<Integer> difference = new ArrayList<>(a);`

difference.removeAll(b);difference.removeAll(b);

*The mind is a strange and wonderful thing. I'm not sure that it will ever be able to figure itself out, everything else, maybe. From the atom to the universe, everything, except itself.*

Piet Souris

Rancher

Posts: 1979

67

Stephan van Hulst

Saloon Keeper

Posts: 7806

142

posted 2 years ago

- 1

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.

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

posted 2 years ago

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

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

2ndGroup.png

3rdGroup.png

Raed Tabani

Ranch Hand

Posts: 50

posted 2 years ago

@ 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

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

posted 2 years ago

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

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: 1979

67

posted 2 years ago

- 2

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

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

posted 2 years ago

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 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: 1979

67

posted 2 years ago

- 1

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

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