pep-material: progs/sudoku.scala@17e6f46260bd (annotated)

268 d20583497c5b updated Christian Urban <urbanc@in.tum.de> parents: diff changeset	1	// Sudoku
d20583497c5b updated Christian Urban <urbanc@in.tum.de> parents: diff changeset	2	//========
d20583497c5b updated Christian Urban <urbanc@in.tum.de> parents: diff changeset	3
492 17e6f46260bd updated Christian Urban <christian.urban@kcl.ac.uk> parents: 464 diff changeset	4	// you can call the parallel version with
17e6f46260bd updated Christian Urban <christian.urban@kcl.ac.uk> parents: 464 diff changeset	5	//
17e6f46260bd updated Christian Urban <christian.urban@kcl.ac.uk> parents: 464 diff changeset	6	// scala -cp scala-parallel-collections_3-1.0.4.jar sudoku.scala
301 aa0e86419773 updated Christian Urban <urbanc@in.tum.de> parents: 268 diff changeset	7	//
492 17e6f46260bd updated Christian Urban <christian.urban@kcl.ac.uk> parents: 464 diff changeset	8	// or with java directly
301 aa0e86419773 updated Christian Urban <urbanc@in.tum.de> parents: 268 diff changeset	9	//
492 17e6f46260bd updated Christian Urban <christian.urban@kcl.ac.uk> parents: 464 diff changeset	10	// java -cp .:scala3-library_3-3.2.2.jar:scala-parallel-collections_3-1.0.4.jar Sudoku
301 aa0e86419773 updated Christian Urban <urbanc@in.tum.de> parents: 268 diff changeset	11
462 c9fa27e4906a updated to scala 3 Christian Urban <christian.urban@kcl.ac.uk> parents: 447 diff changeset	12
268 d20583497c5b updated Christian Urban <urbanc@in.tum.de> parents: diff changeset	13
d20583497c5b updated Christian Urban <urbanc@in.tum.de> parents: diff changeset	14	import scala.collection.parallel.CollectionConverters._
d20583497c5b updated Christian Urban <urbanc@in.tum.de> parents: diff changeset	15
d20583497c5b updated Christian Urban <urbanc@in.tum.de> parents: diff changeset	16	type Pos = (Int, Int)
d20583497c5b updated Christian Urban <urbanc@in.tum.de> parents: diff changeset	17	val emptyValue = '.'
d20583497c5b updated Christian Urban <urbanc@in.tum.de> parents: diff changeset	18	val maxValue = 9
d20583497c5b updated Christian Urban <urbanc@in.tum.de> parents: diff changeset	19
d20583497c5b updated Christian Urban <urbanc@in.tum.de> parents: diff changeset	20	val allValues = "123456789".toList
d20583497c5b updated Christian Urban <urbanc@in.tum.de> parents: diff changeset	21	val indexes = (0 to 8).toList
d20583497c5b updated Christian Urban <urbanc@in.tum.de> parents: diff changeset	22
d20583497c5b updated Christian Urban <urbanc@in.tum.de> parents: diff changeset	23
d20583497c5b updated Christian Urban <urbanc@in.tum.de> parents: diff changeset	24	def empty(game: String) = game.indexOf(emptyValue)
d20583497c5b updated Christian Urban <urbanc@in.tum.de> parents: diff changeset	25	def isDone(game: String) = empty(game) == -1
384 627a944c744b updated Christian Urban <christian.urban@kcl.ac.uk> parents: 383 diff changeset	26
383 72d6a4af4b4a updated Christian Urban <christian.urban@kcl.ac.uk> parents: 329 diff changeset	27	//def emptyPosition(game: String) : Pos =
72d6a4af4b4a updated Christian Urban <christian.urban@kcl.ac.uk> parents: 329 diff changeset	28	// (empty(game) % maxValue, empty(game) / maxValue)
384 627a944c744b updated Christian Urban <christian.urban@kcl.ac.uk> parents: 383 diff changeset	29
383 72d6a4af4b4a updated Christian Urban <christian.urban@kcl.ac.uk> parents: 329 diff changeset	30	def emptyPosition(game: String) = {
72d6a4af4b4a updated Christian Urban <christian.urban@kcl.ac.uk> parents: 329 diff changeset	31	val e = empty(game)
72d6a4af4b4a updated Christian Urban <christian.urban@kcl.ac.uk> parents: 329 diff changeset	32	(e % maxValue, e / maxValue)
72d6a4af4b4a updated Christian Urban <christian.urban@kcl.ac.uk> parents: 329 diff changeset	33	}
268 d20583497c5b updated Christian Urban <urbanc@in.tum.de> parents: diff changeset	34
d20583497c5b updated Christian Urban <urbanc@in.tum.de> parents: diff changeset	35
d20583497c5b updated Christian Urban <urbanc@in.tum.de> parents: diff changeset	36	def get_row(game: String, y: Int) = indexes.map(col => game(y * maxValue + col))
d20583497c5b updated Christian Urban <urbanc@in.tum.de> parents: diff changeset	37	def get_col(game: String, x: Int) = indexes.map(row => game(x + row * maxValue))
d20583497c5b updated Christian Urban <urbanc@in.tum.de> parents: diff changeset	38
d20583497c5b updated Christian Urban <urbanc@in.tum.de> parents: diff changeset	39	def get_box(game: String, pos: Pos): List[Char] = {
d20583497c5b updated Christian Urban <urbanc@in.tum.de> parents: diff changeset	40	def base(p: Int): Int = (p / 3) * 3
d20583497c5b updated Christian Urban <urbanc@in.tum.de> parents: diff changeset	41	val x0 = base(pos._1)
d20583497c5b updated Christian Urban <urbanc@in.tum.de> parents: diff changeset	42	val y0 = base(pos._2)
d20583497c5b updated Christian Urban <urbanc@in.tum.de> parents: diff changeset	43	for (x <- (x0 until x0 + 3).toList;
d20583497c5b updated Christian Urban <urbanc@in.tum.de> parents: diff changeset	44	y <- (y0 until y0 + 3).toList) yield game(x + y * maxValue)
d20583497c5b updated Christian Urban <urbanc@in.tum.de> parents: diff changeset	45	}
d20583497c5b updated Christian Urban <urbanc@in.tum.de> parents: diff changeset	46
d20583497c5b updated Christian Urban <urbanc@in.tum.de> parents: diff changeset	47
d20583497c5b updated Christian Urban <urbanc@in.tum.de> parents: diff changeset	48	def update(game: String, pos: Int, value: Char): String =
d20583497c5b updated Christian Urban <urbanc@in.tum.de> parents: diff changeset	49	game.updated(pos, value)
d20583497c5b updated Christian Urban <urbanc@in.tum.de> parents: diff changeset	50
d20583497c5b updated Christian Urban <urbanc@in.tum.de> parents: diff changeset	51	def toAvoid(game: String, pos: Pos): List[Char] =
d20583497c5b updated Christian Urban <urbanc@in.tum.de> parents: diff changeset	52	(get_col(game, pos._1) ++ get_row(game, pos._2) ++ get_box(game, pos))
d20583497c5b updated Christian Urban <urbanc@in.tum.de> parents: diff changeset	53
d20583497c5b updated Christian Urban <urbanc@in.tum.de> parents: diff changeset	54	def candidates(game: String, pos: Pos): List[Char] =
d20583497c5b updated Christian Urban <urbanc@in.tum.de> parents: diff changeset	55	allValues.diff(toAvoid(game, pos))
d20583497c5b updated Christian Urban <urbanc@in.tum.de> parents: diff changeset	56
462 c9fa27e4906a updated to scala 3 Christian Urban <christian.urban@kcl.ac.uk> parents: 447 diff changeset	57	// search for all solutions
268 d20583497c5b updated Christian Urban <urbanc@in.tum.de> parents: diff changeset	58	def search(game: String): List[String] = {
d20583497c5b updated Christian Urban <urbanc@in.tum.de> parents: diff changeset	59	if (isDone(game)) List(game)
d20583497c5b updated Christian Urban <urbanc@in.tum.de> parents: diff changeset	60	else
464 1b1330cde075 updated Christian Urban <christian.urban@kcl.ac.uk> parents: 462 diff changeset	61	candidates(game, emptyPosition(game)).par.
268 d20583497c5b updated Christian Urban <urbanc@in.tum.de> parents: diff changeset	62	map(c => search(update(game, empty(game), c))).toList.flatten
d20583497c5b updated Christian Urban <urbanc@in.tum.de> parents: diff changeset	63	}
d20583497c5b updated Christian Urban <urbanc@in.tum.de> parents: diff changeset	64
447 0cf1b374e146 updated Christian Urban <christian.urban@kcl.ac.uk> parents: 446 diff changeset	65
462 c9fa27e4906a updated to scala 3 Christian Urban <christian.urban@kcl.ac.uk> parents: 447 diff changeset	66	// search for single solution
325 26058bf089ae updated Christian Urban <urbanc@in.tum.de> parents: 321 diff changeset	67	def search1T(games: List[String]): Option[String] = games match {
26058bf089ae updated Christian Urban <urbanc@in.tum.de> parents: 321 diff changeset	68	case Nil => None
26058bf089ae updated Christian Urban <urbanc@in.tum.de> parents: 321 diff changeset	69	case game::rest => {
26058bf089ae updated Christian Urban <urbanc@in.tum.de> parents: 321 diff changeset	70	if (isDone(game)) Some(game)
26058bf089ae updated Christian Urban <urbanc@in.tum.de> parents: 321 diff changeset	71	else {
26058bf089ae updated Christian Urban <urbanc@in.tum.de> parents: 321 diff changeset	72	val cs = candidates(game, emptyPosition(game))
26058bf089ae updated Christian Urban <urbanc@in.tum.de> parents: 321 diff changeset	73	search1T(cs.map(c => update(game, empty(game), c)) ::: rest)
26058bf089ae updated Christian Urban <urbanc@in.tum.de> parents: 321 diff changeset	74	}
26058bf089ae updated Christian Urban <urbanc@in.tum.de> parents: 321 diff changeset	75	}
26058bf089ae updated Christian Urban <urbanc@in.tum.de> parents: 321 diff changeset	76	}
26058bf089ae updated Christian Urban <urbanc@in.tum.de> parents: 321 diff changeset	77
329 828326d1b3b2 updated Christian Urban <urbanc@in.tum.de> parents: 325 diff changeset	78	def pretty(game: String): String =
383 72d6a4af4b4a updated Christian Urban <christian.urban@kcl.ac.uk> parents: 329 diff changeset	79	"\n" + (game.grouped(maxValue).mkString(",\n"))
329 828326d1b3b2 updated Christian Urban <urbanc@in.tum.de> parents: 325 diff changeset	80
828326d1b3b2 updated Christian Urban <urbanc@in.tum.de> parents: 325 diff changeset	81
301 aa0e86419773 updated Christian Urban <urbanc@in.tum.de> parents: 268 diff changeset	82	// a list of hard games according to Andrew Coles and Peter Norvig
268 d20583497c5b updated Christian Urban <urbanc@in.tum.de> parents: diff changeset	83
d20583497c5b updated Christian Urban <urbanc@in.tum.de> parents: diff changeset	84	val hard_games =
321 f6cb539e0ffb updated Christian Urban <urbanc@in.tum.de> parents: 320 diff changeset	85	List("52...6.........7.13...........4..8..6......5...........418.........3..2...87.....",
301 aa0e86419773 updated Christian Urban <urbanc@in.tum.de> parents: 268 diff changeset	86	"6.....8.3.4.7.................5.4.7.3..2.....1.6.......2.....5.....8.6......1....",
aa0e86419773 updated Christian Urban <urbanc@in.tum.de> parents: 268 diff changeset	87	"48.3............71.2.......7.5....6....2..8.............1.76...3.....4......5....",
aa0e86419773 updated Christian Urban <urbanc@in.tum.de> parents: 268 diff changeset	88	"......52..8.4......3...9...5.1...6..2..7........3.....6...1..........7.4.......3.",
aa0e86419773 updated Christian Urban <urbanc@in.tum.de> parents: 268 diff changeset	89	"6.2.5.........3.4..........43...8....1....2........7..5..27...........81...6.....",
aa0e86419773 updated Christian Urban <urbanc@in.tum.de> parents: 268 diff changeset	90	".524.........7.1..............8.2...3.....6...9.5.....1.6.3...........897........",
aa0e86419773 updated Christian Urban <urbanc@in.tum.de> parents: 268 diff changeset	91	"6.2.5.........4.3..........43...8....1....2........7..5..27...........81...6.....",
384 627a944c744b updated Christian Urban <christian.urban@kcl.ac.uk> parents: 383 diff changeset	92	".923.........8.1...........1.7.4...........658.........6.5.2...4.....7.....9.....",
301 aa0e86419773 updated Christian Urban <urbanc@in.tum.de> parents: 268 diff changeset	93	"85...24..72......9..4.........1.7..23.5...9...4...........8..7..17..........36.4.",
268 d20583497c5b updated Christian Urban <urbanc@in.tum.de> parents: diff changeset	94	"..53.....8......2..7..1.5..4....53...1..7...6..32...8..6.5....9..4....3......97..",
d20583497c5b updated Christian Urban <urbanc@in.tum.de> parents: diff changeset	95	"12..4......5.69.1...9...5.........7.7...52.9..3......2.9.6...5.4..9..8.1..3...9.4",
d20583497c5b updated Christian Urban <urbanc@in.tum.de> parents: diff changeset	96	"...57..3.1......2.7...234......8...4..7..4...49....6.5.42...3.....7..9....18.....",
d20583497c5b updated Christian Urban <urbanc@in.tum.de> parents: diff changeset	97	"7..1523........92....3.....1....47.8.......6............9...5.6.4.9.7...8....6.1.",
d20583497c5b updated Christian Urban <urbanc@in.tum.de> parents: diff changeset	98	"1....7.9..3..2...8..96..5....53..9...1..8...26....4...3......1..4......7..7...3..",
d20583497c5b updated Christian Urban <urbanc@in.tum.de> parents: diff changeset	99	"1...34.8....8..5....4.6..21.18......3..1.2..6......81.52..7.9....6..9....9.64...2",
d20583497c5b updated Christian Urban <urbanc@in.tum.de> parents: diff changeset	100	"...92......68.3...19..7...623..4.1....1...7....8.3..297...8..91...5.72......64...",
d20583497c5b updated Christian Urban <urbanc@in.tum.de> parents: diff changeset	101	".6.5.4.3.1...9...8.........9...5...6.4.6.2.7.7...4...5.........4...8...1.5.2.3.4.",
d20583497c5b updated Christian Urban <urbanc@in.tum.de> parents: diff changeset	102	"7.....4...2..7..8...3..8.799..5..3...6..2..9...1.97..6...3..9...3..4..6...9..1.35",
d20583497c5b updated Christian Urban <urbanc@in.tum.de> parents: diff changeset	103	"....7..2.8.......6.1.2.5...9.54....8.........3....85.1...3.2.8.4.......9.7..6....",
d20583497c5b updated Christian Urban <urbanc@in.tum.de> parents: diff changeset	104	"52...6.........7.13...........4..8..6......5...........418.........3..2...87.....",
d20583497c5b updated Christian Urban <urbanc@in.tum.de> parents: diff changeset	105	"6.....8.3.4.7.................5.4.7.3..2.....1.6.......2.....5.....8.6......1....",
d20583497c5b updated Christian Urban <urbanc@in.tum.de> parents: diff changeset	106	"48.3............71.2.......7.5....6....2..8.............1.76...3.....4......5....",
d20583497c5b updated Christian Urban <urbanc@in.tum.de> parents: diff changeset	107	"......52..8.4......3...9...5.1...6..2..7........3.....6...1..........7.4.......3.",
d20583497c5b updated Christian Urban <urbanc@in.tum.de> parents: diff changeset	108	"6.2.5.........3.4..........43...8....1....2........7..5..27...........81...6.....",
d20583497c5b updated Christian Urban <urbanc@in.tum.de> parents: diff changeset	109	".524.........7.1..............8.2...3.....6...9.5.....1.6.3...........897........",
d20583497c5b updated Christian Urban <urbanc@in.tum.de> parents: diff changeset	110	"6.2.5.........4.3..........43...8....1....2........7..5..27...........81...6.....",
d20583497c5b updated Christian Urban <urbanc@in.tum.de> parents: diff changeset	111	".923.........8.1...........1.7.4...........658.........6.5.2...4.....7.....9.....",
d20583497c5b updated Christian Urban <urbanc@in.tum.de> parents: diff changeset	112	"6..3.2....5.....1..........7.26............543.........8.15........4.2........7..",
d20583497c5b updated Christian Urban <urbanc@in.tum.de> parents: diff changeset	113	".6.5.1.9.1...9..539....7....4.8...7.......5.8.817.5.3.....5.2............76..8...",
d20583497c5b updated Christian Urban <urbanc@in.tum.de> parents: diff changeset	114	"..5...987.4..5...1..7......2...48....9.1.....6..2.....3..6..2.......9.7.......5..",
d20583497c5b updated Christian Urban <urbanc@in.tum.de> parents: diff changeset	115	"3.6.7...........518.........1.4.5...7.....6.....2......2.....4.....8.3.....5.....",
d20583497c5b updated Christian Urban <urbanc@in.tum.de> parents: diff changeset	116	"1.....3.8.7.4..............2.3.1...........958.........5.6...7.....8.2...4.......",
d20583497c5b updated Christian Urban <urbanc@in.tum.de> parents: diff changeset	117	"6..3.2....4.....1..........7.26............543.........8.15........4.2........7..",
d20583497c5b updated Christian Urban <urbanc@in.tum.de> parents: diff changeset	118	"....3..9....2....1.5.9..............1.2.8.4.6.8.5...2..75......4.1..6..3.....4.6.",
d20583497c5b updated Christian Urban <urbanc@in.tum.de> parents: diff changeset	119	"45.....3....8.1....9...........5..9.2..7.....8.........1..4..........7.2...6..8..",
d20583497c5b updated Christian Urban <urbanc@in.tum.de> parents: diff changeset	120	".237....68...6.59.9.....7......4.97.3.7.96..2.........5..47.........2....8.......",
d20583497c5b updated Christian Urban <urbanc@in.tum.de> parents: diff changeset	121	"..84...3....3.....9....157479...8........7..514.....2...9.6...2.5....4......9..56",
d20583497c5b updated Christian Urban <urbanc@in.tum.de> parents: diff changeset	122	".98.1....2......6.............3.2.5..84.........6.........4.8.93..5...........1..",
d20583497c5b updated Christian Urban <urbanc@in.tum.de> parents: diff changeset	123	"..247..58..............1.4.....2...9528.9.4....9...1.........3.3....75..685..2...",
d20583497c5b updated Christian Urban <urbanc@in.tum.de> parents: diff changeset	124	".2.3......63.....58.......15....9.3....7........1....8.879..26......6.7...6..7..4",
d20583497c5b updated Christian Urban <urbanc@in.tum.de> parents: diff changeset	125	"1.....7.9.4...72..8.........7..1..6.3.......5.6..4..2.........8..53...7.7.2....46",
d20583497c5b updated Christian Urban <urbanc@in.tum.de> parents: diff changeset	126	"4.....3.....8.2......7........1...8734.......6........5...6........1.4...82......",
d20583497c5b updated Christian Urban <urbanc@in.tum.de> parents: diff changeset	127	".......71.2.8........4.3...7...6..5....2..3..9........6...7.....8....4......5....",
d20583497c5b updated Christian Urban <urbanc@in.tum.de> parents: diff changeset	128	"6..3.2....4.....8..........7.26............543.........8.15........8.2........7..",
d20583497c5b updated Christian Urban <urbanc@in.tum.de> parents: diff changeset	129	".47.8...1............6..7..6....357......5....1..6....28..4.....9.1...4.....2.69.",
d20583497c5b updated Christian Urban <urbanc@in.tum.de> parents: diff changeset	130	"......8.17..2........5.6......7...5..1....3...8.......5......2..4..8....6...3....",
d20583497c5b updated Christian Urban <urbanc@in.tum.de> parents: diff changeset	131	"38.6.......9.......2..3.51......5....3..1..6....4......17.5..8.......9.......7.32",
d20583497c5b updated Christian Urban <urbanc@in.tum.de> parents: diff changeset	132	"...5...........5.697.....2...48.2...25.1...3..8..3.........4.7..13.5..9..2...31..",
d20583497c5b updated Christian Urban <urbanc@in.tum.de> parents: diff changeset	133	".2.......3.5.62..9.68...3...5..........64.8.2..47..9....3.....1.....6...17.43....",
d20583497c5b updated Christian Urban <urbanc@in.tum.de> parents: diff changeset	134	".8..4....3......1........2...5...4.69..1..8..2...........3.9....6....5.....2.....",
d20583497c5b updated Christian Urban <urbanc@in.tum.de> parents: diff changeset	135	"..8.9.1...6.5...2......6....3.1.7.5.........9..4...3...5....2...7...3.8.2..7....4",
d20583497c5b updated Christian Urban <urbanc@in.tum.de> parents: diff changeset	136	"1.....3.8.6.4..............2.3.1...........958.........5.6...7.....8.2...4.......",
d20583497c5b updated Christian Urban <urbanc@in.tum.de> parents: diff changeset	137	"1....6.8..64..........4...7....9.6...7.4..5..5...7.1...5....32.3....8...4........",
d20583497c5b updated Christian Urban <urbanc@in.tum.de> parents: diff changeset	138	"249.6...3.3....2..8.......5.....6......2......1..4.82..9.5..7....4.....1.7...3...",
d20583497c5b updated Christian Urban <urbanc@in.tum.de> parents: diff changeset	139	"...8....9.873...4.6..7.......85..97...........43..75.......3....3...145.4....2..1",
d20583497c5b updated Christian Urban <urbanc@in.tum.de> parents: diff changeset	140	"......8.16..2........7.5......6...2..1....3...8.......2......7..3..8....5...4....",
d20583497c5b updated Christian Urban <urbanc@in.tum.de> parents: diff changeset	141	".476...5.8.3.....2.....9......8.5..6...1.....6.24......78...51...6....4..9...4..7",
d20583497c5b updated Christian Urban <urbanc@in.tum.de> parents: diff changeset	142	".....7.95.....1...86..2.....2..73..85......6...3..49..3.5...41724................",
d20583497c5b updated Christian Urban <urbanc@in.tum.de> parents: diff changeset	143	".4.5.....8...9..3..76.2.....146..........9..7.....36....1..4.5..6......3..71..2..",
d20583497c5b updated Christian Urban <urbanc@in.tum.de> parents: diff changeset	144	".834.........7..5...........4.1.8..........27...3.....2.6.5....5.....8........1..",
d20583497c5b updated Christian Urban <urbanc@in.tum.de> parents: diff changeset	145	"..9.....3.....9...7.....5.6..65..4.....3......28......3..75.6..6...........12.3.8",
d20583497c5b updated Christian Urban <urbanc@in.tum.de> parents: diff changeset	146	".26.39......6....19.....7.......4..9.5....2....85.....3..2..9..4....762.........4",
d20583497c5b updated Christian Urban <urbanc@in.tum.de> parents: diff changeset	147	"2.3.8....8..7...........1...6.5.7...4......3....1............82.5....6...1.......",
d20583497c5b updated Christian Urban <urbanc@in.tum.de> parents: diff changeset	148	"6..3.2....1.....5..........7.26............843.........8.15........8.2........7..",
d20583497c5b updated Christian Urban <urbanc@in.tum.de> parents: diff changeset	149	"1.....9...64..1.7..7..4.......3.....3.89..5....7....2.....6.7.9.....4.1....129.3.",
d20583497c5b updated Christian Urban <urbanc@in.tum.de> parents: diff changeset	150	".........9......84.623...5....6...453...1...6...9...7....1.....4.5..2....3.8....9",
d20583497c5b updated Christian Urban <urbanc@in.tum.de> parents: diff changeset	151	".2....5938..5..46.94..6...8..2.3.....6..8.73.7..2.........4.38..7....6..........5",
d20583497c5b updated Christian Urban <urbanc@in.tum.de> parents: diff changeset	152	"9.4..5...25.6..1..31......8.7...9...4..26......147....7.......2...3..8.6.4.....9.",
d20583497c5b updated Christian Urban <urbanc@in.tum.de> parents: diff changeset	153	"...52.....9...3..4......7...1.....4..8..453..6...1...87.2........8....32.4..8..1.",
d20583497c5b updated Christian Urban <urbanc@in.tum.de> parents: diff changeset	154	"53..2.9...24.3..5...9..........1.827...7.........981.............64....91.2.5.43.",
d20583497c5b updated Christian Urban <urbanc@in.tum.de> parents: diff changeset	155	"1....786...7..8.1.8..2....9........24...1......9..5...6.8..........5.9.......93.4",
d20583497c5b updated Christian Urban <urbanc@in.tum.de> parents: diff changeset	156	"....5...11......7..6.....8......4.....9.1.3.....596.2..8..62..7..7......3.5.7.2..",
d20583497c5b updated Christian Urban <urbanc@in.tum.de> parents: diff changeset	157	".47.2....8....1....3....9.2.....5...6..81..5.....4.....7....3.4...9...1.4..27.8..",
d20583497c5b updated Christian Urban <urbanc@in.tum.de> parents: diff changeset	158	"......94.....9...53....5.7..8.4..1..463...........7.8.8..7.....7......28.5.26....",
d20583497c5b updated Christian Urban <urbanc@in.tum.de> parents: diff changeset	159	".2......6....41.....78....1......7....37.....6..412....1..74..5..8.5..7......39..",
d20583497c5b updated Christian Urban <urbanc@in.tum.de> parents: diff changeset	160	"1.....3.8.6.4..............2.3.1...........758.........7.5...6.....8.2...4.......",
d20583497c5b updated Christian Urban <urbanc@in.tum.de> parents: diff changeset	161	"2....1.9..1..3.7..9..8...2.......85..6.4.........7...3.2.3...6....5.....1.9...2.5",
d20583497c5b updated Christian Urban <urbanc@in.tum.de> parents: diff changeset	162	"..7..8.....6.2.3...3......9.1..5..6.....1.....7.9....2........4.83..4...26....51.",
d20583497c5b updated Christian Urban <urbanc@in.tum.de> parents: diff changeset	163	"...36....85.......9.4..8........68.........17..9..45...1.5...6.4....9..2.....3...",
d20583497c5b updated Christian Urban <urbanc@in.tum.de> parents: diff changeset	164	"34.6.......7.......2..8.57......5....7..1..2....4......36.2..1.......9.......7.82",
d20583497c5b updated Christian Urban <urbanc@in.tum.de> parents: diff changeset	165	"......4.18..2........6.7......8...6..4....3...1.......6......2..5..1....7...3....",
d20583497c5b updated Christian Urban <urbanc@in.tum.de> parents: diff changeset	166	".4..5..67...1...4....2.....1..8..3........2...6...........4..5.3.....8..2........",
d20583497c5b updated Christian Urban <urbanc@in.tum.de> parents: diff changeset	167	".......4...2..4..1.7..5..9...3..7....4..6....6..1..8...2....1..85.9...6.....8...3",
d20583497c5b updated Christian Urban <urbanc@in.tum.de> parents: diff changeset	168	"8..7....4.5....6............3.97...8....43..5....2.9....6......2...6...7.71..83.2",
d20583497c5b updated Christian Urban <urbanc@in.tum.de> parents: diff changeset	169	".8...4.5....7..3............1..85...6.....2......4....3.26............417........",
d20583497c5b updated Christian Urban <urbanc@in.tum.de> parents: diff changeset	170	"....7..8...6...5...2...3.61.1...7..2..8..534.2..9.......2......58...6.3.4...1....",
d20583497c5b updated Christian Urban <urbanc@in.tum.de> parents: diff changeset	171	"......8.16..2........7.5......6...2..1....3...8.......2......7..4..8....5...3....",
d20583497c5b updated Christian Urban <urbanc@in.tum.de> parents: diff changeset	172	".2..........6....3.74.8.........3..2.8..4..1.6..5.........1.78.5....9..........4.",
d20583497c5b updated Christian Urban <urbanc@in.tum.de> parents: diff changeset	173	".52..68.......7.2.......6....48..9..2..41......1.....8..61..38.....9...63..6..1.9",
d20583497c5b updated Christian Urban <urbanc@in.tum.de> parents: diff changeset	174	"....1.78.5....9..........4..2..........6....3.74.8.........3..2.8..4..1.6..5.....",
d20583497c5b updated Christian Urban <urbanc@in.tum.de> parents: diff changeset	175	"1.......3.6.3..7...7...5..121.7...9...7........8.1..2....8.64....9.2..6....4.....",
d20583497c5b updated Christian Urban <urbanc@in.tum.de> parents: diff changeset	176	"4...7.1....19.46.5.....1......7....2..2.3....847..6....14...8.6.2....3..6...9....",
d20583497c5b updated Christian Urban <urbanc@in.tum.de> parents: diff changeset	177	"......8.17..2........5.6......7...5..1....3...8.......5......2..3..8....6...4....",
d20583497c5b updated Christian Urban <urbanc@in.tum.de> parents: diff changeset	178	"963......1....8......2.5....4.8......1....7......3..257......3...9.2.4.7......9..",
d20583497c5b updated Christian Urban <urbanc@in.tum.de> parents: diff changeset	179	"15.3......7..4.2....4.72.....8.........9..1.8.1..8.79......38...........6....7423",
d20583497c5b updated Christian Urban <urbanc@in.tum.de> parents: diff changeset	180	"..........5724...98....947...9..3...5..9..12...3.1.9...6....25....56.....7......6",
d20583497c5b updated Christian Urban <urbanc@in.tum.de> parents: diff changeset	181	"....75....1..2.....4...3...5.....3.2...8...1.......6.....1..48.2........7........",
d20583497c5b updated Christian Urban <urbanc@in.tum.de> parents: diff changeset	182	"6.....7.3.4.8.................5.4.8.7..2.....1.3.......2.....5.....7.9......1....",
d20583497c5b updated Christian Urban <urbanc@in.tum.de> parents: diff changeset	183	"....6...4..6.3....1..4..5.77.....8.5...8.....6.8....9...2.9....4....32....97..1..",
d20583497c5b updated Christian Urban <urbanc@in.tum.de> parents: diff changeset	184	".32.....58..3.....9.428...1...4...39...6...5.....1.....2...67.8.....4....95....6.",
d20583497c5b updated Christian Urban <urbanc@in.tum.de> parents: diff changeset	185	"...5.3.......6.7..5.8....1636..2.......4.1.......3...567....2.8..4.7.......2..5..",
d20583497c5b updated Christian Urban <urbanc@in.tum.de> parents: diff changeset	186	".5.3.7.4.1.........3.......5.8.3.61....8..5.9.6..1........4...6...6927....2...9..",
d20583497c5b updated Christian Urban <urbanc@in.tum.de> parents: diff changeset	187	"..5..8..18......9.......78....4.....64....9......53..2.6.........138..5....9.714.",
d20583497c5b updated Christian Urban <urbanc@in.tum.de> parents: diff changeset	188	"..........72.6.1....51...82.8...13..4.........37.9..1.....238..5.4..9.........79.",
d20583497c5b updated Christian Urban <urbanc@in.tum.de> parents: diff changeset	189	"...658.....4......12............96.7...3..5....2.8...3..19..8..3.6.....4....473..",
d20583497c5b updated Christian Urban <urbanc@in.tum.de> parents: diff changeset	190	".2.3.......6..8.9.83.5........2...8.7.9..5........6..4.......1...1...4.22..7..8.9",
d20583497c5b updated Christian Urban <urbanc@in.tum.de> parents: diff changeset	191	".5..9....1.....6.....3.8.....8.4...9514.......3....2..........4.8...6..77..15..6.",
d20583497c5b updated Christian Urban <urbanc@in.tum.de> parents: diff changeset	192	".....2.......7...17..3...9.8..7......2.89.6...13..6....9..5.824.....891..........",
321 f6cb539e0ffb updated Christian Urban <urbanc@in.tum.de> parents: 320 diff changeset	193	"3...8.......7....51..............36...2..4....7...........6.13..452...........8..",
f6cb539e0ffb updated Christian Urban <urbanc@in.tum.de> parents: 320 diff changeset	194	"....14....3....2...7..........9...3.6.1.............8.2.....1.4....5.6.....7.8...",
f6cb539e0ffb updated Christian Urban <urbanc@in.tum.de> parents: 320 diff changeset	195	"4.....8.5.3..........7......2.....6.....8.4......1.......6.3.7.5..2.....1.4......")
384 627a944c744b updated Christian Urban <christian.urban@kcl.ac.uk> parents: 383 diff changeset	196
329 828326d1b3b2 updated Christian Urban <urbanc@in.tum.de> parents: 325 diff changeset	197
268 d20583497c5b updated Christian Urban <urbanc@in.tum.de> parents: diff changeset	198
d20583497c5b updated Christian Urban <urbanc@in.tum.de> parents: diff changeset	199	// for measuring time
d20583497c5b updated Christian Urban <urbanc@in.tum.de> parents: diff changeset	200	def time_needed[T](i: Int, code: => T) = {
d20583497c5b updated Christian Urban <urbanc@in.tum.de> parents: diff changeset	201	val start = System.nanoTime()
d20583497c5b updated Christian Urban <urbanc@in.tum.de> parents: diff changeset	202	for (j <- 1 to i) code
d20583497c5b updated Christian Urban <urbanc@in.tum.de> parents: diff changeset	203	val end = System.nanoTime()
301 aa0e86419773 updated Christian Urban <urbanc@in.tum.de> parents: 268 diff changeset	204	(end - start) / i / 1.0e9
268 d20583497c5b updated Christian Urban <urbanc@in.tum.de> parents: diff changeset	205	}
d20583497c5b updated Christian Urban <urbanc@in.tum.de> parents: diff changeset	206
d20583497c5b updated Christian Urban <urbanc@in.tum.de> parents: diff changeset	207
462 c9fa27e4906a updated to scala 3 Christian Urban <christian.urban@kcl.ac.uk> parents: 447 diff changeset	208	@main
c9fa27e4906a updated to scala 3 Christian Urban <christian.urban@kcl.ac.uk> parents: 447 diff changeset	209	def test() = {
c9fa27e4906a updated to scala 3 Christian Urban <christian.urban@kcl.ac.uk> parents: 447 diff changeset	210	val total =
c9fa27e4906a updated to scala 3 Christian Urban <christian.urban@kcl.ac.uk> parents: 447 diff changeset	211	(for ((game, i) <- hard_games.zipWithIndex) yield {
c9fa27e4906a updated to scala 3 Christian Urban <christian.urban@kcl.ac.uk> parents: 447 diff changeset	212	val secs = time_needed(1, search(game))
c9fa27e4906a updated to scala 3 Christian Urban <christian.urban@kcl.ac.uk> parents: 447 diff changeset	213	println(f"${i}%2.0f: ${game} \|${secs}%2.3f secs")
c9fa27e4906a updated to scala 3 Christian Urban <christian.urban@kcl.ac.uk> parents: 447 diff changeset	214	secs
c9fa27e4906a updated to scala 3 Christian Urban <christian.urban@kcl.ac.uk> parents: 447 diff changeset	215	}).sum
301 aa0e86419773 updated Christian Urban <urbanc@in.tum.de> parents: 268 diff changeset	216
462 c9fa27e4906a updated to scala 3 Christian Urban <christian.urban@kcl.ac.uk> parents: 447 diff changeset	217	println(f"\ntotal: ${total}%.3f secs")
268 d20583497c5b updated Christian Urban <urbanc@in.tum.de> parents: diff changeset	218	}
d20583497c5b updated Christian Urban <urbanc@in.tum.de> parents: diff changeset	219
301 aa0e86419773 updated Christian Urban <urbanc@in.tum.de> parents: 268 diff changeset	220
aa0e86419773 updated Christian Urban <urbanc@in.tum.de> parents: 268 diff changeset	221
462 c9fa27e4906a updated to scala 3 Christian Urban <christian.urban@kcl.ac.uk> parents: 447 diff changeset	222	// some numbers:
c9fa27e4906a updated to scala 3 Christian Urban <christian.urban@kcl.ac.uk> parents: 447 diff changeset	223	//
c9fa27e4906a updated to scala 3 Christian Urban <christian.urban@kcl.ac.uk> parents: 447 diff changeset	224	// single thread version 800 secs
446 30b8f14b2655 updated Christian Urban <christian.urban@kcl.ac.uk> parents: 384 diff changeset	225	//
320 90aed247c8cf updated Christian Urban <urbanc@in.tum.de> parents: 301 diff changeset	226	// 4 cores parallel version on a moderate laptop 400 secs
90aed247c8cf updated Christian Urban <urbanc@in.tum.de> parents: 301 diff changeset	227	// 8 cores: 290 secs
446 30b8f14b2655 updated Christian Urban <christian.urban@kcl.ac.uk> parents: 384 diff changeset	228	// 10 cores: 156 secs
320 90aed247c8cf updated Christian Urban <urbanc@in.tum.de> parents: 301 diff changeset	229	// 18 cores: 142 secs
301 aa0e86419773 updated Christian Urban <urbanc@in.tum.de> parents: 268 diff changeset	230

author	Christian Urban <christian.urban@kcl.ac.uk>
	Fri, 12 Sep 2025 10:36:07 +0100
changeset 492	17e6f46260bd
parent 464	1b1330cde075
permissions	-rw-r--r--