5 Replies - 3144 Views - Last Post: 19 December 2011 - 09:16 AM Rate Topic: -----

#1 cupidvogel  Icon User is offline

  • D.I.C Addict

Reputation: 31
  • View blog
  • Posts: 593
  • Joined: 25-November 10

Python sudoku solver strategy algo

Posted 13 December 2011 - 11:49 PM

Hi, I am writing a Python Sudoku Solver which will solve the sudoku with sheer logic and no need for backtracking. There is one strategy I would like to implement, but I can't think of a way apart from lots of looping. In the image, see that all the candidate 7's in the first row are restricted to the 3rd grid only (1st row 7th and 8th columns). Since a 7 has to appear in the first row, we can safely eliminate 7's from other cells in the 3rd grid (in this case, only 2nd row 9th column), which in turn will expose a hidden 7 in 4th row last column. Now how do I implement this strategy? That is, for every row, for all candidates occurring in that row in different cells (3,7,8 and 9 for 1st row), if one candidate is restricted to one grid only, that candidate should be eliminated from other cells in that grid. Same goes for column. And similarly for a grid, if one particular candidate occurs in one row or one column only, then that candidate can be excluded from other cells in that row or column. I have a dictionary dic, where the key is the element's coordinates (I am implementing the matrix through numpy), and the value is its corresponding current list of candidates. If the cell has an established value, dic doesn't have that cell's coordinates as its key. For example dic[(0,2)] doesn't exist, as sudoku[0][2] has a value of 6, while dic[(1,8)] = [1,3,7] (2nd row 8th column). Any idea how to implement this check without excessive looping?

Attached image(s)

  • Attached Image

This post has been edited by cupidvogel: 13 December 2011 - 11:51 PM


Is This A Good Question/Topic? 0
  • +

Replies To: Python sudoku solver strategy algo

#2 SwiftStriker00  Icon User is offline

  • No idea why my code works
  • member icon

Reputation: 432
  • View blog
  • Posts: 1,596
  • Joined: 25-December 08

Re: Python sudoku solver strategy algo

Posted 16 December 2011 - 09:40 AM

Well when I was in school there were two ways I did went about a solver, one was complicated and was in Assembly the other was much simpler. Depth First Search is your friend for these types of problems.

While BFS may be a little brutish, you can always use different heuristics to smarten up its decisions
Was This Post Helpful? 0
  • +
  • -

#3 cupidvogel  Icon User is offline

  • D.I.C Addict

Reputation: 31
  • View blog
  • Posts: 593
  • Joined: 25-November 10

Re: Python sudoku solver strategy algo

Posted 16 December 2011 - 10:11 AM

The near entirety of sudoku solvers found on net use depth first search. That might be easier technically (indeed I myself designed one two or three years back in C), but the method completely takes the challenge out of it, and reduces a challenging problem to a brute force one. Hence I am trying to devise it such that it won't have any need for guessing, each step would be logical.
Was This Post Helpful? 0
  • +
  • -

#4 Simown  Icon User is offline

  • Blue Sprat
  • member icon

Reputation: 319
  • View blog
  • Posts: 650
  • Joined: 20-May 10

Re: Python sudoku solver strategy algo

Posted 16 December 2011 - 04:54 PM

Well, the request was for a sudoku solver "with no need for backtracking". If this is the case then you might want to reconsider, depth first search inherently uses backtracking; with a fixed search tree, it may well have a benefit over breath-first search.

Lots of looping could be the way forward, if you can do it that way, although sudoku puzzles are often treated as NP-complete.

This post has been edited by Simown: 16 December 2011 - 05:00 PM

Was This Post Helpful? 0
  • +
  • -

#5 cupidvogel  Icon User is offline

  • D.I.C Addict

Reputation: 31
  • View blog
  • Posts: 593
  • Joined: 25-November 10

Re: Python sudoku solver strategy algo

Posted 17 December 2011 - 03:34 AM

Well, I said that I don't want backtracking, that is way I haven't gone for depth first search. So can anyone suggest an algo to solve this particular problem?
Was This Post Helpful? 0
  • +
  • -

#6 effecypeKab  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 3
  • Joined: 24-August 11

Re: Python sudoku solver strategy algo

Posted 19 December 2011 - 09:16 AM

курсы аппаратного маникюра
обучение наращиванию ногтей в иркутске
косметика venus купить
прыщи на головке фото
варианты макияжа фото
торт из туалетной бумаги
арха карие глаза
стрижки для девушек
румяна chanel
играть бесплатно приготовление иды прически макияж одевалка
letual каталог в кортинках
как называется широкое женское пальто
макияж как у элис кален
какой крем для ног лучше
обучающие центры парикмахеров
стриженная машинка для барана
интернет магазин парикмахеров
вечерние платья 52-54размера
регистрация косметики
макияж мастер класс онлайн
модные стрижки для подростков фото
скачать программу для подбора причесок торрент
увеличение груди в казахстане
макияж для зеленых глаз видео
guerlain parure пудра отзывы
модная одежда в уфе
частные объявления косметолог
лондестраль купить киев
кто из известных артистов делает мезотерапию фото
журналы парикмахерского искусства
краска для волос syoss палитра
туфли regbnm
афро прическа
прокат вечерних платьев в сургуте
вечерние зеленые платья
волосатые письки жен
тушь для ресниц орифлейм
где взять вечернее платье напрокат
velvet крем для депиляции отзывы
уроки зротического массажа смотреть онлайн
роспись ногтей по-мокрому
мастер-класс как разрисовать серьги
наращивание ресниц на дому
рейтинг парфюмерии
парикмахерская лотос
платья вечернее класическое
почему желтеют части тела
desheli отзывы
художественная роспись ногтей фото
оттенки wella
магазины парфюмерии в санкт петербурге
покраска ресниц отзывы
парикмахерская в кузьминках
настольная книга начинающего фотографа скачать
кератиновое выпрямление волос
товары для косметологов
прическа за 5 мин
трафареты интимных мужских причесок
депиляции видео скрытая камера
шампуни утяжеляющие волосы
наращивание ногтей акрилом новосибирск
ив роше крем для рук
сити фитнес отзывы
gta bote оты
одежда для учителей
карты для landwirtschafts simulator 2009 моды
биологическая завивка волос
фитнес клуб с бассейном
шоколадный кутюрье
оранжевые туфли
keenwell купить
наращивание ногтей фрейзер
увеличение малой половой губы
одевалки макияж онлайн бесплатно
тушь для ресниц мейбелин
прически китайских императоров
голова куклы для причесок и макияжа
завивка с эффектом мокрых олос
эпиляция половых губ
игры барби причёски
восстановление после пилинга
вечерний макияж для кареглазой шатенки
если у мужчины длинные ресницы есть лекарство
смывки краски для волос в запорожье
женские стрижки спб
самый лучший парфюм для мужчин
сколько стоит автозагар в салоне
как плести косички по голове картинки
старики ебут горничных
причёски с чёлкой для парней фото
амер кутюрье
avon 1 2010
bogart туалетная вода
конкурс красоты девочек нудистов смотреть онлайн бесплатно без регистрации
гинзбург скачать бесплатно худеем с аппетитом
студия сочи волгоград 7 ветров
парфюмерия ноты
моды для игры мафия
тушь nivea
лазерная эпиляция лица отзывы
где можно купить шапмунь yes to
стрижка волчица видео
восточная косметика
парфюмерия косметика омск
макияж радуга
музыка из рекламы тушь буржуа
бесплатно скачать причёски для симс 3
какающие бесплатно смотреть
выбор вечернего платья
ysl помада
игры онлайн макияж и прически
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1