17 replies to this topic

[IceMetalPunk]

What do you do when you forget to take your personal computer--the only place you save your projects--with you on vacation? You use another computer to make random, small projects like a Sudoku solver!

For those who don't know, Sudoku is a number puzzle consisting of a 9x9 grid divided into 9 3x3 squares. The puzzle starts out with numbers filled in some cells, and the goal is to fill in all the remaining cells such that every row, every column, and every 3x3 grid contains exactly one copy of each digit from 1 to 9.

My little app will let you manually enter in the values of the cells you know, and as each cell is entered it will fill in any other cells it can figure out.

For example:



The gray cells were entered in from the start, the black ones were solved by the app.

But the real beauty in this app is that it works beyond manual entry. There are many websites online that let you play Sudoku puzzles on your computer. While there exist several main formats for these, the most common puzzle sites use a similar UI control scheme. And that means this app can automatically load, analyze, solve, and fill-in any of these puzzles with minimal intervention on your part.

Download

The instructions come up in the game, but here's the summary:

1) You can manually enter numbers wherever the cursor is, and move the cursor with the arrow keys or by left-clicking an empty cell.

2) To auto-solve an online puzzle, the following conditions must be met:
a) The puzzle must be a standard 9x9 puzzle; no other sizes will work.
Pressing TAB in the puzzle must move the cursor to the next cell to the right, wrapping to the next row when it reaches the end.
c) Pressing SHIFT+TAB should do the opposite, moving the cursor backwards.
d) Pressing CTRL+A should select the current cell in the puzzle.

If those are satisfied (there's a list of tested compatible sites in the F1 info), then you can simply move the cursor to the first cell in your puzzle and press CTRL+ALT+S and the app will get to work loading your puzzle, then filling in any values it could solve.

3) If you auto-load a difficult puzzle, the app may not be able to solve every cell. In that case, you can manually fill in missing values if you know them, and once the puzzle is complete, you can go back to the online puzzle's first cell and press CTRL+ALT+F to fill in the updated values.

Download

I've screencaptured videos of it being used on multiple websites, but until I get back to my personal computer tomorrow, I can't edit them together. So hold on for a day if you want to see it in action .

-IMP

*EDIT*

Video demo!



This is a demo showing it being used to solve puzzles from several sites and to auto-fill the cells in. I had to speed up the video (or it would have been over 10 minutes, since it takes about 40 seconds per puzzle), so it looks like it skips some cells--but it doesn't. It analyzes every cell and fills in every cell.

Note: the video was recorded before I changed the window size to fit the Sudoku board.

Music by Charlie Shaw via TimEGardner's video: Original Song Video Here

Edited by IceMetalPunk, 27 November 2011 - 11:40 PM.

[Nial8r]

This is AMAZING O_O
Major props to you on this one!

[AhmedElyamani]

That's a very good one , but like this Sudoku will be usless

[IceMetalPunk]

@Nial8r: Thanks .

@ahmed # elyamani: Yeah, well...when those pesky puzzles get annoying, this can help .

-IMP

[LaLaLa]

What do you use the "Windowz.dll" for? Wouldn't it just be easier to use the GM window and create a few scripts to implement the text boxes?

Also, any chance of releasing the source for this?

[IceMetalPunk]

What do you use the "Windowz.dll" for? Wouldn't it just be easier to use the GM window and create a few scripts to implement the text boxes?

Also, any chance of releasing the source for this?

I use the Windowz DLL just to check to see what the active window is. This way it can abort the analysis/filling script if the focus changes from the website, since the script simulates keypresses (without this, if you switched windows while it was analyzing/filling a puzzle, the keypresses would seriously mess things up with your computer).

And the Manual Entry method lets you input the data directly if you want, but it's just faster to have GM quickly tab through a puzzle and input all the values than for you to manually do it. If you prefer manual entry, go ahead and stick with that .

I may release the source soon. This was just a small project anyway to fill my time when I didn't have access to my own laptop. However, I've been working on getting the program to generate Sudoku puzzles on its own (you can see that I have a topic about this in the Advanced forum), so if I ever get around to getting that working, I'd want it done before I release the source.

The method is quite simple, though:

1) Each square has a list of possible values, which starts out filled with the numbers 1 through 9.

2) When a number is entered, all values from that square's list, besides the entered value, are removed. Likewise, all squares in the same row, column, or box as that square have the given value removed from their own lists.

3) Also, if a number appears on the list of only one square in a given row, column, or box, that must be the correct value for that square, so #2 is called using that number as the remaining value.

4) Whenever any square only has 1 value left on its list, steps 2-3 are recursively called beginning with that square.

5) If at any time a square has an empty list, the puzzle is impossible and that square is displayed as a red X.

There are other, more advanced situations to check for that would be able to solve harder puzzles, but when I researched them I couldn't understand their theory enough to implement them . But as you can see, even without those the program works pretty well.

-IMP

Edited by IceMetalPunk, 03 December 2011 - 12:21 AM.

[HelpMyFellowPeople]

This guy... This guy is a genius!

[Big J]

When I run it, I just get a blank black window. When I right click, messages pop up, but Game Maker's engine never draws anything.

That Windowz DLL must be doing something strange.

Edited by Big J, 13 December 2011 - 02:29 PM.

[IceMetalPunk]

When I run it, I just get a blank black window. When I right click, messages pop up, but Game Maker's engine never draws anything. :sad:

That Windowz DLL must be doing something strange.

That's very odd... the Windowz DLL is one I made such a long time ago that I no longer have its source, but all I use it for here is, as I said, to detect when an auto-fill window has lost focus to prevent keys from being pressed in other windows (thus causing problems). Perhaps the initialization is an issue for you for some reason?

One thing that I vaguely remember is having problems with non-composite Windows themes...are you using Aero? If not, try temporarily switching your Windows theme to Windows Aero and running this. If it works then, it is indeed the DLL, and I can re-write a new DLL that doesn't have that initialization, since I don't need it here anyway.

-IMP

[Big J]

I am on Windows XP, I don't think I have that theme. I just have Windows XP theme and Windows Classic theme. I am using the Windows XP Silver theme.

Here's a screenshot:

I can't see anything. The window title is missing as well.

Edited by Big J, 13 December 2011 - 11:32 PM.

[IceMetalPunk]

Actually, there is no title . But yeah, I think the problem is that XP doesn't have any composite themes. I'll work on creating a simplified DLL to fix that bug.

-IMP

*EDIT* OK, redownload from the same link. I've replaced the Windowz DLL with a simpler DLL with only the one function I needed. Hopefully that fixes your problem.

Edited by IceMetalPunk, 14 December 2011 - 02:41 AM.

[Big J]

No, in the first post the window title is clearly "Sudoku Solver". Well, the room caption anyway.

[IceMetalPunk]

No, in the first post the window title is clearly "Sudoku Solver". Well, the room caption anyway. :tongue:

Heh, nevermind. Ignore what I said about the title; I'd forgotten . Does the new version with the simplified DLL work for you?

-IMP

[Big J]

Sort of... I got "error defining an external function", but I closed FRAPS and that fixed it. I encountered the same issue with Ultracrypt.dll, so that's why I knew to try that.

Yeah I can see everything now, thanks.

Edited by Big J, 14 December 2011 - 03:13 AM.

[LaLaLa]

Okay, perhaps I'm missing something obvious here, but can this program actually attempt to solve a puzzle? The first time I opened the ZIP file it wouldn't run because I didn't bother extracting the DLL too, so I just closed it. Later, however, I finished my program, so I went back and ran yours. It appears to only solve cells if there is only one possiblility remaining for them based on the basic rules for Sudoku. This isn't very helpful, as there are many more puzzles that can be solved using guess-and-check, even those with only one solution that yours odesn't find.

Take, for example, a very difficult puzzle on this Wikipedia page (18-clue double symmetric). My program found the one and only solution after about 5 minutes, but yours doesn't fill it out on its own. What's up with that?

I uploaded an executable of mine here.

Edited by LaLaLa, 25 December 2011 - 05:50 PM.

[rogonow]

I thought much about how a basic sudoku solver would be made in GM. Thx for sharing the info. A sudoku puzzle is like 9*3 simultaneous equations.

[IceMetalPunk]

Okay, perhaps I'm missing something obvious here, but can this program actually attempt to solve a puzzle? The first time I opened the ZIP file it wouldn't run because I didn't bother extracting the DLL too, so I just closed it. Later, however, I finished my program, so I went back and ran yours. It appears to only solve cells if there is only one possiblility remaining for them based on the basic rules for Sudoku. This isn't very helpful, as there are many more puzzles that can be solved using guess-and-check, even those with only one solution that yours odesn't find.

Take, for example, a very difficult puzzle on this Wikipedia page (18-clue double symmetric). My program found the one and only solution after about 5 minutes, but yours doesn't fill it out on its own. What's up with that?

I uploaded an executable of mine here.

The algorithm I used I came up with from scratch. It's not perfect, and it doesn't guess-and-check, but it definitely does solve many, many puzzles. Just not the hardest ones, but some difficult ones can be solved with this. If you go to any of the websites listed in the F1 Help screen, the program will solve all of the Easy-level puzzles, most of the Medium and Hard, and some of the Hardest/Wicked/Whatever-the-heardst-level-is-called puzzles.

-IMP

Edited by IceMetalPunk, 22 January 2012 - 10:37 PM.

[Anzkji]

That's wrong...