| |
I'm bored |
| |
This is a long thread. Click here to view the threaded list. |
| |
|
Jeffrey Lee |
Message #66094, posted by Phlamethrower at 15:09, 31/5/2005, in reply to message #66093 |
 Hot Hot Hot Hot Hot Hot Hot Hot Hot Hot Hot Hot Hot stuff
Posts: 15100
|
Why not try my (easiest ever) Sodoku?
1?|4?
?2|??
-----
??|1?
??|?? Because I don't know what Sodoku is?  |
| |
 [ Log in to reply ] |
| |
|
Tony Haines |
Message #66096, posted by Loris at 15:24, 31/5/2005, in reply to message #66094 |
 Ha ha, me mine, mwahahahaha
Posts: 1025
|
No not rat bite fever. Its a typo of Sudoku, does that help?
No? how about this then? |
| |
[ Log in to reply ] |
| |
|
Jeffrey Lee |
Message #66098, posted by Phlamethrower at 15:42, 31/5/2005, in reply to message #66096 |
Hot Hot Hot Hot Hot Hot Hot Hot Hot Hot Hot Hot Hot stuff
Posts: 15100
|
So how can you make a 2x2 box contain the numbers 1-9 exactly once? |
| |
[ Log in to reply ] |
| |
|
Tony Haines |
Message #66099, posted by Loris at 15:55, 31/5/2005, in reply to message #66098 |
Ha ha, me mine, mwahahahaha
Posts: 1025
|
That is clearly just one format. I'm sure you can work out a reduced set of symbols to fit in four gaps. |
| |
[ Log in to reply ] |
| |
|
Jeffrey Lee |
Message #66100, posted by Phlamethrower at 16:22, 31/5/2005, in reply to message #66099 |
Hot Hot Hot Hot Hot Hot Hot Hot Hot Hot Hot Hot Hot stuff
Posts: 15100
|
1  |4 2
4 2 |1
-------------
2 4 |1
1 |2 4
Easy! I could even write a program to do it 
[Edited by Phlamethrower at 16:24, 31/5/2005] |
| |
[ Log in to reply ] |
| |
|
Adrian Lees |
Message #66101, posted by adrianl at 16:26, 31/5/2005, in reply to message #66100 |
Member
Posts: 1637
|
Easy! I could even write a program to do it Bloody hell, it must be easy
sorry, but you walked straight into that!  |
| |
[ Log in to reply ] |
| |
|
Jeffrey Lee |
Message #66102, posted by Phlamethrower at 16:33, 31/5/2005, in reply to message #66101 |
Hot Hot Hot Hot Hot Hot Hot Hot Hot Hot Hot Hot Hot stuff
Posts: 15100
|
Bloody hell, it must be easy
sorry, but you walked straight into that! Well, it is! |
| |
[ Log in to reply ] |
| |
|
Adrian Lees |
Message #66103, posted by adrianl at 17:13, 31/5/2005, in reply to message #66102 |
Member
Posts: 1637
|
There should be a geeks' version, with a 4 x 4 grid of 4 x 4 subgrids each containing the symbols 0-F |
| |
[ Log in to reply ] |
| |
|
Jeffrey Lee |
Message #66105, posted by Phlamethrower at 17:20, 31/5/2005, in reply to message #66103 |
Hot Hot Hot Hot Hot Hot Hot Hot Hot Hot Hot Hot Hot stuff
Posts: 15100
|
4-dimensional version? |
| |
[ Log in to reply ] |
| |
|
Tony Haines |
Message #66106, posted by Loris at 17:30, 31/5/2005, in reply to message #66103 |
Ha ha, me mine, mwahahahaha
Posts: 1025
|
Try doing a proper (moderately hard) one and you'll probably change your mind on that.
Actually when I first heard about them I thought they would be mildly interesting for a few minutes, but a program to solve them would be more of a challenge. |
| |
[ Log in to reply ] |
| |
|
Jeffrey Lee |
Message #66107, posted by Phlamethrower at 17:44, 31/5/2005, in reply to message #66106 |
Hot Hot Hot Hot Hot Hot Hot Hot Hot Hot Hot Hot Hot stuff
Posts: 15100
|
Actually when I first heard about them I thought they would be mildly interesting for a few minutes, but a program to solve them would be more of a challenge. Nah!
For each row, column and grid, make a list of the symbols that haven't been used. Then for each square without a symbol, AND the appropriate lists together, so that you get a list of possible symbols for that location. Collect all 1-length lists into one list, and remember the shortest list which is more than 1 symbol long. If you have any 1-length lists, add their contents to the puzzle, update the row/column/grid lists, and start again. If you don't have any 1-length lists, then you'll need to try the alternatives presented in the longer-than-1-length-list, backtracking if you encounter a situation where no other options are possible.
An hour or two of poking around in Prolog and you'll have a solution. Probably won't take too long to write a solution in other languages, either.
[Edited by Phlamethrower at 17:46, 31/5/2005] |
| |
[ Log in to reply ] |
| |
|
Adrian Lees |
Message #66108, posted by adrianl at 17:49, 31/5/2005, in reply to message #66107 |
Member
Posts: 1637
|
That's if you haven't run out of memory first. My instinct tells me that it's probably akin to solving the rubik cube by brute force. Combinatorial explosion -> lots of memory and/or time. |
| |
[ Log in to reply ] |
| |
|
Jeffrey Lee |
Message #66109, posted by Phlamethrower at 17:55, 31/5/2005, in reply to message #66108 |
Hot Hot Hot Hot Hot Hot Hot Hot Hot Hot Hot Hot Hot stuff
Posts: 15100
|
That's the idea of taking the 1-length lists first - they'll remove the majority of the combinations for you. |
| |
[ Log in to reply ] |
| |
|
Tony Haines |
Message #66110, posted by Loris at 18:02, 31/5/2005, in reply to message #66107 |
Ha ha, me mine, mwahahahaha
Posts: 1025
|
That may work for some of the easier puzzles I suppose.
I've only done a couple, so I'm no expert, but there are other inferences to make.
Your strategy will pick up the 'obvious' holes quickly. However, a simple catch may be that while several symbols could fit in a particular square, it has to be one, because of other squares already being used.
I guess your backtracking would work, but it is kind of brute force and therefore inelegant.
...and do it in befunge. |
| |
[ Log in to reply ] |
| |
|
Jeffrey Lee |
Message #66111, posted by Phlamethrower at 18:09, 31/5/2005, in reply to message #66110 |
Hot Hot Hot Hot Hot Hot Hot Hot Hot Hot Hot Hot Hot stuff
Posts: 15100
|
...and do it in befunge. OK, saves me having to remind myself of the finer points of Prolog |
| |
[ Log in to reply ] |
| |
|
Jeffrey Lee |
Message #66112, posted by Phlamethrower at 18:39, 31/5/2005, in reply to message #66111 |
Hot Hot Hot Hot Hot Hot Hot Hot Hot Hot Hot Hot Hot stuff
Posts: 15100
|
*starts work* |
| |
[ Log in to reply ] |
| |
|
Adrian Lees |
Message #66118, posted by adrianl at 19:39, 31/5/2005, in reply to message #66112 |
Member
Posts: 1637
|
I think you'll find that there aren't any 1-length lists to start with, you only get those later, as you start to approach the solution; hence they don't solve the combinatorial problem.
If there were, the puzzle wouldn't be much of a puzzle
When I first encountered a Sudoku (note, I've not actually tried in earnest to solve any so I could be speaking out of my fundament), I idly wondered how to solve it (as coders do), and wondered about what's called a relaxation network; each square is like a neuron in a network and it tries to drive its neighbours into the appropriate states so that it can attain a valid state itself.... so if 'I' look at my neighbours in the row, column and grid, and decide I need to be either a 5 or a 3, I produce a signal to my neighbours to steer them away from those values.
The network then ends up oscillating, over many iterations, and - with luck! - converges upon a solution.
[Edited by adrianl at 19:45, 31/5/2005] |
| |
[ Log in to reply ] |
| |
|
Richard Wilson |
Message #66119, posted by not_ginger_matt at 19:57, 31/5/2005, in reply to message #66118 |
Member
Posts: 63
|
I think you'll find that there aren't any 1-length lists to start with, you only get those later, as you start to approach the solution; hence they don't solve the combinatorial problem.
If there were, the puzzle wouldn't be much of a puzzle
I got hooked on these puzzles a few weeks ago and wrote a very simple program to solve them. All it does is scan the horizontal columns, vertical columns and grid to find possible values (as mentioned earlier in this thread) and then when it's run out of things it can fill in (only generally on hard puzzles) it stores the current state to fall back to and puts an available option from a field and recurses.
The hard part of the puzzles, in my opinion, is creating ones that are just the correct difficulty.
[Edited by not_ginger_matt at 19:58, 31/5/2005] |
| |
[ Log in to reply ] |
| |
|
Jeffrey Lee |
Message #66120, posted by Phlamethrower at 20:10, 31/5/2005, in reply to message #66118 |
Hot Hot Hot Hot Hot Hot Hot Hot Hot Hot Hot Hot Hot stuff
Posts: 15100
|
I think you'll find that there aren't any 1-length lists to start with, you only get those later, as you start to approach the solution; hence they don't solve the combinatorial problem. Combinational complexity + befunge = fun
I've written the initialisation code (detect puzzle size, build initial row/column/grid lists), and am now starting work on the code that builds the lists of possible moves. |
| |
[ Log in to reply ] |
| |
|
Matthew Somerville |
Message #66121, posted by Matthew at 20:38, 31/5/2005, in reply to message #66119 |
Posts: 520
|
then when it's run out of things it can fill in (only generally on hard puzzles) it stores the current state to fall back to and puts an available option from a field and recurses. Ah, but the point of Su Doku is that all puzzles are solvable using only logic; you never need to choose an option and recurse. Obviously that only works if your program has every sort of logic that you yourself have to use.
I do them by hand myself, more fun. Logic steps include, but are not limited to: "that one must be a 1 because it's the only place in that square that isn't blanked out by 1s in other rows and columns", "those two are both a 4 or a 6, therefore nothing else in that square can be a 4 or a 6", and so on.  |
| |
[ Log in to reply ] |
| |
|
Jeffrey Lee |
Message #66122, posted by Phlamethrower at 20:47, 31/5/2005, in reply to message #66121 |
Hot Hot Hot Hot Hot Hot Hot Hot Hot Hot Hot Hot Hot stuff
Posts: 15100
|
I do them by hand myself, more fun. Logic steps include, but are not limited to: "that one must be a 1 because it's the only place in that square that isn't blanked out by 1s in other rows and columns", "those two are both a 4 or a 6, therefore nothing else in that square can be a 4 or a 6", and so on. Which is essentially what my program will encapsulate
Hopefully backtracking won't be needed, because I'm not too sure if this current design can support it  |
| |
[ Log in to reply ] |
| |
|
Jeffrey Lee |
Message #66123, posted by Phlamethrower at 21:04, 31/5/2005, in reply to message #66122 |
Hot Hot Hot Hot Hot Hot Hot Hot Hot Hot Hot Hot Hot stuff
Posts: 15100
|
OK - Providing backtracking isn't needed, this program should work... (and exit if it finds a backtracking case)
*runs* |
| |
[ Log in to reply ] |
| |
|
Jeffrey Lee |
Message #66124, posted by Phlamethrower at 21:06, 31/5/2005, in reply to message #66123 |
Hot Hot Hot Hot Hot Hot Hot Hot Hot Hot Hot Hot Hot stuff
Posts: 15100
|
Bah, it's exiting... |
| |
[ Log in to reply ] |
| |
|
Jeffrey Lee |
Message #66125, posted by Phlamethrower at 21:19, 31/5/2005, in reply to message #66124 |
Hot Hot Hot Hot Hot Hot Hot Hot Hot Hot Hot Hot Hot stuff
Posts: 15100
|
*fixes some bugs*
Hmm, now it's overwriting itself |
| |
[ Log in to reply ] |
| |
|
Adrian Lees |
Message #66126, posted by adrianl at 21:23, 31/5/2005, in reply to message #66125 |
Member
Posts: 1637
|
*fixes some bugs*
Hmm, now it's overwriting itself Omg, it's become self-aware! |
| |
[ Log in to reply ] |
| |
|
Jeffrey Lee |
Message #66127, posted by Phlamethrower at 21:29, 31/5/2005, in reply to message #66126 |
Hot Hot Hot Hot Hot Hot Hot Hot Hot Hot Hot Hot Hot stuff
Posts: 15100
|
*fixes some bugs*
Hmm, now it's overwriting itself Omg, it's become self-aware!
Yah... memory leaks in Befunge programs are fun
*checks code 1 instruction at a time* |
| |
[ Log in to reply ] |
| |
|
Jeffrey Lee |
Message #66128, posted by Phlamethrower at 21:55, 31/5/2005, in reply to message #66127 |
Hot Hot Hot Hot Hot Hot Hot Hot Hot Hot Hot Hot Hot stuff
Posts: 15100
|
My debugger is buggy  |
| |
[ Log in to reply ] |
| |
|
Andrew Poole |
Message #66131, posted by andypoole at 22:05, 31/5/2005, in reply to message #66128 |
Posts: 5558
|
My debugger is buggy Well debug it then |
| |
[ Log in to reply ] |
| |
|
Jeffrey Lee |
Message #66132, posted by Phlamethrower at 22:12, 31/5/2005, in reply to message #66131 |
Hot Hot Hot Hot Hot Hot Hot Hot Hot Hot Hot Hot Hot stuff
Posts: 15100
|
My debugger is buggy Well debug it then
Have done
Now to fix the code so that it compiles using my new library files and the new version of GCC |
| |
[ Log in to reply ] |
| |
|
Jeffrey Lee |
Message #66133, posted by Phlamethrower at 22:25, 31/5/2005, in reply to message #66132 |
Hot Hot Hot Hot Hot Hot Hot Hot Hot Hot Hot Hot Hot stuff
Posts: 15100
|
Ah, the sweet soun^H^H^Hight of error-less compiling
*updates doccymentation and prepares website update while he waits* (*)
(*) and posts on forum |
| |
[ Log in to reply ] |
| |
| Pages (4): |< <
2
> >|
|
