Ruby Challenge: Sudoku

  • (2 Pages)
  • +
  • 1
  • 2

25 Replies - 12737 Views - Last Post: 24 July 2011 - 07:24 PM Rate Topic: -----

#1 xclite  Icon User is offline

  • LIKE A BOSS
  • member icon


Reputation: 915
  • View blog
  • Posts: 3,195
  • Joined: 12-May 09

Ruby Challenge: Sudoku

Post icon  Posted 17 June 2011 - 11:56 AM

The guys in VB.NET beat me to it (I was still finalizing my solution when I wasn't at work), but I wanted to do a challenge involving Sudoku.

To quote wikipedia:

Quote

The objective is to fill a 9×9 grid with digits so that each column, each row, and each of the nine 3×3 sub-grids that compose the grid (also called "boxes", "blocks", "regions", or "sub-squares") contains all of the digits from 1 to 9. The puzzle setter provides a partially completed grid, which typically has a unique solution.

Completed puzzles are always a type of Latin square with an additional constraint on the contents of individual regions. For example, the same single integer may not appear twice in the same 9x9 playing board row or column or in any of the nine 3x3 subregions of the 9x9 playing board.


There will actually be a winner of this one, although I don't have any fancy prizes to hand out (yet? I don't know what my options are here). Winner will be based purely on efficiency, although it would behoove one to make their solution readable.

Requirements:
The program should allow me to specify a file that contains a sudoku puzzle in the following format:
5,3,,,7,,,,
6,,,1,9,5,,,
,9,8,,,,,6,
8,,,,6,,,,3
4,,,8,,3,,,1
7,,,,2,,,,6
,6,,,,,2,8,
,,,4,1,9,,,5
,,,,8,,,7,9


Basically, a comma separated file, each line representing a row from an incomplete puzzle. The output should be the same, except completed.

The program should also be able to solve "invalid" Sudoku puzzles, i.e. puzzles that do not provide you with a known starting point (the example I gave gives enough information that you deduce a value to start with). These require some sort of "guess and check" algorithm instead of just deductive reasoning.

If you're realllly feeling adventurous, write a script to generate such puzzles (not part of the competition, just a mental exercise).

I'll take submissions as late as June 30th to determine the winner.

This post has been edited by xclite: 17 June 2011 - 11:57 AM


Is This A Good Question/Topic? 4
  • +

Replies To: Ruby Challenge: Sudoku

#2 NotarySojac  Icon User is offline

  • D.I.C Regular
  • member icon

Reputation: 53
  • View blog
  • Posts: 428
  • Joined: 30-September 10

Re: Ruby Challenge: Sudoku

Posted 18 June 2011 - 01:25 PM

Quote

...
The program should also be able to solve "invalid" Sudoku puzzles, i.e. puzzles that do not provide you with a known starting point...


Could you expand on what this means? Do you mean the program should work on a puzzle such as...

5,3,,,7,,,,
,,,,,,,,
,,,,,,,,
,,,,,,,,
,,,,,,,,
,,,,,,,,
,,,,,,,,
,,,,,,,,
,,,,,,,,



...where there are obviously multiple solutions?
Was This Post Helpful? 0
  • +
  • -

#3 Tethik  Icon User is offline

  • D.I.C Head

Reputation: 17
  • View blog
  • Posts: 61
  • Joined: 14-March 10

Re: Ruby Challenge: Sudoku

Posted 18 June 2011 - 08:53 PM

I guess I'll be the first to submit then. Nothing great though, simple guessing algorithm only. Way too many indexes though <_<

I haven't tested it thoroughly though but it should work.

Cell class:
Spoiler


Block class:
Spoiler


Sudoku class:
Spoiler

Attached File(s)


Was This Post Helpful? 2
  • +
  • -

#4 xclite  Icon User is offline

  • LIKE A BOSS
  • member icon


Reputation: 915
  • View blog
  • Posts: 3,195
  • Joined: 12-May 09

Re: Ruby Challenge: Sudoku

Posted 18 June 2011 - 10:08 PM

View PostNotarySojac, on 18 June 2011 - 04:25 PM, said:

Quote

...
The program should also be able to solve "invalid" Sudoku puzzles, i.e. puzzles that do not provide you with a known starting point...


Could you expand on what this means? Do you mean the program should work on a puzzle such as...

5,3,,,7,,,,
,,,,,,,,
,,,,,,,,
,,,,,,,,
,,,,,,,,
,,,,,,,,
,,,,,,,,
,,,,,,,,
,,,,,,,,



...where there are obviously multiple solutions?

Correct, although the puzzles used for such testing wouldn't be as... easy. Just slightly less constrained valid sudokus.
Was This Post Helpful? 0
  • +
  • -

#5 NotarySojac  Icon User is offline

  • D.I.C Regular
  • member icon

Reputation: 53
  • View blog
  • Posts: 428
  • Joined: 30-September 10

Re: Ruby Challenge: Sudoku

Posted 19 June 2011 - 11:13 AM

View PostTethik, on 18 June 2011 - 08:53 PM, said:

Spoiler


Brilliant! I've been pulling my hair out for hours trying to get ruby to do possible = (1..9).to_a - xnot.to_a to utterly no effect at runtime.
Was This Post Helpful? 0
  • +
  • -

#6 NotarySojac  Icon User is offline

  • D.I.C Regular
  • member icon

Reputation: 53
  • View blog
  • Posts: 428
  • Joined: 30-September 10

Re: Ruby Challenge: Sudoku

Posted 20 June 2011 - 05:39 PM

Tethik, did you make any unit tests for your project?
Was This Post Helpful? 0
  • +
  • -

#7 kiwi2  Icon User is offline

  • D.I.C Head
  • member icon

Reputation: 8
  • View blog
  • Posts: 178
  • Joined: 16-September 08

Re: Ruby Challenge: Sudoku

Posted 21 June 2011 - 11:49 AM

Spoiler



not ruby but the logic is the same..

This post has been edited by macosxnerd101: 21 June 2011 - 11:50 AM
Reason for edit:: You have 170 posts. Seriously, use code tags (and spoiler tags since this is a challenge)!!!

Was This Post Helpful? 2
  • +
  • -

#8 Tethik  Icon User is offline

  • D.I.C Head

Reputation: 17
  • View blog
  • Posts: 61
  • Joined: 14-March 10

Re: Ruby Challenge: Sudoku

Posted 21 June 2011 - 04:38 PM

View PostNotarySojac, on 20 June 2011 - 05:39 PM, said:

Tethik, did you make any unit tests for your project?


Unfortunately nope. I intend to rewrite and/or add some parts to make it more efficient though so maybe I'll make some then. If somebody made that generator we could use that to make a bunch of tests.

Looks like Kiwi gaves us one :P

This post has been edited by Tethik: 21 June 2011 - 04:41 PM

Was This Post Helpful? 0
  • +
  • -

#9 NotarySojac  Icon User is offline

  • D.I.C Regular
  • member icon

Reputation: 53
  • View blog
  • Posts: 428
  • Joined: 30-September 10

Re: Ruby Challenge: Sudoku

Posted 22 June 2011 - 03:17 PM

Ok, I'm trying to solve it all the way, and I'm running into some issues due to my use of objects. I'll put my post in a spoiler just in case it's got too many ideas in it.

Spoiler

Was This Post Helpful? 0
  • +
  • -

#10 Tethik  Icon User is offline

  • D.I.C Head

Reputation: 17
  • View blog
  • Posts: 61
  • Joined: 14-March 10

Re: Ruby Challenge: Sudoku

Posted 23 June 2011 - 12:37 AM

View PostNotarySojac, on 22 June 2011 - 03:17 PM, said:

Ok, I'm trying to solve it all the way, and I'm running into some issues due to my use of objects. I'll put my post in a spoiler just in case it's got too many ideas in it.

Spoiler


I solved it by giving my "Blocks" the same references for the same cells (a Block is either a column, a row or a 3x3 Box so they overlap). Try doing that with your regions, that way they will change value when one is changed. Tip: you can only reference objects, no primitive types.

This post has been edited by Tethik: 23 June 2011 - 12:38 AM

Was This Post Helpful? 0
  • +
  • -

#11 NotarySojac  Icon User is offline

  • D.I.C Regular
  • member icon

Reputation: 53
  • View blog
  • Posts: 428
  • Joined: 30-September 10

Re: Ruby Challenge: Sudoku

Posted 23 June 2011 - 09:24 AM

I took a moment to study your solutions (well written btw) but I can't find what you're talking about in your code.

Spoiler

Was This Post Helpful? 0
  • +
  • -

#12 Tethik  Icon User is offline

  • D.I.C Head

Reputation: 17
  • View blog
  • Posts: 61
  • Joined: 14-March 10

Re: Ruby Challenge: Sudoku

Posted 23 June 2011 - 02:55 PM

View PostNotarySojac, on 23 June 2011 - 09:24 AM, said:

I took a moment to study your solutions (well written btw) but I can't find what you're talking about in your code.

Spoiler


You're correct in the interpretation but you might be looking in the wrong place.

I set all my Blocks to reference the same cell when they are created. I.E. when the file is parsed.
As for the code being well written, I dunno. Lots of bad stuff efficiency-wise.
Was This Post Helpful? 0
  • +
  • -

#13 NotarySojac  Icon User is offline

  • D.I.C Regular
  • member icon

Reputation: 53
  • View blog
  • Posts: 428
  • Joined: 30-September 10

Re: Ruby Challenge: Sudoku

Posted 24 June 2011 - 01:43 PM

View PostTethik, on 23 June 2011 - 02:55 PM, said:

You're correct in the interpretation but you might be looking in the wrong place.

I set all my Blocks to reference the same cell when they are created. I.E. when the file is parsed.
As for the code being well written, I dunno. Lots of bad stuff efficiency-wise.

I need to make changes to my stuff after parsing AND within the region object though, I'm not sure your code does that, but I may be misunderstanding things, I'm not very good at discussing code.

I figured out the best workaround for me was to have my region return an array and since it's was called from within Board::set_solution, and only called there, it was a cinch to just add some code to check the return value of what my region code sent back. I'm not sure if that makes any sense, but w/e, lol, the code will be done soon and I can highlight things if it's interesting.


View PostTethik, on 23 June 2011 - 02:55 PM, said:

As for the code being well written, I dunno. Lots of bad stuff efficiency-wise.


No way, you wanna see some bad ruby coding? You'll have to check out my solution once I post it. It started out as non-oo before I looked over your work. it was all one file, too, lol.
Was This Post Helpful? 0
  • +
  • -

#14 NotarySojac  Icon User is offline

  • D.I.C Regular
  • member icon

Reputation: 53
  • View blog
  • Posts: 428
  • Joined: 30-September 10

Re: Ruby Challenge: Sudoku

Posted 25 June 2011 - 09:53 AM

I'm stumped on this sudoku,

3,4,,9,,,,,2
2,,,,7,,,8,
6,,1,2,,,,9,
9,,,4,,,3,1,
1,3,4,7,,,,6,9
,,6,3,9,1,,4,5
,,,,,,9,2,4
4,1,3,,2,9,,,
5,,,,4,7,,3,1



AKA
34x 9xx xx2
2xx x7x x8x
6x1 2xx x9x

9xx 4xx 31x
134 7xx x69
xx6 391 x45

xxx xxx 924
413 x29 xxx
5xx x47 x31



Does anyone know what the next tile to solve is?
Was This Post Helpful? 0
  • +
  • -

#15 Tethik  Icon User is offline

  • D.I.C Head

Reputation: 17
  • View blog
  • Posts: 61
  • Joined: 14-March 10

Re: Ruby Challenge: Sudoku

Posted 30 June 2011 - 01:48 PM

Remade the solver with some improvements. Solves the example puzzle around 3-5 times quicker than the original so theres definately a difference. Probably not as big on more annoying puzzles though.

Changes:
  • Each cell now stores a reference to the row, column and box it is contained within instead of vice versa. This way I don't have to keep track of all those damn indexes.
  • Each row/col/box now stores all values in a single variable instead of an array of variables. Operations to find which values are contained etc are done using bitwise operators. This has the benefit of using less memory as well as efficiency.
  • The solving method only iterates through values that weren't given. More memory usage for a tiny bit better efficiency but in my opinion more readable.


Spoiler


Spoiler


Spoiler

Attached File(s)


Was This Post Helpful? 1
  • +
  • -

  • (2 Pages)
  • +
  • 1
  • 2