Messages

376

Developer's Corner / Re: A decade and a half of instability: The history of Google messaging apps

« on: August 27, 2021, 11:44 AM »

Google Talk was the best! Killing it in favor of Google Hangouts and whatever else has come since then was a mistake.

377

General Software Discussion / Re: Windows 11 Announced

« on: August 26, 2021, 03:00 PM »

Looks like the Windows 11 leak was kind of an early kludge of new features, and the changes for the official thing are more extensive than it first appeared:

Windows 11 is bigger than we thought - Linus Tech Tips

378

Living Room / Re: Programming/Coder humor

« on: August 24, 2021, 04:22 PM »

There are two hard problems in programming: Naming things, caching things, and off-by-one errors.

379

DC Gamer Club / Re: Latest GOG Giveaway

« on: August 20, 2021, 02:04 PM »

Quake 2 RTX is free on GOG if you grab it within the next couple of days: https://www.gog.com/game/quake_ii_rtx

EDIT: I just saw that it only includes 3 levels from the shareware version. If you want access to all levels, you need to buy Quake II: Quad Damage (which is currently on sale for $3).

So it's more of a ray-tracing mod that requires you to own the full version separately.

380

General Software Discussion / Re: Gizmo's Tech Support Alert freeware site shutting down

« on: August 19, 2021, 11:19 AM »

Think it wouldn't be much of a problem to host somebodies data, as long as you and "they" can never know what's inside.
That, plus a BAT tip of sorts for the extra bandwidth.

-dantheman (August 18, 2021, 04:23 PM)

Sounds like you're describing Filecoin, which is another (cryptocurrency-based) file-storage technology being developed by the folks who developed IPFS.

By the way, you can see stuff that uses IPFS here, if you'd like to explore a bit: https://awesome.ipfs.io/

Don't know about a browser but we had a couple of ISPs that provided free internet if you allowed them to show you ads - they didn't last very long.

-4wd (August 18, 2021, 06:09 PM)

In the USA there was one called NetZero. IIRC, they lasted a surprisingly long time, but eventually abandoned the adware model and went to normal subscriptions.



Oh wow. I just did a search and it seems they're still alive. And in addition to their subscriptions, they're still offering 10 hours of free dial-up per month. I didn't know dial-up was still a thing. It probably uses up the whole 10 hours just to load the Google home page on dial-up. . .

381

General Software Discussion / Re: Gizmo's Tech Support Alert freeware site shutting down

« on: August 18, 2021, 01:18 PM »

Not quite sure yet on how this all works but IPFS is sure making the news!
Brave browser seems to be pretty strong on this.

It sounds like a peer to peer thing to me, but if it is reliable and secure... that is the question!

-dantheman (August 18, 2021, 07:58 AM)

I started a thread on IPFS about 6 years ago. To me it still sounds like a really great idea. If you're just a consumer looking to download some files or browse some content hosted on IPFS, then it's not a much different experience than the standard WWW.

The problem, as I see it, is when you want to host some content using IPFS. Until it gains much more widespread adoption, it's basically just you running a fileserver on your own system(s). On the one hand, if what you're hosting isn't very popular, then I suppose it won't take much of your system resources (and possibly ISP-limited data cap) to serve to others. On the other hand, if what you're hosting is very popular, then the nature of IFPS is that it will likely be distributed and "mirrored" by many others who can help offset some of the load.

But maybe a person who was adequately motivated could set up some cloud service such as Oracle Cloud Free Tier and have that running an IPFS server for hosting/serving IPFS content without exposing your personal/home PC to the public like that.

382

General Software Discussion / Re: Help Installing Tray Weather

« on: August 14, 2021, 02:10 PM »

Deozaan how do I get a API  I am not a computer savy can you please tell me the directions to install it please

-sportman12 (August 13, 2021, 06:06 PM)

I don't know. But it looks like there's a link in your screenshot. It probably has instructions. Read carefully and follow the instructions and I think you'll do fine.

383

General Software Discussion / Re: Help Installing Tray Weather

« on: August 13, 2021, 12:15 PM »

The words written in red at the bottom of your screenshot seem to indicate that you have not gotten an API key as instructed.

384

DC Gamer Club / Re: Latest GOG Giveaway

« on: August 07, 2021, 10:33 AM »

Consoles don't really interest me. Although I have seen videos today from a preview of the 'Steam deck' from Valve. The most expensive version has a retail price of 650 USD, but it can do a lot. That is a seriously capable little game machine...until you hook up a USB dongle and connect a monitor, Ethernet, mouse and keyboard to it. Then it is a pretty decent Linux computer too. And you can still use the built-in screen when a second monitor is connected. It has the makings of a Nintendo Switch "killer", it does everything a Switch can do and then a whole lot more.

And of course, it will play GoG games with ease 

-Shades (August 07, 2021, 05:39 AM)

Even though I have been favoring GOG over Steam as much as possible for the past several years, my problem with the idea of the Steam Deck and GOG is that GOG has really been pushing for adoption of their Steam-like client, GOG Galaxy. Some features (such as multiplayer!) are locked behind its usage. But it doesn't support Linux. . .


P.S. there's a thread for Steam Deck here: https://www.donation...ex.php?topic=51571.0

385

DC Gamer Club / Re: Latest GOG Giveaway

« on: August 07, 2021, 03:32 AM »

Syndicate Plus, Syndicate Wars, and Ultima Underworld 1 & 2 are all free on GOG until Sept 3:

https://www.gog.com/...rworld_and_syndicate

Links to individual games:

https://www.gog.com/game/syndicate
https://www.gog.com/game/syndicate_wars
https://www.gog.com/...ltima_underworld_1_2

386

Living Room / Re: Who here makes ice cream?

« on: August 05, 2021, 01:22 PM »

I generally dislike cooking and have never really been interested in cooking shows, but I discovered Glen and Friends Cooking YouTube channel a while ago and have watched many of his videos since. He does all kinds of strange and interesting things. He also does "normal" things, too, I guess. But anyway, he has done a couple ice cream recipes lately:


(Savory) Mac and Cheese Ice Cream:

Toblerone Ice Cream (Churn-free)

387

DC Gamer Club / Re: Chronicles of Elyria

« on: August 02, 2021, 05:41 PM »

I just started watching this (only a minute into it) and it sounded slightly familiar. So I searched and found this thread. I figure I'd post this here for any who might be interested.



The MMO which never existed - The admirable stupidity of Chronicles of Elyria

388

Developer's Corner / Re: Constructing a minimal Sudoku puzzle

« on: July 29, 2021, 01:09 PM »

Javascript version that runs in your browser: jsSudoku

It's generating puzzles almost immediately on my computer at any of the 5 difficulty levels.

-4wd (July 29, 2021, 07:32 AM)

After looking through the source code for a few minutes, it appears to be generating the solution using an idea that occurred to me as a possibility sometime in the past couple of days.

It starts with a single, pre-generated solution, then applies random transformations to it fifteen times, which basically shuffles it in ways that maintain the legality of number placement. (In my own code, I was generating a random solution, then transforming it 100 times. This usually only took tens of milliseconds at most, but sometimes generating a random solution took hundreds of milliseconds. Meanwhile, transforming is always super quick to do, taking only up to a few milliseconds at most, but often finishing under 1ms.) So they skipped the slowest part of solution generation by starting with a solved puzzle and just transforming it.

Then, to create a puzzle out of the solution, it randomly removes a certain number of digits based on the difficulty level. That is to say:

• Trivial removes 22 digits, resulting in 59 givens.
• Easy removes 32 digits, resulting in 49 givens.
• Medium removes 42 digits, resulting in 39 givens.
• Hard removes 52 digits, resulting in 29 givens.
• Ultra removes 58 digits, resulting in 23 givens.

Like the python code wraith808 linked to, the result is obviously not necessarily a minimal puzzle. And in fact, all but Hard and Ultra difficulty result in puzzles that have so many givens that professional Sudoku puzzle creators would throw them out.

I also insist that the average number of clues hangs around 27 and is never more than 30. Nikoli, the inventor of the modern version of Sudoku states as part of his definition that the number of clues should not exceed 32.

[...]

Over a large run I get a set of puzzles where the number of clues is a bell-curve centered on 27.

-https://www.sudokuwiki.org/Sudoku_Creation_and_Grading.pdf

But in the case of Ultra difficulty, which results in a puzzle with only 23 givens, it may be good enough considering the speed at which it does it. Many of the puzzles I've been generating the slow way have up to a few more givens than that.

So maybe I just need to drop the self-imposed requirement of having a minimal puzzle, since it seems there do exist other methods of generating a puzzle that is good enough in a much faster time.

389

Developer's Corner / Re: Constructing a minimal Sudoku puzzle

« on: July 29, 2021, 03:30 AM »

And speaking again of code duplication, I've converted the code from https://www.101compu...generator-algorithm/ into GDScript. It contains two, ~70-line functions which are virtually identical, with only something like 3 lines different between them.

It works, but it still takes about 3 seconds on average to generate a puzzle. And they tend to be easier puzzles (with more givens) because it just tries to get rid of one number at a time until it finds multiple solutions, does that a few times, then stops attempting even if there are other numbers that could be removed while maintaining a unique solution.

So then I modified their "digging" function to try every square in a randomized order, and it takes significantly longer to generate a puzzle, with only a few fewer givens.

I benchmarked the difference between "Hey, I tried a bit, what do you expect of me?" and "I must attempt to remove every single number I can!" by generating 10 puzzles of each, and the difference is staggering. As stated, the "lazy" way took about 3 seconds on average to generate a puzzle, 0.1 seconds for the fastest and 12 seconds for the slowest. But the "stickler" way took about 12 minutes on average, 26 seconds for the fastest one and and a whopping 18 minutes for the slowest one.

I'm starting to think that most Sudoku software doesn't actually generate minimal puzzles on the fly every time you start a new puzzle, because I'm having a hard time imagining being able to do so reliably in 0.1 seconds or less.

Either that or I need to get closer to the metal with C++ or something. 😬

390

Developer's Corner / Re: Constructing a minimal Sudoku puzzle

« on: July 28, 2021, 04:09 PM »

You know the famous Knuth programming quote: "premature optimization is the root of all evil" (which I don't agree with -- I think code duplication gets that spot).

-mouser (July 28, 2021, 01:49 PM)

Well, speaking of code duplication, I think that brings up another adage that applies very well to this situation: "Don't try to reinvent the wheel."

I kind of wanted to understand how to generate a Sudoku puzzle, so I could use that knowledge to accomplish something else that was related to doing so. But I realize now--after banging my head against the wall for several days trying to solve something that has already been solved by people who are much smarter than I am--that "the how" of doing it is ancillary to the actual goal of making a Sudoku game in a game engine. So I think I'm going to revisit some of the references I found during my research on "the how" which also included example code in the explanations, such as Peter Norvig's article on Solving Every Sudoku Puzzle and just copy/convert it line for line until I get something that works. (And of course, I'm definitely going to be using the link from wraith808 as a jumping off point as well, so thanks for that.)

Thanks for taking the time to give detailed and helpful replies. Now I have some direction and hope that there's light at the end of the tunnel.

391

Developer's Corner / Re: Constructing a minimal Sudoku puzzle

« on: July 28, 2021, 02:09 PM »

After it all works then worry about speeding it up.

-mouser (July 28, 2021, 01:49 PM)

That's where I am (I think).

I had it working (I think). But it was too slow to be useable in a real-time game. So now I'm trying to speed it up. And breaking it in the process.

And that's also why some of the code doesn't make much sense. Originally, I was counting solutions. The solve() function was flexible and could be used to find just one solution, two solutions (quitting after it realized the puzzle wasn't unique), or all solutions. Then I realized I didn't really care about finding all solutions. And then I realized I could tweak my other code so that it only needed to find a single solution to know whether or not it was unique. So the solution count stayed in there even though it didn't need to count anymore. Oops! My bad.

But looking at the code, i see what MIGHT be a problem.

Your last lines of solve say "       

[Select]

# if we got this far then we've solved it!        solutions += 1         return solutions

"

But let's look how we can get down there.
One way is if there are no more holes -- that's what we want.  When there are no holes, return TRUE, we found a solution.
But also i think you can get there if your PRELIMINARY sorting operations identifying possibilities creates a situation where some illegal spot has no good options.  this should NOT be returning a true case(!)

-mouser (July 28, 2021, 01:45 PM)

I think you're onto something. I was writing up a response about how I didn't see how that was possible, but in the process of explaining my viewpoint there was a momentary flash of neurons connecting in such a way as to realize that you may be right. But then those neurons went on break or something, because I don't think I fully comprehend it yet. So I'm not fully convinced that you're right (or in what way you're right). But now my confidence that my initial viewpoint was right is very low.

392

Developer's Corner / Re: Constructing a minimal Sudoku puzzle

« on: July 28, 2021, 01:40 PM »

"Unit: Any nine squares that compose a row, column, or box. Each square has exactly 3 units." <-- do you mean each square is a MEMBER of exactly 3 units.

-mouser (July 28, 2021, 11:23 AM)

Yes, that's a better way of phrasing it. I'll edit the post to reflect that.

As I understand the basic gist of the algorithm is that you incrementally blank out squares, and check to make sure (by running a solver) that there is still only a unique solution to the puzzle with the square blanked out.  If there are multiple solutions with that square blanked out, you must force it to be a given, and try looking for another square to blank out (dig a hole).

So, this algorithm guarantees that the puzzle, with its givens and its holes (blanks) is UNIQUELY SOLVABLE.

But it doesn't really guarantee that the puzzle is MINIMAL.  I don't think it claims to, does it?

It's not doing a brute force search for all POSSIBLE ways to dig holes.. It is in fact going through an ORDERED list of possible squares to dig, checking them one at a time, and when it finds one it can dig (leave blank), it makes it blank going forward.

This does not guarantee a minimal set of givens.  Depending on what holes (blanks) you decide on early, you may be forced into having more or less holes in the rest of the puzzle.

You could use it to find minimal puzzles if you ran it once for every possible sequence of potential holes, and kept the one that resulted in the fewest givens.

---

Does that make sense? Or am I missing something?

I just think it's important to understand that the algorithm doesn't seem to be promising to generate minimal puzzles.

-mouser (July 28, 2021, 12:00 PM)

I was operating under the idea that, of all the number of clues given at the start of the puzzle, if removing any one of them results in multiple solutions, then that puzzle is a minimal puzzle. But you make a convincing case that there is a distinction between a truly minimal puzzle and the conception I had of it, and there could possibly be (and almost certainly is) a different arrangement/number of givens that would result in the same unique solution using the digging holes method.

And now that I realize this, I'm interested in what it would take to attain your definition of a truly minimal puzzle. But at the same time, I think the definition I've been using until now is good enough for my purposes with this project.

For reference, I got the idea of a minimal puzzle from a paper by Andrew C. Stuart (PDF link), and there may have been something lost in my paraphrasing of his definition:

The fifth criterion is that the puzzle should be minimal. That is all the numbers have been removed so that the bare minimum of clues remain make a single solution puzzle. Interestingly mathematicians have worked out that 39 numbers is the most number of clues that a minimal puzzle can have.

[...]

Given a filled board I then start subtracting numbers to make the puzzle. To maintain symmetry either two or four numbers that are diagonally opposite each other must be removed at the same time. For the first twenty or so subtractions four numbers can be removed. Beyond that the chance of four numbers leaving a single solution puzzle get slimmer so two at a time are subtracted. A low target of 20 clues is set and by 30 the remaining numbers are tested individually to see if they can be removed safely. After each subtraction the puzzle is tested to see if it retains a single solution. If this fails the numbers are restored and a different quad, pair or single subtraction is tried.

-https://www.sudokuwiki.org/Sudoku_Creation_and_Grading.pdf

So that's the "original" source of the term "minimal puzzle" that I'm aware of. And it doesn't seem to contradict my interpretation of it.

Maybe im missing something since it seems like it would break everything if it was missing, or maybe you didn't show all the code, but in find_givens() function, line 21 starts a loop checking if there are solutions with the alternative digits.

In the loop you force the test value, and check if there is a solution..
And at the end of the loop if you DID find other solutions, you force the value back and then set it as a given square.

BUT what you dont do is at the end of that if you DONT find any solutions, is FORCE that value to a hole (value 0).. so in the code you show above it will be left as bad value (the last value you checked in the loop), rather than marked as a hole.
Did you just forget to show that code or am i missing something?

-mouser (July 28, 2021, 12:12 PM)

You're right. You're missing something that I failed to mention.

For the sake of simplicity, I lied a little in my description of the problem, because I failed to understand the ramifications of the differences I swept under the rug. I'm not actually using a true array to store the squares. I'm using a special array type in GDScript called a PoolIntArray, which is optimized for memory usage and is passed by value instead of reference. I thought both of these characteristics were important for improving the speed of the algorithm, but didn't really see it worth mentioning this special type. (I've updated the original post to include this detail)

But because it's passed by value instead of reference, there's no need to backtrack the changes because the PoolIntArray from the level above is unchanged. What that means is that I actually don't even need to force the value back to its original value when a solution is found. I just need to mark it as given in the "given" array (which is a true array).

Forcing it back to its original value is an artifact in the code from when I originally wrote the functions using a two-dimensional array to store the grid. I thought it was so slow because not only did I have to duplicate the array each time I tried to solve it recursively, I had to do a deep copy to ensure the nested arrays didn't get set to bad values. So when I went to change the code to use a normal array I found the PoolIntArray and thought that it was killing two birds with one stone: No more deep copying, and memory usage optimization! I managed to remove the code to re-dig the hole when no solution was found, but accidentally left in the code that re-sets the square to the original value when a solution is found.

Here is one in Python that does the same thing you're trying to do (I think)

https://www.101compu...generator-algorithm/

Not sure if that helps...

-wraith808 (July 28, 2021, 01:05 PM)

Thanks. I'll take a look at that.

393

Developer's Corner / Constructing a minimal Sudoku puzzle

« on: July 28, 2021, 10:35 AM »

Hi all,

I've been working on programming a Sudoku game and I've run into a problem with my code that I've been unable to solve for the past few days and realize I need some fresh eyes on the problem. This may not be the best place to ask about this, but as best as I can tell this problem requires a bit of an in-depth explanation and I don't really feel comfortable asking on other sites that may be more closely aligned with the specific area of inquiry, but where I have not really established myself as part of the community. And maybe it could be asked more succinctly, but unfortunately for anyone who reads this, I tend to be overly verbose in an effort to make sure I'm explaining myself clearly. So here goes.

First of all, I assume the reader is familiar with Sudoku puzzles and understands the basic rules. But I figure I should establish some Sudoku terminology (mostly from Peter Norvig), so we're all speaking the same language here.

Square: A place where a number goes. A Sudoku puzzle is made up of 81 squares arranged in a 9x9 grid.
Row: Nine squares arranged horizontally (9x1), in which the numbers 1 through 9 can only appear once.
Column: Nine squares arranged vertically (1x9), in which the numbers 1 through 9 can only appear once.
Box: Nine squares arranged in a 3x3 grid, in which the numbers 1 through 9 can only appear once.
Unit: Any nine squares that compose a row, column, or box. Each square is a member of exactly 3 units.
Peers: Any squares that share a unit are considered peers. Each square has exactly 20 peers.
Given: The "freebie" clues that are known at the start of the puzzle.
Minimal Puzzle: A Sudoku puzzle that has the fewest amount of givens possible, while still only having one unique solution.

And here's a crude diagram showing a minimal puzzle with some of the above terminology highlighted:



So what I'm trying to accomplish is making a game that can generate an infinite number of Sudoku puzzles (well, as many of the 6,670,903,752,021,072,936,960 possible puzzles as a player might want/be able to play). It turns out that generating solutions is easy. You can sort of just make it up as you go along. The part I'm having trouble with is going from the solution to the minimal puzzle.

In other words, in order to present the player with a puzzle to solve, I want to go from something like what's on the left to something like what's on the right:

Code: Text [Select]

1. 1 2 7 | 4 5 8 | 3 6 9     . . . | . . . | . 6 .
2. 5 3 9 | 6 7 2 | 1 8 4     . 3 . | . . 2 | . . .
3. 6 4 8 | 9 3 1 | 7 2 5     . . . | . 3 . | . . .
4. ------+-------+------     ------+-------+------
5. 3 1 5 | 7 8 6 | 4 9 2     . . . | 7 . 6 | . . .
6. 4 8 2 | 3 1 9 | 6 5 7     . 8 2 | . 1 . | . . .
7. 9 7 6 | 2 4 5 | 8 3 1     9 . 6 | . 4 . | . . .
8. ------+-------+------     ------+-------+------
9. 8 9 4 | 5 6 7 | 2 1 3     8 9 4 | 5 . 7 | . . 3
10. 2 6 3 | 1 9 4 | 5 7 8     . . . | 1 . . | 5 7 8
11. 7 5 1 | 8 2 3 | 9 4 6     . 5 . | . . . | . . .

I've written code that accomplishes it. In fact, the above puzzle was generated by my code. But it's far too slow, and unpredictably so, to be useful in a real-time game. Sometimes it only takes a couple of seconds to generate a puzzle, which in itself is too slow. But other times it takes up to a few minutes. And in a few cases it has taken so long that I've been too impatient to let it finish. I'm coding this in GDScript, which is a custom language created for Godot, but which is very similar to Python.

I'm storing the solution of the 9x9 grid in a special kind of one-dimensional array in GDScript called a PoolIntArray, which is passed by value instead of reference. It would look like this as a traditional array:

Code: Python [Select]

1. var answer := [
2.         1, 2, 7, 4, 5, 8, 3, 6, 9,
3.         5, 3, 9, 6, 7, 2, 1, 8, 4,
4.         6, 4, 8, 9, 3, 1, 7, 2, 5,
5.         3, 1, 5, 7, 8, 6, 4, 9, 2,
6.         4, 8, 2, 3, 1, 9, 6, 5, 7,
7.         9, 7, 6, 2, 4, 5, 8, 3, 1,
8.         8, 9, 4, 5, 6, 7, 2, 1, 3,
9.         2, 6, 3, 1, 9, 4, 5, 7, 8,
10.         7, 5, 1, 8, 2, 3, 9, 4, 6,
11. ]

I also have a similar array of booleans, called "givens" which indicates if a particular square is a given or not.

I then follow a method I read about in a paper called Sudoku Puzzles Generating: from Easy to Evil (link to archive, since original link is dead) which the authors refer to as "digging holes" in the puzzle, and offer this flowchart as part of their explanation:



I'll summarize my understanding and (attempted) implementation as follows:

• Order a list of all the squares to "dig" however you see fit. (I just shuffle an array of all the squares)
• For each square in the list, attempt to dig the known value N. This means to set the value as "unknown" or "empty" (represented internally by the number 0).
• With the newly dug square, attempt to solve the puzzle with all possible values (1-9) other than N.
• If you find a solution, it means the puzzle is no longer unique (it has multiple solutions), so the square is considered a given and must display the value N to maintain uniqueness.
• If you don't find a solution, the square can remain "dug" and you continue iterating the list to dig more holes.
• Once you've iterated the entire list, you should have dug out all squares that are not essential to maintaining the uniqueness of the puzzle, which results in a minimal puzzle.

Here's the code which I think does what I described above:

Code: Python [Select]

1. # digs a solved grid to find a minimal puzzle
2. func find_givens() -> void:
3.         # make a list of all 81 indices of the grid
4.         var dig_list := []
5.         for idx in 81:
6.                 dig_list.push_back(idx) # push_back() just adds elements to the end of an array
7.         # randomize the order of squares we "dig"
8.         dig_list.shuffle()
9.         # prepare some variables we'll be using repeatedly
10.         var nums = answer # grab a copy of the answer so we don't make changes to it
11.         var v : int # temporarily stores the "dug" value in case we need to replace it
12.         var coords := Vector2() # x,y coordinates
13.         # iterate the randomized list
14.         for i in dig_list:
15.                 # don't attempt to dig a square that is known to be a given
16.                 if given[i] == true:
17.                         # sanity check: this code should never actually be reached
18.                         continue
19.                 # store the current value of the digit
20.                 v = nums[i]
21.                 for n in range(1, 10): # iterate the numbers 1-9
22.                         # skip if this is the square's original value
23.                         if n == v:
24.                                 continue
25.                         # dig the value and try finding other solutions
26.                         nums[i] = 0
27.                         # get the (x, y) coords for this square
28.                         coords = index_to_coord(i) # convert the index (0-80) to x,y coordinates as if on a 9x9 grid
29.                         # change the value at this square to something else, if possible
30.                         if is_possible(nums, coords.y, coords.x, n):
31.                                 # N could legally be placed in this square
32.                                 nums[i] = n
33.                                 # try to find a solution to the puzzle with this new value in this square
34.                                 if solve(nums) > 0:
35.                                         # we found a solutions, which means the puzzle is no longer unique
36.                                         # so put the value back
37.                                         nums[i] = v
38.                                         # mark this square as a given
39.                                         given[i] = true
40.                                         # don't attempt further numbers for this square
41.                                         break

And here's the code for the if_possible() function, which is used to determine if a value n could legally be placed in the square located at (x,y) in a 9x9 grid. Or in other words, it makes sure that no other peer of the square (x,y) has the value n:

Code: Python [Select]

1. # returns true if no peers have the value n
2. func is_possible(grid, y : int, x : int, n : int) -> bool:
3.         for i in 9:
4.                 # check if n already exists in current row (9x1)
5.                 if grid[coord_to_index(y, i)] == n:
6.                         return false
7.                 # check if n already exists in current column (1x9)
8.                 if grid[coord_to_index(i, x)] == n:
9.                         return false
10.         # integer math here means (5 / 3) * 3 is the same as 1 * 3
11.         var x0 : int = (x / 3) * 3
12.         var y0 : int = (y / 3) * 3
13.         # check if n already exists in current box (3x3)
14.         for i in 3:
15.                 for j in 3:
16.                         if grid[coord_to_index(y0 + i, x0 + j)] == n:
17.                                 return false
18.         # as far as we know, n is a legal value for this square
19.         return true

And finally, the code used to attempt to find a solution to the puzzle. I think this is where my trouble lies. This function basically just brute-forces the grid, attempting every possible value in every unknown square, looking for a solution, with backtracking when it reaches a dead-end. Initially I had it naively starting at element 0 of the array and looping through them in order, but this is obviously very inefficient and leads to a lot of duplicated efforts due to backtracking. It seemed to work, and generated minimal puzzles which usually had about 24-26 givens. But as mentioned previously, it was pretty slow.

So then I attempted to sort the list of squares to solve by the number of possible values that were legal to place there, starting with those which had the least possible solutions. This increases chances of success, but even in the event of a failure (dead-end) it cuts out a huge number of the possible solutions we'd have to check.

Oh, and since it's recursive, I have it keep track of and return how many solutions it has found so that it can immediately jump all the way back down the stack once a solution has been found.

Code: Python [Select]

1. func solve(grid, solutions := 0) -> int:
2.         # this is a dictionary whose key will be the (x,y) coordinate
3.         # and the value will be the number of possibilities for that coordinate
4.         var possibilities = {}
5.         # loop through every element in the grid
6.         for i in grid.size():
7.                 # get the (x,y) coordinates for this index
8.                 var coord = index_to_coord(i)
9.                 # start with the assumption that each square has 0 possibilities (i.e., the square's value is known)
10.                 possibilities[coord] = 0
11.                 # if it's not zero, then it's considered "solved" already
12.                 if not grid[i] == 0:
13.                         continue
14.                 # check how many values are possible here
15.                 for n in range(1, 10): # iterate the numbers 1-9
16.                         if is_possible(grid, coord.y, coord.x, n):
17.                                 possibilities[coord] += 1
18.         # sorted_list is an array whose elements will contain the index of the squares grid,
19.         # sorted by the number of possibilities
20.         var sorted_list := []
21.         for n in range(1, 10): # iterate the numbers 1-9
22.                 # loop through each element in possibilities
23.                 for coord in possibilities.keys(): # remember that each key is an (x,y) coordinate
24.                         if possibilities[coord] == n:
25.                                 # add this square to the sorted list of squares to solve
26.                                 sorted_list.push_back(coord_to_index(coord.y, coord.x))
27.         # now iterate through the sorted list and try solving
28.         for i in sorted_list:
29.                 var coord = index_to_coord(i)
30.                 if grid[i] == 0:
31.                         for n in range(1, 10): # iterate the numbers 1-9
32.                                 if is_possible(grid, coord.y, coord.x, n):
33.                                         grid[i] = n
34.                                         solutions += solve(grid, solutions)
35.                                         if solutions > 0:
36.                                                 return solutions
37.                                         else:
38.                                                 grid[i] = 0
39.                         # none were possible, we've reached a dead end
40.                         return solutions
41.         # if we got this far then we've solved it!
42.         solutions += 1
43.         return solutions

And again, this seems to work... kind of. I mean, it is (usually) noticeably faster than when I was naively brute-forcing without sorting. But (1) it's still too slow, taking at least a couple of seconds to complete, and (2) the "minimal" puzzles its generating can't actually be minimal. Doing it the naïve way, I was getting minimal puzzles with about 24-26 givens on average, the puzzles this is generating consistently have almost twice as many, usually in the 44-46 range. But it has been proven that the least amount of givens a unique puzzle could have is as low as 17 and the highest amount of givens a minimal unique puzzle can have is 39. So something is definitely wrong. Here's an example:

Code: Text [Select]

1. . . . | . 5 9 | . 3 4
2. 2 1 . | . . 6 | . 5 7
3. 9 . . | 3 . 7 | . 6 .
4. ------+-------+------
5. . 9 . | . . 3 | 8 4 2
6. 5 . 8 | 7 . 2 | 3 . 9
7. . . 2 | 1 9 . | . . .
8. ------+-------+------
9. . 2 . | 8 7 1 | 4 . .
10. 1 . 7 | 9 . . | 5 . 6
11. . 3 9 | 6 2 . | 7 8 .

Oh, and for completeness, here is the code for a couple of helper functions that are used in a few places in the code above:

Code: Python [Select]

1. # returns an index for an 81-element array based on x,y coordinates of a 9x9 grid
2. func coord_to_index(y : int, x : int) -> int:
3.         return (y * 9) + x
4.  
5.  
6. # returns the x,y coordinates of a square on a 9x9 grid based on 81-element array index
7. func index_to_coord(i : int) -> Vector2:
8.         var coord := Vector2()
9.         coord.x = i % 9
10.         # integer division
11.         coord.y = i / 9
12.         return coord

I tried adding tons of comments everywhere to make sure it was clear what the code was (supposed to be) doing. If anyone here takes the time to read this, parse/understand the code, and offer helpful suggestions/solutions, I'd appreciate it. Mostly I think I just needed a break from the coding and thought that maybe the process of writing this all out would be a form of Rubber Duck debugging.

I know I'm doing something wrong because I'm not getting minimal puzzles anymore. So help figuring out why that's happening would be much appreciated. But perhaps a more helpful response would explain what else I'm doing wrong that is making this so slow. My understanding is that most minimal puzzles should be solved/generated in milliseconds at most, and that it should be fairly rare to come across a puzzle that takes a few seconds and even rarer to come across one that takes minutes or longer. I've tried benchmarking my code by generating 100 puzzles and averaging the time it takes to do each step, and I can't even do that because while it "only" takes a few seconds at best for each puzzle, it often takes up to a few minutes. But the clincher is that in every attempt at generating 100 puzzles in a row there's (at least) one that takes so long that I've never had the patience to find out exactly how long it would take to complete. I can't remember for sure, but I think I've left it running on a single puzzle for over an hour before aborting the process and trying to adjust the code to speed it up.

What am I doing wrong? And where? Please don't say "everything/everywhere"

394

DC Website Help and Extras / Re: A public thank you to Deozaan and other mods keeping the board spam free

« on: July 27, 2021, 02:05 PM »

What is this "sleep" you speak of?

395

DC Website Help and Extras / Re: A public thank you to Deozaan and other mods keeping the board spam free

« on: July 27, 2021, 09:42 AM »

Thanks for noticing.

396

Living Room / Re: I bought an Oculus Quest and I'm blown away by the current state of VR

« on: July 24, 2021, 12:10 PM »

I guess I should also clarify that it will (usually) remember your Guardian from session to session. So if you've already set it up once, then all you have to do thereafter is strap the device to your face.

I'm not sure if mine keeps forgetting just because it intentionally doesn't always remember it (such as after a reboot), or if it "forgets" when it detects I've moved too far away from my Guardian, since I keep moving it back and forth from my (home) office to my living room.

One thing that amazed me was how accurately it can track its own position. When I initially set it up and played with it for a while, I was in my living room. I don't remember how charged it was when it arrived, but after I pulled it out of the box I played for about 2 hours before it started warning me that the battery was going to die soon. So I turned it off and took it to my office to charge up. Later, after it was charged, I put it on my head at my computer desk and it told me I needed to return to my Guardian zone. So I got up from my desk and began to walk around it so I could exit the office and go to the living room. As part of the process of walking around my desk, I happened to face where my living room was (on the other side of a wall), and the Quest 2 showed an outline on the floor through the wall of where my Guardian zone was location. How did it know where it was in relation to the living room? I turned it off while in the living room, moved it to the office and charged it before turning it back on in the office. It felt like having x-ray vision! Or like in sci-fi movies where robots/cyborgs have blueprint schematics and other similar things overlaid on top of their "regular" vision. I don't think the Quest 2 was intended to be used for AR, but that's basically what this was.

It's really cool (and kind of scary!) to think of what could be possible in a couple/few decades as the technology improves and continues to miniaturize.

Later I also discovered that you can mark the size and position of a real-world couch and desk and it will show them in VR to make it easier to sit down or place your controllers down with the headset on. So I did that. And now when I'm playing in the living room, I can see where my desk in my office is through the walls. And when I'm at my desk, I can turn my head toward the living room and see the Guardian boundary as well as my couch through the walls.

397

Living Room / Re: I bought an Oculus Quest and I'm blown away by the current state of VR

« on: July 24, 2021, 10:45 AM »

The one thing with the PS4 one is that I'm really the only one that can set it up. Looking at this, it seems a lot simpler.

-wraith808 (July 24, 2021, 10:31 AM)

I don't know what it takes to set up the PS4 one, but this is pretty easy. You basically just strap it on your face and then trace the open space on your floor to set up your "Guardian boundary" and you can move about freely in VR. Or if you want to be sitting or otherwise stationary, you can do that, too.

How did you guys get around the Facebook requirement? Or did you just decide not to care?

-wraith808 (July 24, 2021, 10:31 AM)

I created a new Facebook account and used that.

If you decide to get one, let mouser or I know before you set it up. We can get you a referral code that will give you and whoever refers you $30 to spend on the Oculus store when you activate your headset.

398

Living Room / Re: I bought an Oculus Quest and I'm blown away by the current state of VR

« on: July 23, 2021, 04:27 PM »

Thanks to mouser's gentle and not-so-gentle () encouragement via PM, I also have an Oculus Quest 2 now.

I'm still in the adjustment period, where sometimes I feel a little "off" after using it. It's like a very slight form of motion sickness, and it only happens after I take the headset off, rather than while I'm in the virtual space. But I agree that it's very impressive and quite entertaining.

And of course, I'm also planning to see if I can develop anything for it using Godot or Unity.

399

General Software Discussion / Re: Windows 10 Announced

« on: July 21, 2021, 10:55 AM »

It's the same as taxis and hiring a car for holidays can be better value than buying a car and being responsible for maintaining it. Advantages and disadvantages according to your needs.

-Dormouse (July 20, 2021, 05:41 PM)

Or perhaps this perspective more closely matches wraith's use-case:

I own a car. It's not in the greatest condition, but reliable enough for my daily needs. I'm not willing to pay what it would cost to buy a new (or only a couple years old) vehicle. But when I take a multi-day trip out of town, I rent a car. I get the benefits of a much newer vehicle which is in much better condition than mine, so I'm not concerned about it breaking down during the trip. And I also don't put those miles on my own car, which will help it last just that much longer before I have to replace it.

400

General Software Discussion / Re: Active Directory | User keeps getting locked out

« on: July 20, 2021, 01:29 PM »

This thread was started by a spammer who later edited their post to add spam links to it. The spam has been removed. But instead of just deleting the entire thread and the helpful replies along with it, I'm locking the thread.