[xclite]

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

[NotarySojac]

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?

[Tethik]

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

# A cell is just a number.
# If locked = true then it should mean that it was part of the
# original puzzle and should therefore not be changed.
class Cell
	attr_accessor :locked, :number
	#@@count = 0 #counted to 81 :)/>

	def initialize(locked, number)
		@locked = locked
		@number = number
		#@@count += 1
	end

	def to_s
		return number.to_s if number > 0
		return ""
	end
end

Block class:

Spoiler

load 'Cell.rb'

# A Block is supposed to be either a row, block or column in the soduku
# table. This means it contains 9 cells.
class Block
	attr_accessor :cells
	
	def initialize
		@cells = []
	end
	

	# By passing the same cell to each row, column etc we use the same reference
	def setCell(position, number)
		@cells[position].number = number
	end

	def createCell(position, cell)
		@cells[position] = cell
	end

	# Check all other positions and return values which 
	# don't exists yet.	
	def getPossibilities(position)
		possible = [ 1, 2, 3, 4, 5, 6, 7, 8, 9 ]
		
		@cells.each do |cell|
			possible.delete ( cell.number )
		end

		return possible
	end

	def getCell(position)
		return @cells[position]
	end

	
	def to_s
		returnString = "" 
		@cells.each do |cell| returnString += cell.to_s + "," end		

		return returnString[0,returnString.length - 1]
	end
end

Sudoku class:

Spoiler

load 'Block.rb'

class Sudoku
	attr_accessor :rows, :boxes, :cols
	
	def initialize()
		@rows = []
		@boxes = []
		@cols = []
		1.upto(9) {
			@rows << Block.new
			@boxes << Block.new
			@cols << Block.new		
		}
	end
	
	private 
	
	#Returns the row(s) index at specified cell position
	
	#Block array indexes
	def rows_index(cell_index)
		return cell_index / 9 
	end
	
	def boxes_index(cell_index)
		return cols_index(cell_index) / 3  + 3 * (rows_index(cell_index) / 3)
	end

	def cols_index(cell_index)
		return cell_index % 9
	end

	# 0 1 2 0 1 2 0 1 2
	# 3 4 5 3 4 5 3 4 5
	# 6 7 8 6 7 8 6 7 8
	#  .. etc
	#
	def box_index(cell_index)
		return cell_index % 3 + 3 * (rows_index(cell_index) % 3)
	end


	public



	# Parses the puzzle into rows, columns and boxes
	def parse(input)	
		rows = input.each_line 

		row_index = 0 # The current row
		cell_index = 0 # The current cell
		# 0 -> 8 is first row
		# 9 -> 17 is second
		# etc..

		rows.each do |row|
			if row_index > 8 
				break
			end
			numbers = row.split(',')	
			col_index = 0 # The current column
			
			numbers.each do |number|
				
				box_index = col_index / 3  + 3 * (row_index / 3)
				box_cell_index = cell_index % 3 + 3 * (row_index % 3)
				#print "[" + box_index.to_s + "," + box_cell_index.to_s + "]"
				number = number.delete ","
				number = number.to_i
				
				locked = true if number > 0			

				cell= Cell.new(locked, number)
				@rows[row_index].createCell(col_index, cell)
				@cols[col_index].createCell(row_index, cell)
				@boxes[box_index].createCell(box_cell_index, cell)
				col_index += 1
				cell_index += 1 
			end	
			#puts 
			row_index += 1 # less expensive than /?
		end
	end

	# Attempts to solve the puzzle
	# returns true or false depending on whether or not it solved the puzzle
	def solve
		
		cell_index = 0
		# move to the right position..
		cell_index += 1 until cell_index > 80 || !@rows[rows_index(cell_index)].cells[cols_index(cell_index)].locked

		while cell_index >= 0 && cell_index < 81 do
			
			# Get row, column and box
			row = @rows[rows_index(cell_index)]
			col = @cols[cols_index(cell_index)]
			box = @boxes[boxes_index(cell_index)]

		 	# Get current value
			value = row.cells[cols_index(cell_index)] # Object of type Cell
			

			# Get next possible value
			possible = 0
			if value.number < 9
				possible_from_row = row.getPossibilities(cols_index(cell_index))
				possible_from_col = col.getPossibilities(rows_index(cell_index))
				possible_from_box = box.getPossibilities(boxes_index(cell_index))
				
				for n in (value.number + 1)..9 do
					if possible_from_row.include?(n) && possible_from_col.include?(n) && possible_from_box.include?(n)
						possible = n
						break
					end
				end
			end

			 #Step by step testing.
			 #show
			 #puts cell_index.to_s
			 #puts
			 #gets
			
			
			if possible == 0
				setCell(cell_index, 0)
				cell_index -= 1
				cell_index -= 1 until cell_index < 0 || !getCell(cell_index).locked
			else
				setCell(cell_index, possible)
				cell_index += 1
			   	cell_index += 1 until cell_index > 80 || !getCell(cell_index).locked
			end							
		end

		if cell_index < 0
			return false
		else
			return true
		end
	end

	def show
		puts to_s
	end

	def to_s
		s = ""
		rows.each do |row| s += row.to_s + "\n" end
		return s
	end

	def setCell(cell_index, number)
		@rows[rows_index(cell_index)].setCell(cols_index(cell_index), number)
	end

	def getCell(cell_index)
		return @rows[rows_index(cell_index)].getCell(cols_index(cell_index))
	end
end

if ARGV.count < 1
	puts "Usage: Sudoku.rb <inputfile>"
	puts "Optional-usage: Sudoku.rb <inputfile> <outputfile>"
	exit
end

input = File.open(ARGV[0])
puzzle = Sudoku.new
puzzle.parse(input)
#puzzle.rows.each do |row| puts row.to_s end
# Test box and col assignment:
#puzzle.boxes.each do |row| puts row.to_s end
#puzzle.cols.each do |row| puts row.to_s end

#puzzle.show
if !puzzle.solve()
   puts "Unable to solve!"
elsif ARGV.count > 1
   f = File.open(ARGV[1], "w")
   f.puts puzzle.to_s
else
    puzzle.show	
end

Attached File(s)

•  sudoku.tar.gz (2K)
  Number of downloads: 93

[xclite]

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

[NotarySojac]

Tethik, on 18 June 2011 - 08:53 PM, said:

Spoiler

24 def getPossibilities(position)
25 possible = [ 1, 2, 3, 4, 5, 6, 7, 8, 9 ]
26
27 @cells.each do |cell|
28 possible.delete ( cell.number )
29 end

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.

[NotarySojac]

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

[kiwi2]

Spoiler

<?php

$array = array("1" , "2" , "3" , "4" , "5" , "6" , "7" , "8" , "9");
shuffle($array);
foreach ($array as $ar) 
{ 
echo "$ar"; 
} 
echo "<br />";
$one[0] ="$array[5]";
$one[1] ="$array[4]";
$one[2] ="$array[3]";
$one[3] ="$array[8]";
$one[4] ="$array[6]";
$one[5] ="$array[7]";
$one[6] ="$array[2]";
$one[7] ="$array[1]";
$one[8] ="$array[0]";
foreach ($one as $on) 
{ 
echo "$on"; 
} 
echo "<br />";
$two[0] ="$one[4]";
$two[1] ="$one[5]";
$two[2] ="$one[3]";
$two[3] ="$one[8]";
$two[4] ="$one[7]";
$two[5] ="$one[6]";
$two[6] ="$one[2]";
$two[7] ="$one[1]";
$two[8] ="$one[0]";
foreach ($two as $to) 
{ 
echo "$to"; 
} 
echo "<br />";
$three[0] ="$two[1]";
$three[1] ="$two[3]";
$three[2] ="$two[4]";
$three[3] ="$two[5]";
$three[4] ="$two[6]";
$three[5] ="$two[7]";
$three[6] ="$two[8]";
$three[7] ="$two[2]";
$three[8] ="$two[0]";
foreach ($three as $th) 
{ 
echo "$th"; 
} 
echo "<br />";
$four[0] ="$three[5]";
$four[1] ="$three[4]";
$four[2] ="$three[6]";
$four[3] ="$three[0]";
$four[4] ="$three[7]";
$four[5] ="$three[8]";
$four[6] ="$three[1]";
$four[7] ="$three[3]";
$four[8] ="$three[2]";
foreach ($four as $fo) 
{ 
echo "$fo"; 
} 
echo "<br />";
$five[0] ="$four[7]";
$five[1] ="$four[4]";
$five[2] ="$four[5]";
$five[3] ="$four[2]";
$five[4] ="$four[6]";
$five[5] ="$four[8]";
$five[6] ="$four[3]";
$five[7] ="$four[1]";
$five[8] ="$four[0]";
foreach ($five as $fi) 
{ 
echo "$fi"; 
} 
echo "<br />";
$six[0] ="$five[7]";
$six[1] ="$five[3]";
$six[2] ="$five[8]";
$six[3] ="$five[5]";
$six[4] ="$five[0]";
$six[5] ="$five[4]";
$six[6] ="$five[1]";
$six[7] ="$five[2]";
$six[8] ="$five[6]";
foreach ($six as $si) 
{ 
echo "$si"; 
} 
echo "<br />";
$sev[0] ="$six[3]";
$sev[1] ="$six[4]";
$sev[2] ="$six[5]";
$sev[3] ="$six[7]";
$sev[4] ="$six[8]";
$sev[5] ="$six[6]";
$sev[6]="$six[2]";
$sev[7] ="$six[1]";
$sev[8] ="$six[0]";
foreach ($sev as $se) 
{ 
echo "$se"; 
} 
echo "<br />";
$eig[0] ="$sev[5]";
$eig[1] ="$sev[3]";
$eig[2] ="$sev[4]";
$eig[3] ="$sev[6]";
$eig[4] ="$sev[7]";
$eig[5] ="$sev[8]";
$eig[6] ="$sev[0]";
$eig[7] ="$sev[2]";
$eig[8] ="$sev[1]";
foreach ($eig as $ei) 
{ 
echo "$ei"; 
} 
?>

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)!!!

[Tethik]

NotarySojac, 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

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

[NotarySojac]

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 have:
1) A main.rb,
2) A Board class
3) A Region class



I instantiate a Board object in main myBoard = Board.new.

myBoard populates itself with 9 'Region' elements.

myBoard has a method to 'set_val'. This is a trivial matter since regions are defined in the Board class.

As things developed, it turned out I needed to set variables in other Regions from within a region. So I would like to invoke Board::set_val from within a Region.

This is difficult because self is only 1 of the 9 regions that needs to have values altered.

How can I do this?

Here's a simplified example that doesn't work:

class Board
  attr_accessor :regions
  def initialize
    @regions = []
    (0..8).each do |i|
      @regions[i] = Region.new
    end
  end

  def set_val(v)
    @regions.each do |reg|
      reg.index = v
    end
  end
end


class Region
  attr_accessor :index

  def r_func(val)
    set_val(val)
  end
  


end


myBoard = Board.new

myBoard.regions[0].r_func(2)      # fails

[Tethik]

NotarySojac, 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 have:
1) A main.rb,
2) A Board class
3) A Region class



I instantiate a Board object in main myBoard = Board.new.

myBoard populates itself with 9 'Region' elements.

myBoard has a method to 'set_val'. This is a trivial matter since regions are defined in the Board class.

As things developed, it turned out I needed to set variables in other Regions from within a region. So I would like to invoke Board::set_val from within a Region.

This is difficult because self is only 1 of the 9 regions that needs to have values altered.

How can I do this?

Here's a simplified example that doesn't work:

class Board
  attr_accessor :regions
  def initialize
    @regions = []
    (0..8).each do |i|
      @regions[i] = Region.new
    end
  end

  def set_val(v)
    @regions.each do |reg|
      reg.index = v
    end
  end
end


class Region
  attr_accessor :index

  def r_func(val)
    set_val(val)
  end
  


end


myBoard = Board.new

myBoard.regions[0].r_func(2)      # fails

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

[NotarySojac]

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

It looks like setCell is only used on the sudoku class.

			if possible == 0          # If nothing was possible, using the three basic algos, set the cell to zero?, and then backpedal?
				setCell(cell_index, 0)
				cell_index -= 1
				cell_index -= 1 until cell_index < 0 || !getCell(cell_index).locked    # backup to the next cell that isn't locked, or to zero
			else
				setCell(cell_index, possible)       # plug in the answer into the square.  The answer may be wrong though?
        @count_possible += 1
        puts
        self.show

Unless I'm reading it wrong.

[Tethik]

NotarySojac, 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

It looks like setCell is only used on the sudoku class.

			if possible == 0          # If nothing was possible, using the three basic algos, set the cell to zero?, and then backpedal?
				setCell(cell_index, 0)
				cell_index -= 1
				cell_index -= 1 until cell_index < 0 || !getCell(cell_index).locked    # backup to the next cell that isn't locked, or to zero
			else
				setCell(cell_index, possible)       # plug in the answer into the square.  The answer may be wrong though?
        @count_possible += 1
        puts
        self.show

Unless I'm reading it wrong.

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.

[NotarySojac]

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

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

[NotarySojac]

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?

[Tethik]

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

load 'Cell.rb'

# A Block is supposed to be either a row, block or column in the soduku
# table. This means it contains 9 cells.
class Block
	attr_accessor :values
	
	def initialize
		@values = 0
	end
	
	def setCell(oldvalue, newvalue)
		if(oldvalue != 0 && contains(oldvalue))
			@values -= (1 << oldvalue)
		end
		
		if(newvalue != 0)
			@values |= (1 << newvalue)	
		end		
	end

	def contains(value)
		return @values & (1 << value) == (1 << value)
	end

end

Spoiler

# A cell is just a number.
# If locked = true then it should mean that it was part of the
# original puzzle and should therefore not be changed.
class Cell
	private
	attr_accessor :number, :row, :col, :box
	#@@count = 0 #counted to 81 :)/>

	public
	def initialize(row, col, box)
		@number = 0
		@row = row
		@col = col
		@box = box
	end

	def set(number)
		row.setCell(@number, number)
		col.setCell(@number, number)
		box.setCell(@number, number)

		@number = number
	end

	def isPossible(value)
		return !row.contains(value) && !col.contains(value) && !box.contains(value)
	end

	def nextPossible()
		possible = @number + 1	
		while(possible <= 9)
			if(isPossible(possible))
				break
			end
			possible += 1
		end	
		
		return possible
	end

	def to_s
		return number.to_s
	end
end

Spoiler

load 'Block.rb'

class Sudoku
	attr_accessor :cells, :unsolved
	
	def initialize()
		@cells = []
		@unsolved = []
	end

	# Parses the puzzle into rows, columns and boxes
	def parse(input)	
		lines = input.each_line 

		rows = []
		boxes = []
		cols = []
		1.upto(9) {
			rows << Block.new
			boxes << Block.new
			cols << Block.new		
		}

		r = 0 # The current row
		cell_index = 0 # The current cell

		lines.each do |line|
			if r > 8 
				break
			end
			numbers = line.split(',')	
			c = 0 # The current column
			
			numbers.each do |number|				
				b = c / 3 + 3 * (r / 3) # The current box
				number = number.delete ","
				number = number.to_i
				
				cell= Cell.new(rows[r], cols[c], boxes[b])
				#print r.to_s + c.to_s + b.to_s + " "
				number = 0 if number == nil
				cell.set(number)

				if number == 0
					@unsolved << cell
				end
								
				@cells[cell_index] = cell;
				
				c += 1
				cell_index += 1 
			end	
			r += 1 
			#puts
		end
		#puts
		#show
		#gets
	end

	# Attempts to solve the puzzle
	# returns true or false depending on whether or not it solved the puzzle
	def solve
		
		cell_index = 0
		# move to the right position..
		# puts @unsolved.length.to_s + " unknown cells!"

		while cell_index >= 0 && cell_index < @unsolved.length do
			cell = @unsolved[cell_index];
			
			possible = cell.nextPossible()	

			if possible > 9 || possible <= 0
				cell.set(0)
				cell_index -= 1
			else
				cell.set(possible)
				cell_index += 1
			end							
		end

		if cell_index < 0
			return false
		else
			return true
		end
	end

	def show
		puts to_s
	end

	def to_s
		s = ""
		i = 0
		@cells.each do |cell| 
			if i % 9  == 0 && i > 0
				s += "\n"
			end		
	
			s += cell.to_s	
			if (i+1) % 9 != 0
				s += ","
			end		
			i += 1
		end
		return s
	end

end

if ARGV.count < 1
	puts "Usage: Sudoku.rb <inputfile>"
	puts "Optional-usage: Sudoku.rb <inputfile> <outputfile>"
	exit
end

input = File.open(ARGV[0])
puzzle = Sudoku.new
puzzle.parse(input)

#puzzle.show
before = Time.now()
solved = puzzle.solve()
diff = Time.now() - before
puts "Solved for: " + diff.to_s  + " seconds"
if !solved
   puts "Unable to solve!"
elsif ARGV.count > 1
   f = File.open(ARGV[1], "w")
   f.puts puzzle.to_s
else
    puzzle.show	
end

Attached File(s)

•  sudoku-solver2.tar.gz (1.77K)
  Number of downloads: 71