Судоку своими руками

Хочу рассказать вам, дорогие читатели блога, об одной своей программке на Icon, о которой очень хотелось рассказать когда-то давно (еще в 2016 году), но тогда не хватало времени, чтобы описать свой игровой эксперимент. Так уж сложилось, что самое интересное, что я делаю на Icon — это игры, и данный случай — не исключение.

Дело в том, что у меня папа очень любит одну японскую головоломку, а мне явно не хватало вдохновения и идеи, чего бы такого запрограммировать, поэтому после недолгих размышлений, я решил для папы написать свою реализацию судоку, а что из этого получилось, вы можете увидеть заглянув под кат этой статьи. Итак, начнем с того, что такое судоку.

Судоку — это популярная японская головоломка, которая представляет собой цифровое поле 9 на 9 клеток, в котором уже поставлены некоторые цифры от 1 до 9. Также, внутри квадрата 9 на 9, есть разделение линиями на меньшие квадраты размером 3 на 3. Это разделение существует с одной стороны для облегчения решения головоломки, с другой стороны, оно является непосредственным элементом самих правил.

Вот так выглядит обычное поле для игры в судоку:

Правила судоку интуитивно просты и понятны: нужно заполнить все игровое поле цифрами от 1 до 9 таким образом, чтобы цифры в строке или столбце не повторялись, при этом также важен тот факт, что в квадратах 3 на 3, также не должно быть повторяющихся цифр. Поскольку, на поле уже присутствуют некоторые из цифр, то располагая этой информацией и необходимо поставить недостающие (согласно описанным правилам), и таким образом осуществить решение самой головоломки.

Теперь можно приступить к реализации задуманного…

Для построения судоку нам необходимо создать саму сетку и разместить в ней некоторым образом цифры, сгенерировав их абсолютно случайным образом:

procedure grid(win)
local i,j,siz
siz:=40
every i:=0 to 8 do {
	every j:=0 to 8 do {
	Fg(win,"gray")	
        DrawRectangle(win,i*siz,j*siz,siz,siz)
}
}
end

procedure square(win)
local i,j
every i:=0 to 2 do {
	every j:=0 to 2 do {
	WAttrib(win,"linewidth=2")	
	Fg(win,"black")	
	DrawRectangle(win,i*120,j*120,120,120)	
	}
}
end

procedure lremove(l,n)
local a,b
a:=l[1:n]
b:=l[n+1:*l+1]
return a|||b
end

procedure r_str()
local pull,s,i
s:=""
pull:=[1,2,3,4,5,6,7,8,9]
every i:=1 to 9 do {
 randomize()	
 siz:=?(*pull)
 s||:=pull[siz]
 pull:=lremove(pull,siz)
}
return s
end

Работают эти процедуры так: сначала с помощью процедуры grid, мы в окне программы просто чертим серую сетку из 81 квадрата (т.е. делаем обычное игровое поле, размером 9 на 9); затем с помощью процедуры square мы выделяем жирными черными линиями 9 квадратов размером 3 на 3 (т.е. разделяем игровое поле на несколько крупных квадратов, согласно правилам судоку); далее используя вспомогательную процедуру lremove для удаления из списка n-ого элемента реализуем необходимую нам далее процедуру r_str, которая формирует одну строку нашего судоку и которая пригодиться нам далее.

Теперь, начинается самое интересное: создание алгоритма построения судоку из одной строки случайно сгенерированных неповторяющихся цифр (вот зачем нам процедура r_str).

Алгоритм построения судоку после очень долгих раздумий получился таким: сначала мы берем строку случайных цифр, а затем создаем из нее 8 оставшихся строк с помощью сдвига самой строки на некоторые фиксированные значения сдвига вправо (данные значения были найдены в ходе долгих поисков по интернету и некоторых экспериментов), затем все 9 строк из цифр мы размещаем на игровом поле, после чего случайным образом стираем некоторое количество цифр (количество цифр определено экспериментально).

Реализация соответственно будет такой:

procedure sshift(s,n)
local a
a:=repl(s,n)
if s=0 then return s else return a[(n+1)+:(*s)]
end

procedure hide()
local i,j
every i:=0 to 9 do {
	every j:=0 to 9 do {
		if ((?100)-?7)>30 then {
			EraseArea(i*40+1,j*40+1,38,38)
		}
	}
}
end

Также нам потребуется создание списка, который будет хранить решение головоломки, поэтому создаем глобальную переменную с пустым списком solv и создаем процедуру рисования всех 9 строк пока без удаления из них цифр:

procedure sudoku()
local i,sh,s,j
s:=r_str()
sh:=[0,3,3,4,3,3,4,3,3]
every i:=1 to *sh do {
 s:=sshift(s,sh[i])
 every j:=1 to *s do {
  Fg("blue")
  DrawString((i-1)*40+15,(j-1)*40+25,s[j])
  put(solv,i,j,s[j])
 }
}
end

Процедура удаления цифр также весьма проста:

procedure hide()
local i,j
every i:=0 to 9 do {
	every j:=0 to 9 do {
		if ((?100)-?7)>30 then {
			EraseArea(i*40+1,j*40+1,38,38)
		}
	}
}
end

Поскольку, пока существует сама судоку без стираний, легко определить процедуру отображения решения самой головоломки, сделав его отображение на основе существующих процедур, но в отдельном окне:

procedure show_solve(col)
local i,j,zz,xx,yy,W
W:=WOpen("size=360,400")
grid(W)
square(W)
Fg(W,col)
every i:=1 to *solv by 3 do {
 xx:=(solv[i]-1)*40+15
 yy:=(solv[i+1]-1)*40+25
 zz:=solv[i+2]
 DrawString(W,xx,yy,zz)
}
case Event(W) of {
 &lpress : if Active(W) then WClose(W)
}
end

Если вспомнить наши предыдущие статьи по созданию всяких мелких игрушек на Icon, то процедуры осуществления хода и его отмены выглядят весьма банально, а изменяется только привязка к конкретным координатам в окне:

procedure find_xy(a,b)
local i,j,xx,yy,t
every i:=1 to 9 do {
	every j:=1 to 9 do {
	xx:=i*40
        yy:=j*40
        if xx<=a<=(xx+40) & yy<=b<=(yy+40) then {
         GotoXY(xx+15,yy+25)
         Fg("red")
         t:=WRead()
         DrawString(xx+15,yy+25,t)
        }
	}
}
end

procedure clear_xy(a,b)
local i,j,xx,yy,t
every i:=1 to 9 do {
	every j:=1 to 9 do {
	xx:=i*40
        yy:=j*40
        if xx<=a<=(xx+40) & yy<=b<=(yy+40) then {
         EraseArea(xx+1,yy+1,38,38)
        }
	}
}

Объединим теперь все это в одну программу, собрав все процедуры и импорты в основную процедуру:

link graphics,random
global solv,sud
procedure main()
local W,i,j
W:=WOpen("size=360,400")
solv:=list()
grid(W)
square(W)
sudoku()
hide()
repeat {
case Event() of {
	&lpress : find_xy(&x,&y)
	&rpress : clear_xy(&x,&y)
	"s" : show_solve("darkgreen")
	"q" : exit()
 	
}
}
WDone()
end

Итак, пользователь делает ход, щелкнув левой клавишей мыши по интересующей его клетке и осуществив вод нужной цифры, отмена хода осуществляется щелчком правой клавишей мыши по неправильно поставленной цифре (защита от дурака, к сожалению, не предусмотрена, поскольку писалось все, как говорится, на коленке); а отображение правильного решения осуществляется по нажатию клавиши s.

Это выглядит так:

Подводя итоги, скажу, что мой папа очень был доволен тем, что получил в свои руки классную минималистическую игрушку, за которой он может отдохнуть от работы, однако, для себя я вынес следующую мораль: не стоит писать код в таком стиле, даже если программа делается за один вечер, а необходимо детально вникнуть в проблему и создать качественный код, поскольку внезапно может выясниться, что исходник программы всплывает через несколько лет…